AtCoder Typical DP Contest J ボール : Grenache's blog

問題概要

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

期待値のところで長い間苦労した問題です。

解法

以前、yukicoder No.65で説明した条件付き期待値を使って計算することになります。まずは確率変数を定義します。

$S=\{x_1,x_2,...,x_N\}$(最初に物が置いてある座標の集合)

$S_i\subseteq S$($S$の部分集合)

$X_{S_i}$：集合$S_i$の座標に物が残っているときに、全ての物を倒すのに必要なボールを投げる回数

このような確率変数を定義すると求めたいのは確率変数$X_S$の期待値$\mathrm{E}[X_{S}]$です。

ここで、条件付き期待値の考え方で次にボールをどこに投げるのかによって新しい確率変数$\mathrm{E}[X_{S_i}|Y]$を定義して、その確率分布を示します。

$\mathrm{E}[X_{S_i}\|Y]$	$1+\mathrm{E}[X_{S_i-\{x-1\}}]$	$1+\mathrm{E}[X_{S_i-\{x\}}]$	$1+\mathrm{E}[X_{S_i-\{x+1\}}]$	合計
確率	$\frac{1}{3}$	$\frac{1}{3}$	$\frac{1}{3}$	1

$Y$：次にボールを座標$x$に投げたときに飛んでいく先の座標

結局、yukicoder No.65と同じように求める期待値は以下になります。

$$\begin{eqnarray} \mathrm{E}[X_{S_i}] & = & \mathrm{E}[\mathrm{E}[X_{S_i}|Y]] \\ & = & 1+\mathrm{E}[X_{S_i-\{x-1\}}]\cdot \frac{1}{3}+\mathrm{E}[X_{S_i-\{x\}}]\cdot \frac{1}{3}+\mathrm{E}[X_{S_i-\{x+1\}}]\cdot \frac{1}{3} \end{eqnarray}$$

ここで、$S_i-\{x\}$は集合$S_i$に$x$という座標が含まれていたらそれを除いた残りの集合という意味ですが、つまりはボールが飛んで行った先の座標にあった物が倒れた後の状態の期待値で表されるということを意味します。しかし、座標$x$にボールを投げたときに、$x-1,x,x+1$それぞれに必ず物があるとは限りません。座標$x$に物がない場合は、$S_i-\{x\}=S_i$となってしまいます。ということは、先ほどの漸化式の右辺にも$\mathrm{E}[X_{S_i}]$が現れるので、式の変形が必要となります。

また、集合$S_i$の要素は0～15の数値で重複はないので、bitDPが使えます。この後は、集合$S_i$を整数$i$にマッピングして表したとします。

漸化式の定義： $$\begin{eqnarray} dp[i] & = & \min\{1+dp[i\ \scriptsize clear\normalsize(x-1)]\cdot \frac{1}{3}+dp[i\ \scriptsize clear\normalsize(x)]\cdot \frac{1}{3}\\ & + & dp[i\ \scriptsize clear\normalsize(x+1)]\cdot \frac{1}{3}:x=1,2,...,14\} \end{eqnarray}$$

$dp[i]$：集合$S_i$の座標に物が残っているときに、全ての物を倒すのに必要なボールを投げる回数の期待値

$i$：集合$S_i$の要素(0～15の値)を$i$のビットの位置とみなして、要素に含まれる座標のビットを1とした場合の整数。ただし、$S_i\subseteq S$なので、$i\ \&\ \tilde{I}=0$が成り立つ$i$のみ。(最初に物がないところのビットが1になっている$i$の時は計算しない)

$i\ \scriptsize clear\normalsize(x)$：整数$i$の$x$番目のビットを0とした場合の整数

$(0\le i \lt I,\ 0\le x \le 15,\ I$:集合$S$の要素(最初に物がある位置の座標)のビットを全て1とした場合の整数)

初期値：$dp[0]=0$、その他は$INF$(適切な大きな値)

求める解：$dp[I]$

$i$のループですが、$S_i\subset S_j$の時には$i\lt j$が成り立つので、小さい値から$i=1～I$のループを回せばよいことになります。

$x$は倒れる確率が3か所とも同じなので、両端の座標0や15に投げる意味がない(倒れる対象が2か所になってしまうので1つ内側の1や14ほうが回数は少なくて済む)のでループに含めません。また、$x-1,x,x+1$全てに物がない場合も投げても意味がない(無駄に回数が増えるだけ)のでその場合は値の更新はありません。もし、$x-1$に物がない場合は$i=i\ \scriptsize clear\normalsize(x-1)$なので、右辺にも$dp[i]$が現れます。したがって、式を変形して$dp[i]=(1+dp[i\ \scriptsize clear\normalsize(x)]\cdot \frac{1}{3}+dp[i\ \scriptsize clear\normalsize(x+1)]\cdot \frac{1}{3})\cdot \frac{3}{2}$となります。$x-1,x$の2か所に物がない場合は、$dp[i]=(1+dp[i\ \scriptsize clear\normalsize(x+1)]\cdot \frac{1}{3})\cdot \frac{3}{1}$です。このように$x$のループを回しながら、$i$の値によっては式の変形もしつつ最小値を求める必要があります。