読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Typical DP Contest J - ボール

よくある期待値の問題。

tdpc.contest.atcoder.jp

解法

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 ができる。解説では場合分けをしたが、コードの中ではしていない。

Typical DP Contest J - ボール

この期待値の求め方気に入ってる。