2022-04-30 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 ほど読んだ。
今日のコミット。
- rust-sandbox 2 commits
- rust-atcoder 1 commit