EDPC : Educational DP Contest の J, K, L を解いた。
- J - Sushi
https://atcoder.jp/contests/dp/tasks/dp_j
- 提出: https://atcoder.jp/contests/dp/submissions/31380844
- 解説 AC https://kyopro-friends.hatenablog.com/entry/2019/01/12/231000
- 解説を見ながら解いたのだけどたぶんゼロ除算の件を考慮しそびれているのでそのままでは解けない
dp[i][j][k] := 寿司が 1 個置かれている皿が i 皿、 2 個が j 皿、 3 個が k 皿のときの操作回数の期待値と置いてメモ化再帰(1−(0個の皿が選ばれる確率)の部分が0になることの考慮が解説から落ちている
- K - Stones
https://atcoder.jp/contests/dp/tasks/dp_k
- 提出: https://atcoder.jp/contests/dp/submissions/31398338
- 典型考察の「後ろ (ゲーム終了) から調べる」で良い
- 山が 0 のとき手番が来ると負け
- 山が 1 のとき手番が来ると集合に 1 があれば相手を負けに遷移できるので勝ち・なければ負け
- 集合の元だけ山を減らせるので減らせる先に相手を負けにできるものがあれば勝ち
- 山が N のときまで順に勝ち負けを埋めれば勝ち負けが分かる
- L - Deque
https://atcoder.jp/contests/dp/tasks/dp_l
- 提出: https://atcoder.jp/contests/dp/submissions/31398622
- 左右の位置の組ごとに最善の値が決まる
- 左を選ぶ場合・右を選ぶ場合をそれぞれメモ化再帰で良い
今日のコミット。
