Educational DP Contest I: Coins
https://atcoder.jp/contests/dp/submissions/10476921
自明に感じる人にとってはfizzbuzzだと思う。
自分は自明に感じなかったので解説ACになってしまった。地頭力がない。
i=coin[i]まで投げた、j=表のコイン数(状態)とする。
[i]は自明なので主に[j]の状態変化を意識してDP遷移を2つ書く。
- dp[i][j - 1] += dp[i - 1][j - 1] * (1.0 - p[i]);
- dp[i][j] += dp[i - 1][j - 1] * p[i];
色々な[i]や[j]の値から遷移できるため、[i]と[j]について全探索して加算すれば網羅できる。とりあえず、事象の確率は足し算と暗記すれば効率良いかと思う。式の形として以下を暗記する。
- rep(i, ...) rep(j, ...) DP[i][j] += DP[i-1][j-1] * Pi; など
なお、初期値は2通りの実装がある。
- 0枚のとき表0枚とDP定義して dp[0][0] = 1とする
- coin[0]が表と裏で dp[0][0] = 1.0 - p[0]; dp[0][1] = p[0];
自分は0-indexでcoin[0]～coin[N-1]と表現したので後者で実装した。
