問題

直線上に並んだターゲット全てにボールを当てるまでの回数の期待値を求める。ボールを狙った座標とその両隣それぞれに1/3の確率でボールが飛んでいく。

考察

$N \leq 16$ なので、dp[s] = (sが1の座標にターゲットが残っているときの期待値)とする。

$x-1, x, x+1$ に向かってボールを投げて、 $x$ にあるターゲットに当たる確率は1/3なので、狙ったターゲットに当たるまでの回数の期待値は $e$ は、

$e = \sum_{k = 1}^{\infty} k \frac{1}{3} (\frac{2}{3})^{k-1} = 3$

また、ターゲットはなるべく左から倒すようにし、最も右のターゲットに当たる最も左の座標を狙う方がよい。