Grenache's blog

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

問題概要

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

解法

「ゲームでお互いが最善を尽くしたとき」という問題は、どちらか片方のプレイヤー側から見た場合の状態を考えるとうまくいくと思います。また、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. 数学的な基礎の強化にお勧めです。詳しくはこちらの記事を。

このページのトップヘ