問題概要

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

試行回数の期待値を求める問題で、漸化式の右辺に先の項が現れて、単純にボトムアップのループで解けない問題です。

解法

基本的な考え方はyukicoder No.65と同じです。ただ、合計がちょうど$K$にならないといけないので、$K$を超えたときの期待値が、$\mathrm{E}[X_0]$になります。つまり、下記のような漸化式になります。

漸化式の定義: $$dp[i]=1+dp[i+1]\cdot \frac{1}{6}+dp[i+2]\cdot \frac{1}{6}+...+dp[i+6]\cdot \frac{1}{6}$$

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

初期値:$dp[K]=0,\ \underline{dp[i]=dp[0](i\gt K)}$

求める解:$dp[0]$

この漸化式だと$i=K-1$の時に、$dp[K-1]=1+dp[K]\cdot \frac{1}{6}+dp[0]\cdot \frac{5}{6}$となって、この時点で$dp[0]$が出てくるので、単純にDPで$dp[K-1]$を求めることができません。つまりこれは、$K$個の未知数($dp[0],\ dp[1],...,dp[K-1]$)を$K$個の式から求める連立一次方程式になります。

しかし、この問題の場合は連立一次方程式を解かなくても解く方法があります。

1.漸化式で解く方法

単純なDPでは解けないといいましたが、$dp[K-1]$は$dp[0]$で表され、$dp[K-2]$は$dp[K-1],\ dp[0]$で表されて、結局$dp[i]=a_i\cdot dp[0]+b_i$と表されます。つまり、次の漸化式を解いて、最後に$dp[0]=a_0\cdot dp[0]+b_0$という$dp[0]$に関する一次方程式を解けば、解が得られます。

漸化式の定義: $$\begin{eqnarray} a_i & = & a_{i+1}\cdot \frac{1}{6}+...+a_{i+6}\cdot \frac{1}{6}\\ b_i & = & 1+b_{i+1}\cdot \frac{1}{6}+...+b_{i+6}\cdot \frac{1}{6} \end{eqnarray}$$

$a_i,\ b_i$:$dp[i]=a_i\cdot dp[0]+b_i$と表されると考えたときの係数

初期値:$a_K=0,\ b_K=0,\ a_i=1(i\gt K),\ b_i=0(i\gt K)$

求める解:$a_0,\ b_0$

2.二分探索で解く方法

$dp[0]=x$と仮の値を使って、$dp[K-1],\ dp[K-2],…,dp[0]$をDPのように求めていって、得られた$dp[0]$を$f(x)$とします。すると、$x=f(x)$となる$x$を求める問題と考えることができます。$x-f(x)$は単調増加な関数なので、これは$x$を二分探索で求めることもできます。$f(x)$を求めるのに$O(K)$なので、問題ありません。

ところで、二分探索の探索範囲はどのくらいに見積もるべきなんでしょうか?下限は0ですが、上限をどの程度にすればよいのかの根拠がわかりません。また、$x-f(x)$と$f(x)-x$のどちらが単調増加なのかってすぐわかるもんなんでしょうか?1.の方法の式まで考えると、$x-f(x)$が単調増加だと分かるのですが、すぐにはわかりませんでした。今回はいずれも適当にやってみて決めることができますが、本番ではそこまでなかなか考えられません。。。

考察

いろいろな解説を読んでじっくり考えて、やっとなぜ二分探索で求めることができるのかがわかりました。ほかにもガウス・ザイデル法やガウス・ジョルダン、モンテカルロ法を使ってもできるという解説もありました。コンテスト時間内にこれだけのことを考えるのはとても無理な気がしています。。。