【競プロ】期待値系のDPの基本と典型パターン

はじめに

期待値系のDPにどうしても慣れないので自分の感覚になじむように改めてまとめます
想定読者層は茶~青色くらいのAtCoderユーザです

期待値とは

まずは定義をwikipediaから引用してきました

確率論における期待値（きたいち、英: expected value）は確率変数を含む関数の実現値に確率の重みをつけた加重平均である[1]。  

ここで出てきたいくつかの用語の説明をします

確率変数

今回は競技プログラミングでの使用を想定しているので離散型確率変数を扱います
確率変数というのは確率的に何かしらの値をとる変数です。

たとえば偏りのないさいころの場合は確率変数 $X$ は $1,2,3,4,5,6$ のいずれかの値を取ります。
以上です。

それだけではあまり良さを感じられないので次に確率質量関数の説明をします。

確率質量関数

確率質量関数とは確率変数が取る値を引数にとり、その確率を返す関数です。
偏りのないさいころを例に確率質量関数 $f_X(x)$ は以下のような値を取ります。
$f_X(1)=f_X(2)=f_X(3)=f_X(4)=f_X(5)=f_X(6)=1/6$

これで期待値の説明をする準備が整いました。

期待値の定義の解釈

というわけで冒頭の文章さいころを例にしてを解釈します。

確率論における期待値（きたいち、英: expected value）は確率変数を含む関数の実現値に確率の重みをつけた加重平均である[1]。  

文章中の 確率変数を含む関数の実現値 とは　$1,2,3,4,5,6$ の値を指します。
確率の重みはそれぞれの値に対して1/6です。
つまり期待値は確率質量関数を用いて以下の式で定義されます

\sum_{i=1}^{n} x_if_X(x_i)

ここで $x_i$ はi個目の確率変数が取りうる値とし、$x_n$ まであるとします。

というわけでさいころの場合の出た目の期待値 $E$ は以下のように求めます。

\begin{align}
E &= x_1f_X(x_1)+x_2f_X(x_2)+x_3f_X(x_3)+x_4f_X(x_4)+x_5f_X(x_5)+x_6f_X(x_6) \\
&=1 \times \frac{1} {6} + 2 \times \frac{1} {6} + 3 \times \frac{1} {6} + 4 \times \frac{1} {6} + 5 \times \frac{1} {6} + 6 \times \frac{1} {6} \\
&= 3.5
\end{align}

プログラマ的には数式は理解しにくいかもしれないのでサンプルコードです。

# 確率変数が取りうる値X
X=[1,2,3,4,5,6]
# X[i]を取る確率P
P=[1/6,1/6,1/6,1/6,1/6,1/6]

E=0
for i in range(len(X)):
  E+=X[i]*P[i]

上記のコードの形式であればさいころが偏り2の目が他の目の2倍の確率で出るようになった時は $P$ を適切に書き換えればよいことがわかりやすいです($sum(P)$ は1である必要があることに注意)

すごろく系典型問題

上記で期待値とは何かを理解しましたが、だから問題が解けるというわけではありません。
そこで練習として以下の問題を考えましょう

問題

太郎君はすごろくをします。
最初太郎君は地点1におり、地点 $N$ につくまでサイコロを振ります。
太郎君が振るサイコロは $1,2,…,P$ の出目が一様ランダムに出るサイコロで、
地点 $x$ にいるときに自分の振ったサイコロの出目が $i$ であるとき、地点$min(x+i,N)$ に進みます。
地点Nにつくまでにサイコロを振る回数を求めてください

制約

制限時間 2s

\begin{align}
&2 \leq N \leq 10^5\\
&1 \leq P \leq 10\\
\end{align}

解法

いくつかダメな方針を含めて方針を列挙してみます。

ダメそうな方針

サイコロのすべての出目を追う $\rightarrow$ 多分 $10^{10^4}$ くらいの計算が必要です。
$dp[i][j]$=i回サイコロを振って地点jにいるというDP $\rightarrow$ さいころをN回振る可能性があるので $O(N^2)$ です

なんとかなりそうな解法

前から$E[i]$ を地点iにいるときのサイコロを振った回数の期待値とし、$P[i]$ を地点Nを目指す過程でを地点iにとまる確率として地点1から遷移する $\rightarrow$ できます。結構大変です。

素敵な解法

$E[i]$ を地点iにいるときのサイコロを振った回数の期待値とし、地点Nから遷移する

素敵な解法解説

というわけで問題は前からも解くことができますがゴール状態からDPの遷移を考えたほうが簡単です

サンプルとして$N=4,P=3$ を考えます
今回はある地点から地点Nにつくまでに振るさいころの期待値について考えます

ゴールの1つ手前

1回サイコロを振ればゴールができます

ゴールの2つ手前

1が出た場合のみ2回その他の場合1回
1が出る確率は1/3なので期待値は $2 \times \frac{1}{3}+1 \times \frac{2}{3} = \frac{4}{3} $

ゴールの3つ手前

3が出た場合1回
2が出た場合2回
1が出た場合ゴールの2つ手前の期待値+1回
期待値は $1 \times \frac{1}{3} +2 \times \frac{1}{3} + (\frac{4}{3}+1) \times \frac{1}{3} = \frac{16}{9}$

上記より求める答えは $\frac{16}{9}$ となります。

つまり下記のような遷移で求めることができます

E[i]=\sum_{k=1}^{P} E[i-k]/P

問題設定の追加

上記の問題からいくつか派生形のを考えていきます。
難易度が高いわりに説明が簡素なのでわからなくても気にしないでください。
また、既存の問題とかぶっているものが多い事にも注意が必要です

振り出しに戻るマスの追加

• 1次式を持つDP
• 未知変数2分探索

目に0を含む

0が出る可能性がある場合には注意が必要です。
これはさいころの目の0以外が初めて出るまでの回数の期待値を求め1回ではなく0以外が初めて出る回数振ったとして0の目を除外します
ここで0以外の目が出る確率が$p$であるとき0以外の目が初めて出るまでにさいころを振る回数の期待値は$\frac{1}{1-p}$ です。導出はi回目に初めて事象が起きる確率を極限使って足し続ければできますが省略します