期待値DPと確率DPの例 - ぱるまの日記

こんにちは、ぱるまです。

最近 AtCoder で出た期待値DP/確率DPの問題を整理してみました。具体的には以下の3問を整理してみました。

共通の話

後ろから考えるとうまく解けがちです。
遷移のグラフを作って、（入っていく方の辺より）出ていく方の辺を考えると良さそうです
グラフのループがある場合は一次方程式が立てられるはずです。
- 一次方程式を解く際はゼロ除算に注意です。

ABC326 E - Revenge of "The Salary of AtCoder Inc."

問題の概要は以下の通りです。

$N$ 面ダイスと変数 $x=0$ を用意する。
以下の手順を繰り返す。

ダイスを1度振って出た目を $y$ をする。

もし $x < y$ ならば $A_y$ 円支給し、$x = y$ と更新する。

そうでないならば終了する。

このとき支給された金額の合計値の期待値 ${}\bmod{998244353}$ は？

[制約]

$1 \leq N \leq 3 \times 10^5$

$0 \leq A_i < 998244353$

これは以下のように DP をすることで解けます。（画像では $N$ が $n$ になっていますが気にしないてください）

遷移をグラフにして、dp[i] を考えるときは頂点 i から出ていく辺に着目して、漸化式を作りました。

この問題はループがないシンプルなパターンです。

自分の提出(Rust): https://atcoder.jp/contests/abc326/submissions/51019715

ABC333 F - Bomb Game 2

問題の概要は以下の通りです。

$N$ 人の人が一列に並んでいる。人 $i$ は先頭から $i$ 番目に並んでいる。
以下の操作を $1$ 人になるまで繰り返します。

列の先頭にいる人を $1/2$ の確率で列から取り除く。取り除かない場合は列の末尾に移す。

$i=1,2,\ldots, N$ に対して、人 $i$ が列にいる最後の1人になる確率 ${}\bmod{998244353}$ は？

[制約]

$2 \leq N \leq 3000$

これは以下のように DP をすることで解けます。

ループの部分は一次方程式を解くことで、DP 配列の各値が求められます。

ゼロ除算が発生しないことの確認

${}\bmod{998244353}$ で $1/(2^{i+1}) \equiv 1$ のとき、ゼロ除算が発生します。

$1/(2^{i+1}) \equiv 1$ は $2^{i+1} \equiv 1$ と同値です。

ここで、$2^{k} \equiv 1$ となる最小の正整数 $k$ は $k = (998244353-1)/2$ であることが実験からわかります*1。

# 実験の例 (Python)
x = 1
for i in range(1, 998244353):
    x = (x * 2) % 998244353
    if x == 1:
        print(i) # (998244353-1)/2 = 499122176 が出力される
        break

$1 \leq i \leq N$ で $N=3000$ なので、 $2^{i+1} \not\equiv 1$ が成り立ちます。よって、今回の制約下ではゼロ除算が発生しません

自分の提出(Rust): https://atcoder.jp/contests/abc333/submissions/48595243

ARC 174 C - Catastrophic Roulette

問題の概要は以下の通りです。

整数 $1,2,\ldots ,N$ が均等な確率で出るルーレットがある。 2人で以下のゲームをする

先攻と後攻が交互にルーレットを回す。

出た整数が今までに出ていないものであった場合、何も起こらない。

そうでない場合、ルーレットを回したプレイヤーが罰金 $1$ 円を払う。

$N$ 個の整数すべてが少なくとも $1$ 度出たとき、ただちにゲームが終了する。

先行後攻それぞれについて、ゲームが終了するまでに支払う罰金の期待値 ${}\bmod{998244353}$ は？

[制約]

$1 \leq N \leq 10^6$

これは以下のように DP をすることで解けます。

ABC333 F - Bomb Game 2 と大体同じです。

ゼロ除算が発生しないことの確認

${}\bmod{998244353}$ で $(i/N)^2 \equiv 1$ のとき、ゼロ除算が発生します。

$(i/N)^2 \equiv 1$ は $i^2 \equiv N^2$ つまり $(N + i)(N-i) \equiv 0$ と同値です。ここで、$0 \leq i < N$ と問題の制約 $2 \leq N \leq 3000$ から $N{}+i$ と $N-i$ はともに $998244353$ の倍数になりません。つまり、$(N + i)(N-i) \not \equiv 0$ です。

よって、今回の制約下ではゼロ除算が発生しません。

自分の提出(Rust): https://atcoder.jp/contests/arc174/submissions/52441869