[yukicoder] No.309 シャイな人たち (1)

スポンサーリンク

概要

問題文 →
公式解説 →
自分の提出 →

$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)$ 時間の解法が得られます。

タイトルとURLをコピーしました