Typical DP Contest J - ボール
よくある期待値の問題。
解法
oxoooxox
の状態からすべて倒すまでに投げるボールの個数の期待値を $E[10111010]$ と表すことにする。つまり bitDP をする。
パターン 1：投げた先 3 マスがすべてが埋まっている
v ooo
このときの期待値は
$$ E[111]=\frac{E[011]}{3} + \frac{E[101]}{3} + \frac{E[110]}{3} + 1 $$
パターン 2：投げた先 2 マスが埋まっている
v oxo
このときの期待値は
$$ E[101]=\frac{E[001]}{3} + \frac{E[101]}{3} + \frac{E[100]}{3} + 1 $$
これは式変形すると
$$ E[101]=\frac{3}{2}\left( \frac{E[001]}{3} + \frac{E[100]}{3} + 1 \right) $$
になる。
パターン 3：投げた先 1 マスが埋まっている
v xxo
このときの期待値は
$$ E[001]=\frac{E[001]}{3} + \frac{E[001]}{3} + \frac{E[000]}{3} + 1 $$
これは式変形すると
$$ E[001]=3\left( \frac{E[000]}{3} + 1 \right) $$
以上のパターンを考えれば bitDP ができる。解説では場合分けをしたが、コードの中ではしていない。
この期待値の求め方気に入ってる。
