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]$ が答え。

Python3

programming_algorithm/contest_history/atcoder/2021/1023_abc224.txt · 最終更新: 2021/10/23 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0