概要
$O(HW^22^W)$ 時間で解ける方法を説明します。
解法
$1$ 行目から順に計算します。$1$ 列目から順に計算します。直前 $W$ マスの「状態」を持ちながら DP の計算を進めていく典型テクニックです（参考：アリ本 p.179）。
また、計算対象は期待値です。これは、各人が挙手する確率の総和なので、
- DP では、「状態」ごとの確率を持つ
- 各人に対して挙手確率を計算し、答に加算していく
という方針で考えます。
一方この問題では、ある人が挙手するかどうかには、自身の右の人の挙手状況が関係してきます。したがって、この計算順に従うと、その時点では挙手するかどうかを決められません。この部分に上手く対応しましょう。
ある人が最終的に挙手する場合、次のどちらかが成り立ちます。
- DP の計算順で自分の手前だけを見て、挙手することが確定する
- DP の計算順で自分の後ろ側の人間の影響で、挙手することが確定する
後者の場合については、ひとまず挙手判定を保留しておきます。そして、挙手が確定した瞬間に答に計上するようにします。つまり
- ある人が、DPの計算順で、自分の手前だけを見て挙手することが確定したとする
- その時点で、挙手判定を保留中の人が $n$ 人居るならば、その $n$ 人分の確率をまとめて答に計上する
という計算方法をとります。DP の状態としては、
- 直前 $W$ 人の、その時点までで確定している挙手状況
- 直前に、挙手判定が保留されている人数が何人いるか
という、$W\cdot 2^W$ 状態を持ちます。以上を実装すれば、$O(HW^2\cdot 2^W)$ 時間の解法が得られます。
