https://atcoder.jp/contests/dp/tasks/dp_l 前提知識 ミニマックス法 区間DP 解説 https://atcoder.jp/contests/dp/submissions/3948451問題設定がミニマックス法に適しているので適用する。 DPコンテストなのだが、区間DPなので、メモ化再帰で書いている。…

https://atcoder.jp/contests/dp/tasks/dp_k 前提知識 後退解析 解説 https://atcoder.jp/contests/dp/submissions/3948285ゲーム問題のテクとして後退解析がある。 この後退解析をDPっぽくやる手法がある。 dp[k] := k個の石からなる山で先手が勝ち状態か(=…

https://atcoder.jp/contests/dp/tasks/dp_j 前提知識 期待値DP 解説 https://atcoder.jp/contests/dp/submissions/3963610もし考え方違ってたら指摘ください…期待値DPをする。 何番目の寿司かということは特に関係なく、残っている個数毎に集計して問題ない…

https://atcoder.jp/contests/dp/tasks/dp_i 前提知識 確率DP 解説 https://atcoder.jp/contests/dp/submissions/3947967確率DPをする。 dp[i][omote] := i枚のコインを投げて表の枚数がomoteとなる確率 uraを保持しなくてもいいのか？という問題があるが、u…