https://atcoder.jp/contests/dp/tasks/dp_h 前提知識 組み合わせ系の動的計画法 解説 https://atcoder.jp/contests/dp/submissions/3947874mod10^9+7の数え上げはDPの可能性が高いし、マス移動でDPを使う問題は死ぬほどみたせいか、DPの定義が自然と出てく…

https://atcoder.jp/contests/dp/tasks/dp_g 前提知識 トポロジカルソート 解説 https://atcoder.jp/contests/dp/submissions/3947799トポロジカルソートを知っていれば一瞬だが、知らないと解けない。 DPというのは「ある状態を処理するときは、その状態に…

https://atcoder.jp/contests/dp/tasks/dp_f 前提知識 動的計画法テク「遷移が多い場合は貪欲法を使うことで最適であろう遷移を絞ることができる」 解説 https://atcoder.jp/contests/dp/submissions/3947645恐らく想定解ではないライブラリによる筋肉解法で…

https://atcoder.jp/contests/dp/tasks/dp_e 前提知識 動的計画法 解説 https://atcoder.jp/contests/dp/submissions/3946715ナップサック問題のよくある変形。 状態として保持する物を変形して解く。 というより、解く流れとしては、1. dp[N][W]では状態数…

https://atcoder.jp/contests/dp/tasks/dp_d 前提知識 動的計画法 解説 https://atcoder.jp/contests/dp/submissions/3946683一般的なナップサック問題。 dp[i][tot] := i番目までの商品を入れて、重さの総和がtotである場合の価値の総和の最大値 ナップサッ…

https://atcoder.jp/contests/dp/tasks/dp_c 前提知識 最大最小系の動的計画法 解説 https://atcoder.jp/contests/dp/submissions/3946364DPだという前提で考えると、 dp[i] := i日目の活動を終えたときの幸福度の総和の最大値 というDPが思いつく。 しかし…

https://atcoder.jp/contests/dp/tasks/dp_b 前提知識 最大最小系の動的計画法 解説 https://atcoder.jp/contests/dp/submissions/3946249EDPCのAの強化版であり、同じDPで同じ方針で解く。 dp[i] := i番目の足場にたどり着くためのコストの総和の最小値 最…

https://atcoder.jp/contests/dp/tasks/dp_a 前提知識 最大最小系の動的計画法 解説 https://atcoder.jp/contests/dp/submissions/3946204最小値のDPを書く。 dp[i] := i番目の足場にたどり着くためのコストの総和の最小値 最小値のDPを書く場合はすべての要…