Typical DP Contest J - ボール - ツバサの備忘録

解法

bitDPです。
期待値の考え方については、こちらの問題のおかげですんなりいきました。

$dp[S] =$ 座標においてある物の状態が $S$ である場合に、そこから全ての物を倒すまでに投げるボールの回数の期待値
とします。座標は0~15までしかないので、このようなことができます。座標 $x$ に物が存在するとき、右から $x+1$ 番目のビットに1を立てます。すると、この状態は $2^{x}$ で表現することができます。
さて、初期状態は $dp[0] = 0$ となります。
ある状態 $S$ の際にボールを $x$ めがけて投げると、 $x-1,x,x+1$ のどこかに物が存在していれば、倒すことができます。確率はすべて $1/3$ なので、座標 $x$ にボールが落ちたときに $S$ から $S_{x}$ に遷移すると仮定すると、 $dp[S]$ は次のように表現することができます。
$dp[S] = \frac{1}{3} (dp[S_{x-1}] + dp[S_{x}] + dp[S_{x+1}]) + 1$
式変形すると、次のようになります。
$3dp[S] = dp[S_{x-1}] + dp[S_{x}] + dp[S_{x+1}] + 3$
さて、これを再帰なりなんなりを用いて、全ての $x$ について計算した上で最小値を求めればいいのですが、注意が必要です。
$S_x$ が、実は $S$ と同じ状態になる可能性があります。 $x$ に物が存在しなかった場合です。
例えば、 $x-1$ と $x+1$ には物が存在して、 $x$ には物が存在しなかった場合は、
$3dp[S] = dp[S_{x-1}] + dp[S] + dp[S_{x+1}] + 3$
となります。
これは、式変形をさらに行い、
$2dp[S] = dp[S_{x-1}] + dp[S_{x+1}] + 3$
とすることができます。
また、 $x-1,x,x+1$ のどの場所にも物が存在しなかった場合、この式を適用することはできず、またそもそもこれが最適解になることはありえない(1回分無駄うちしていることになります)ので、スルーすることに注意しましょう。
あとは、このDPをうまく実装して、全ての $x$ に対しての計算を行い、最小値を求めていけば、答えを求めることができます。