Official
C - Catastrophic Roulette Editorial by physics0523
ヒントHint 1
DP(動的計画法) で求解することを考えます。
例えば、 DP の index(添え字) に 「今までにルーレットを何度回したか」を持ってしまうと無限個の状態を管理する羽目になります。
管理する状態の個数を少なく抑えて求解することを考えましょう。何をどう管理するべきでしょうか?
Hint 2
今までに出た整数の種類数を \(q\) とし、 \(q\) ごとに以下の量を管理することを考えましょう。
- 出た整数の種類数が $q$ になった直後の手番が 先攻 / 後攻 である確率
- 出た整数の種類数が $q$ になった直後の時点で、 先攻 / 後攻 が支払う罰金の期待値
\(q=1,2,\dots,N-1\) について順にこれらの量を更新していくことでこの問題に正解できます。
丁寧に立式して、これを実現しましょう。
Hint 3
\(0 < p < 1\) について、 \(\displaystyle 1 + p^2 + p^4 + p^6 + \dots = \sum_{i=0}^{\infty} p^{2i} = \frac{1}{1-p^2}\) が成り立ちます。
無限和の処理に困った場合はこのヒントが役に立つかもしれません。
posted:
last update: