Grenache's blog

競技プログラミング初心者です。

問題概要

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

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

解法

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

漸化式の定義: $$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回のDP問題を解いて、$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$の部分を変数と見たときの漸化式が成り立ちます。つまり、この問題は下記のようなDPと考えることができます。

漸化式の定義: $$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の方法で求めるやり方を記載しましたが、サンプルからこの漸化式を使って求めることもできます。

考察

よく似た2つのDPに帰着しましたが、よく考えると意味合いも式もちょっと違うんですね。この記事を書いてみて初めて意識することができました。

問題概要

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

解法

優勝するには$K$連勝するということになるので、人$i$が$j$連勝する確率を考えます。これは$j-1$連勝する確率がわかっているとすると、その確率に$j$ラウンド目で勝つ確率をかければ求められます。

$j$ラウンド目で勝つ確率は、そこで当たる可能性がある人に勝つ確率の和、つまり自分が勝ち上がってきたトーナメントの山側ではない人$k$が$j-1$連勝して、かつ、その人に勝つ確率の和となります。

漸化式の定義: $$dp[i][j]=dp[i][j-1]\sum_{k\in S}dp[k][j-1]\cdot \Pr\{人iが人kに勝つ\}$$

$dp[i][j]$:人$i$が$K$連勝する確率
$(0\le i \le 2^K-1,\ 0\le j \le K,\ S=\{$人$i$が$j$ラウンド目で当たる可能性のある人$\})$

初期値:$dp[i][0]=1$

求める解:$dp[i][K]$

ここで、集合$S$は下記の図のように、自分が勝ち上がってきたトーナメントの山の人ではなく、$j$ラウンド目で当たる可能性のある人なので、$i$の下位$j-1$ビット以外の部分が一致せず、$i$の下位$j$ビット以外の部分が一致する人$k$となる(ただし、問題と違って$i$,$k$を0-indexedと考えた場合)。$k$は、mask=0xffffffff$<<$(j-1), mask2=0xffffffff$<<$jとしたときに、(i$\&$mask)$\ne$(k$\&$mask)かつ(i$\&$mask2)$=$(k$\&$mask2)を満たす。

typicalDPC

考察

確率のDPは配るDPが多い気がしてましたが、これは貰うDPです。

問題概要

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

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

解法

基本的な考え方は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)$が単調増加だと分かるのですが、すぐにはわかりませんでした。今回はいずれも適当にやってみて決めることができますが、本番ではそこまでなかなか考えられません。。。

考察

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

このページのトップヘ