No.309

各行は1つ前の行にしか依存しないので, 前の行から順に計算していく.

$i$ 行目の計算であるが, $i-1$ 行目で挙手状況と $i$ 行目の知識状況でループし, 状況ごとに $i$ 行目の挙手状況を求める.

挙手状況とはその行で誰が挙手しているかどうかの状態であり, 知識状況とはその行で誰が倉敷が何県か知っているかどうかの状態である. これはビットで表現する.

$i-1$ 行目の挙手状況になる確率は DP で計算でき, $i$ 行目の知識状況になる確率は知識状況の各人のビットと $P_{i,j}$ から求められるので, ここから $i$ 行目の挙手状況ごとの確率を求めることができる.

$i-1$ 行目の挙手状況と $i$ 行目の知識状況から $i$ 行目の挙手状況を求めるには, $i$ 行目の各人の挙手状態を伝播させる必要があり $O(C)$ の計算量が必要なため, 全体で $O(CR4^C)$ の計算量が必要となる.

そこで前処理を行う.

ある行の各人の(挙手状態が伝播する前の)前の人の挙手状態を考慮に入れたポイントは 0〜5 ポイントとなる. 挙手するまでのポイントを考えると 0〜4 ポイントであるが, 挙手するまで3ポイントか4ポイント必要な場合はどちらも挙手しないことが決まっているので, 挙手するまでのポイントは3ポイントとしてまとめる.

ここで各人の残りポイントの状態を行でまとめて行の残りポイント状況として $2C$ ビットで表現する. この行の残りポイント状況から挙手状況をあらかじめ計算しておく. この前処理の計算量は $O(C4^C)$ である.

そして $i-1$ 行目の挙手状況でまず外側のループをまわす. このとき, $i$ 行目の人がすべて知っている場合の残りポイント状況を求めることができる.

その上で $i$ 行目の知識状況で内側のループをまわす. このとき, 知らない人の残りポイントは3になるので, 外側のループ内で求めた $i$ 行目の人がすべて知っている場合の残りポイント状況から $i$ 行目のポイント状況をビットのOR演算で求めることができる.

こうしてポイント状況が分かれば前処理によって挙手状況が $O(1)$ で求まるので, $i-1$ 行目の挙手状況と $i$ 行目の知識状況から $i$ 行目の挙手状況を求める計算量を $O(1)$ にすることができる.

したがって全体の計算量は $O((R+C)4^C)$ となる.