yukicoder No.76 回数の期待値で練習 : Grenache's blog

問題概要

問題文はこちらを参照してください。

試行回数の期待値を求める問題で、yukicoder No.65によく似ていますが、複数の$K$(この問題文では$N$となっていますが、No.65の問題に合わせて$K$を使います)に対して期待値を求めなければいけません。

解法

期待値のＤＰとしての考え方はyukicoder No.65と同じです。各面が出る確率が$\frac{1}{6}$ではなく、それをサンプルから計算しないといけないという点が特殊です。それぞれの$K$について下記のＤＰで期待値を求めることができます。

漸化式の定義： $$dp[i]=1+dp[i+1]\cdot p_1+dp[i+2]\cdot p_2+...+dp[i+6]\cdot p_6$$

$dp[i]$：これまでの目の合計が$i$のとき、合計が$K$になるまでに振ることになる回数の期待値$(0\le i \le K,\ p_j：jの目が出る確率)$

初期値：$dp[K]=0,\ dp[i]=dp[K](i\gt K)$

求める解：$dp[0]$

$K=1$の時、$dp[0]=1$

$K=2$の時、$dp[0]=1+dp[1]\cdot p_1,\ dp[1]=1$

となり、サンプルで$K=1～6$の期待値があるので、6回のＤＰ問題を解いて、$K=6$までで$p_1～p_5$までの確率がわかります。さらに、$\displaystyle\sum_{i=1}^{6}p_i=1$なので、$p_6$も求めることができます。

しかし、この問題では50個の$K$について期待値を求めなければいけないので、このままではTLEの可能性があります。

ここで確率変数の定義に立ち返って見ます。

$X_{K,i}$：これまでの目の合計が$i$のとき、合計が$K$になるまでに振ることになる回数

この定義から、$K-i$が同じ値の場合は同じ回数と見なすことができて、$X_{K+j,i+j}=X_{K,i}$が成り立ちます。ここで求めなければいけないのは、それぞれの$K$について、$\mathrm{E}[X_{K,0}]$ですが、No.65の問題で考えた漸化式より、

$$\begin{eqnarray} \mathrm{E}[X_{K,0}] & = & 1+\mathrm{E}[X_{K,1}]\cdot p_1+\mathrm{E}[X_{K,2}]\cdot p_2+...+\mathrm{E}[X_{K,6}]\cdot p_6 \\ & = & 1+\mathrm{E}[X_{K-1,0}]\cdot p_1+\mathrm{E}[X_{K-2,0}]\cdot p_2+...+\mathrm{E}[X_{K-6,0}]\cdot p_6 \end{eqnarray}$$

と、$X_{K,i}$の$K$の部分を変数と見たときの漸化式が成り立ちます。つまり、この問題は下記のようなＤＰと考えることができます。

漸化式の定義： $$dp2[i]=1+dp2[i-1]\cdot p_1+dp2[i-2]\cdot p_2+...+dp2[i-6]\cdot p_6$$

$dp2[i]$：これまでの合計が0の状態から、合計が$i$になるまでに振ることになる回数の期待値$(p_j：jの目が出る確率)$

初期値：$dp2[i]=0(i\le 0)$

求める解：$dp2[i]$

先ほどは$p_i$についてNo.65の方法で求めるやり方を記載しましたが、サンプルからこの漸化式を使って求めることもできます。