7K12 blog

猫でも分かるアルゴリズム解説

確率DP

Educational DP Contest I: Coins

f:id:tkr987:20200223223649p:plain

https://atcoder.jp/contests/dp/submissions/10476921

自明に感じる人にとってはfizzbuzzだと思う。

自分は自明に感じなかったので解説ACになってしまった。地頭力がない。

f:id:tkr987:20200302185515p:plain

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]と表現したので後者で実装した。