Grenache's blog

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

2015年08月

問題概要

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

解法

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

考察

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

問題概要

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

解法

「ゲームでお互いが最善を尽くしたとき」という問題は、どちらか片方のプレイヤー側から見た場合の状態を考えるとうまくいくと思います。また、DPは実際に求めたいものを設定するのが良いと言われています。ということで、ある状態でのその時以降に先手が取れるものの価値の合計を考えます。

先手が取る番の時は、左右の山どちらかの物を取った後の状態から得られる価値の合計がわかっていれば、今から取るものと取った後の状態から得られる価値の和が大きくなるように取ります。

後手が取る番の時は、その状態で先手が得られる価値の合計は後手が取った後の状態から得られる価値の合計になります(後手が取っても先手の合計は増えないので)。従って、後手が最善を尽くすということは、先手にとっては最悪なので、取った後に先手が得られる価値が少なくなるように取ります。

漸化式の定義: $$\begin{eqnarray} dp[i][j] & = & \begin{cases} \max\{dp[i-1][j]+a_{A+1-i},\ dp[i][j-1]+b_{B+1-j}\} & (先手の番) \\ \min\{dp[i-1][j],\ dp[i][j-1]\} & (後手の番) \end{cases}\\ dp[0][j] & = & \begin{cases} dp[0][j-1]+b_{B+1-j} & (先手の番) \\ dp[0][j-1] & (後手の番) \end{cases}\\ dp[i][0] & = & \begin{cases} dp[i-1][0]+a_{A+1-i} & (先手の番) \\ dp[i-1][0] & (後手の番) \end{cases} \end{eqnarray}$$

$dp[i][j]$:左の山に$i$個、右の山に$j$個のものが残っている状態で、その状態から終了までに先手が得られる価値の合計 $(0\le i \le A,\ 0\le j \le B)$

$a_k$:左の山の上から$k$番目の物の価値$(1\le k \le A)$

$b_k$:右の山の上から$k$番目の物の価値$(1\le k \le B)$

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

求める解:$dp[A][B]$

先手の番か後手の番かは、これまでに取った物の数($A+B-(i+j)$)が偶数か奇数かで判断します。

考察

お互いに最善な戦略をとったときって、漸化式をどちらの目線で定義したかを意識しないと、何が最善なのかがこんがらがることが多いです。

ちなみに、$i,\ j$を左の山から$i$個、右の山から$j$個取った状態という風に、逆のインデックスのほうがわかりやすかったりするのでしょうか。どうも他の方の解説を見ると、逆になっていることが多い気がします。

問題概要

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

試行回数の期待値を求める基本問題です。いわゆるコンプガチャの期待値の問題で、回数の期待値を求める問題があることを知りました。

解法

試行回数の期待値を求める問題では、ある状態から1回の試行によって遷移する状態の期待値との漸化式を立ててそれを動的計画法で解くことになります。基本的には、下記の式の形になるようです。

$$\mathrm{E}[Z]=1+\mathrm{E}[Z_1]\cdot p_1+\mathrm{E}[Z_2]\cdot p_2+...+\mathrm{E}[Z_n]\cdot p_n$$

$Z$の状態から、1回の試行によってそれぞれ$p_i$の確率で$Z_i$の状態に遷移する場合。

ここではなぜ上記の式になるのかを考えるため、確率変数の定義とその確率分布を意識していきたいと思います。

$X_i$:これまでの目の合計が$i$のとき、合計が$K$になるまでに振ることになる回数

このように考えると、求める期待値は$X_0$の期待値、$i\ge K$のときすでに$K$を超えているので、$\mathrm{E}[X_i]=0$となります。

ここで、これまでの目の合計が$i$の時に次に振るさいころの目が$1$であると仮定した場合の$X_i$の期待値を考えると、目の合計が$i+1$の時の期待値に$1$が出た試行1回を足したものになります。これは$X_i$の条件付き期待値と呼ばれるもので、式で表すと次のようになります。

$$\mathrm{E}[X_i|Y=1]=1+\mathrm{E}[X_{i+1}]$$

$Y$:これまでの目の合計が$i$のとき、次に振るさいころの目の値

同様にその他の目が出た時を考えると、次の確率分布を満たすような確率変数$\mathrm{E}[X_i|Y]$を定義することができます。

$\mathrm{E}[X_i|Y]$ $\scriptsize 1+\mathrm{E}[X_{i+1}]$ $\scriptsize 1+\mathrm{E}[X_{i+2}]$ $\scriptsize 1+\mathrm{E}[X_{i+3}]$ $\scriptsize 1+\mathrm{E}[X_{i+4}]$ $\scriptsize 1+\mathrm{E}[X_{i+5}]$ $\scriptsize 1+\mathrm{E}[X_{i+6}]$ 合計
確率 $\frac{1}{6}$ $\frac{1}{6}$ $\frac{1}{6}$ $\frac{1}{6}$ $\frac{1}{6}$ $\frac{1}{6}$ 1

ここで、条件付き期待値には$\mathrm{E}[\mathrm{E}[X_i|Y]]=\mathrm{E}[X_i]$という式が成り立つとのこと。したがって、$X_i$の期待値は$\mathrm{E}[X_i|Y]$の期待値を求めればよく、これは期待値の定義より下記になります。

$$\begin{eqnarray} \mathrm{E}[X_i] & = & \mathrm{E}[\mathrm{E}[X_i|Y]] \\ & = & (1+\mathrm{E}[X_{i+1}])\cdot \frac{1}{6}+(1+\mathrm{E}[X_{i+2}])\cdot \frac{1}{6}+...+(1+\mathrm{E}[X_{i+6}])\cdot \frac{1}{6} \\ & = & 1+\mathrm{E}[X_{i+1}]\cdot \frac{1}{6}+\mathrm{E}[X_{i+2}]\cdot \frac{1}{6}+...+\mathrm{E}[X_{i+6}]\cdot \frac{1}{6} \end{eqnarray}$$

例えば、$\mathrm{E}[X_{K-1}]=1+\mathrm{E}[X_{K}]\cdot \frac{1}{6}+\mathrm{E}[X_{K+1}]\cdot \frac{1}{6}+...+\mathrm{E}[X_{K+5}]\cdot \frac{1}{6}$となり、$i\ge K$のとき$\mathrm{E}[X_i]=0$より、$\mathrm{E}[X_{K-1}]=1$です。

漸化式にて$\mathrm{E}[X_{i}]$を$\mathrm{E}[X_{i+1}]~\mathrm{E}[X_{i+6}]$にて定義できているので、DPで$i$を$K-1$から$0$のループを回すことで$\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,\ dp[i]=dp[K](i\gt K)$

求める解:$dp[0]$

考察

条件付き期待値に関する情報は少なめだったので、最初の式をなかなか理解することができませんでした。結局このような形で、理解したつもりになっています。

  1. なにはなくとも蟻本です。Kindle版で読んでいます。とても広い範囲をカバーしている、実際に使えるコードが書いてある、などリファレンスとして必携だと思います。



  2. アルゴリズムイントロダクションは、自分が数学的な背景とか、何故そうなるのかを理解しないと他への応用がうまく出来ないので、その辺りを調べるのに助かります。総合版はハードカバーで1000ページ越えでとても持ち歩けるような代物ではありませんが、分冊版は精選トピックスの部分が絶版のようです。総合版を使ってます。


  3. このブログはコンプガチャの期待値問題がどうしても理解できなくて、それを調べ始めたことから作りました。その際に、確率統計の本も調べたのですが、この数学ガールの中に出てくる「サイコロのすべての目が出るまでの投げる回数の期待値」に関する部分が一番参考になりました。
    数学ガール/乱択アルゴリズム
    結城 浩
    SBクリエイティブ
    2014-03-12

  4. 数学的な基礎の強化にお勧めです。詳しくはこちらの記事を。

このページのトップヘ