AtCoder Beginner Contest 224 G問題メモ
G - Roll or Increment
問題
- $1~N$ の目が出る $N$ 面サイコロがある
- はじめ、出目は $S$ であり、出目が $T$ である状態にしたい
- 以下の2つの操作をどちらでも好きな回数行える
- コスト $A$ で出目を1増やす(出目が $N$ 未満の場合のみ可能)
- コスト $B$ でサイコロを振り、出目を $1~N$ のいずれかに等確率に変化させる
- かかるコストを最小化させる戦略をとったとき、期待値を求めよ
- $1 \le N \le 10^9$
解法
遷移ループのあり得る期待値問題。
$rem[i]$ を、現在の出目が $i$ であるとき、最適戦略をとった場合の残りコスト期待値とする。
こういう問題は、何かしらの値を変数 $X$ とおいて、 変数含みで $rem[i]$ の値などを求めてやり、 その後、何らかの値を2通りの $X$ を含む式で表してやれば、$X$ を解いてめでたしめでたし、という解法がある。
$rem$ は、とりあえず $rem[T]=0$ であることはわかるが、 他は今の段階では操作 $A$ を選ぶべきか $B$ を選ぶべきかわからない。が、必ず $N,A,B,T$ によって一意に決まる値ではある。
操作 $B$ を選ぶ場合
操作 $B$ を選択した場合、$i=1~N$ について、確率 $\dfrac{1}{N}$ で遷移先が $rem[i]$ になる。
これは、遷移元の出目が何であろうと関係ない。
$rem$ の平均を $E$ とおくと、$B+E$(具体的にはまだ求まらないが、固定値)となる。
操作 $A$ を選ぶ場合
現在の出目 $i \gt T$ なら、操作 $A$ を行う意味は無い。
操作 $A$ を行った後に操作 $B$ を行うのは無駄なので、 $A$ を行った後は $T$ までひたすら $A$ を使い続けることになる。
つまり、操作 $A$ で $T$ にするのにかかるコストは $A(T-i)$ となる。
戦略
コスト最小化戦略をとるなら、各 $i \lt T$ につき $A(T-i)$ と $B+E$ の小さい方を選ぶことになる。
N=5 A=10 B=4 S T 1 2 3 4 5 rem[1] min(30, 4+E) ┐ rem[2] min(20, 4+E) │ rem[3] min(10, 4+E) │平均E rem[4] 0 │ rem[5] 4+E ┘
$B+E$ の方は固定値なので、何かしらの境界 $x$ があって、 以下のような形になっているはず(各範囲は長さが0の場合もある)。
- $[1, x)$ は操作 $B$ が最適
- $[x, T)$ は操作 $A$ が最適
- $[T+1, N]$ は操作 $B$ が最適
ここで、その切り替わる境界がどこかを仮定すると $E$ は計算できる。
仮に 現在の出目が 1 の場合は操作B、 2,3 の場合は操作Aが最適とした場合 rem[1] 4+E ┐ rem[2] 20 ├ 38+2E → (38+2E)/5 = E rem[3] 10 │ ↓ rem[4] 0 │ E=12.666... rem[5] 4+E ┘
境界を誤った値に仮定してしまうと、 $A(T-i), B+E$ の選択でコストの高い方を選んでしまうということなので、 $E$ は実際より大きくなる。
真の境界より離れれば離れるほど、高いコストの方を選ぶ数が増えるので、$E$ はますます大きくなる。
つまり、$E$ は境界 $x$ をピークとして下に凸のグラフとなっていることになる。
三分探索を使えば、$E$ の最小値、およびそれを実現できる境界 $x$ を求められる。
$x,S,T$ の大小関係によって場合分けし、$rem[S]$ が答え。