Wed Dec 2 16:30:44 JST 2015

問題

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

解答

手を上げてるかの確率をDPっぽく計算することにする. 自分の隣と前の行にしか依存しないので、頭の行から処理していけばいいはず. 一つの行についての処理だけ慎重に行う (手を挙げる行為が伝播する).

ダミーの行として、倉敷を0%の確率で知ってる人たちを頭の行に追加しておけば奇麗に書けそう.

初め考えたのは、\(R, C \leq 11\) なので、 今の行と、前の行のありうる可能性は高々 \(2^{22}\) 通り. これを定めてしまえば、その行について、手が上がってるかどうかは確定できる. これを各行について処理しても \(4 \times 10^7\) 時間.

sample3 を手元で行って既に4秒を超えていたので ダメ元だったけど、提出したのが http://yukicoder.me/submissions/62068 で、案の定TLE.

もうちょっと確率をDPでうんたらするんだろうなーと思って、 其々の人のポイントがいくつである確率みたいなのを計算していって

http://yukicoder.me/submissions/62075

全然WA.