きろく

問題 解法 解答 問題 atcoder.jp 解法 dp(i, j) := i 枚目まで操作し j 枚表のときの，表が裏より多くなる確率 と定義する．このとき， dp(i, j) = dp(i - 1, j + 1) * p_(i - 1) + dp(i - 1, j) * (1 - p_(i - 1)) と漸化式が立つ．状態数 O(N^2)，遷移 O(1) となり O(N^2)． 解答 atcoder.jp 確率漸化式を解かせるだけ．