bouzuya.hatenablog.com

ぼうずやのにっき

EDPC の I を解いた

EDPC : Educational DP Contest の I を解いた。

  • I - Coins https://atcoder.jp/contests/dp/tasks/dp_i
    • 提出: https://atcoder.jp/contests/dp/tasks/dp_i
    • N <= 2999 なので N^2 でも 9 * 10^6 程度なので dp[N][N] くらい持てる
    • dp[i][j] := i 枚目のコインまでで j 枚表が出る確率 と置く
    • 初期化
      • dp[0][0] = 1 - p_1;
      • dp[0][1] = p_i;
    • 遷移
      • dp[i+1][j] = dp[i][j] + 1 - p_1; 裏が出たとき
      • dp[i+1][j+1] = dp[i][j] + p_i; 表が出たとき
    • 遷移が i -> i + 1 しかないので dp[i][j] ではなく dp[j] で十分

妻の親戚と会う。疲れた。

『ソフトウェアアーキテクチャの基礎』を改めて読んでいる。 1/3 ほど読んだ。

今日のコミット。