Educational DP Contest
- Educational DP Contest
- 典型的なDPの問題をまとめたコンテスト
- 自分の記事へのリンクまとめとして書く
- ネットを漁ると色々な人が問題・前提知識について解説を書いているので、問題に詰まった場合は適宜ぐぐるといい
- あと、前提知識を知らないと絶対解けないみたいな問題も多いので、DPの仕組みが分かるから全部解けるという訳じゃない
問題まとめと解説リンク
| # | 問題 | 解説 | 前提知識（白抜き） |
|---|---|---|---|
| A | Frog1 | 解説 | 最大最小DP |
| B | Frog 2 | 解説 | 最大最小DP |
| C | Vacation | 解説 | 最大最小DP |
| D | Knapsack 1 | 解説 | ナップサック系DP |
| E | Knapsack 2 | 解説 | ナップサック系DP,状態に持つものを考える |
| F | LCS | 解説 | DP復元、累積minを使った貪欲法 |
| G | Longest Path | 解説 | トポロジカルソート |
| H | Grid 1 | 解説 | 組み合わせDP、mod10^9+7 |
| I | Coins | 解説 | 確率DP |
| J | Sushi | 解説 | 期待値DP |
| K | Stones | 解説 | ゲーム、後退解析（バックトラック） |
| L | Deque | 解説 | ゲーム、ミニマックス法、区間DP |
| M | Candies | 解説 | 貰うDPへ変換後、BITによるDP更新高速化 |
| N | Slimes | 解説 | 区間DP |
| O | Matching | 解説 | bitDP |
| P | Independent Set | 解説 | 木DP |
| Q | Flowers | 解説 | LIS, インラインDP |
| R | Walk | 解説 | 行列累乗によるDP高速化 |
| S | Digit Sum | 解説 | 桁DP |
| T | Permutation | 解説 | BITによるDP更新高速化 |
| U | Grouping | 解説 | O(3^N)でのbitDP |
| V | Subtree | 解説 | 全方位木DP |
| W | Intervals | 解説 | 遅延評価セグメントツリー、とそれを使ったDP更新高速化 |
| X | Tower | 解説 | ソートしてからDP |
| Y | Grid 2 | 解説 | 包除原理 |
| Z | Frog 3 | 解説 | CHTによるDP高速化 |
これを終えたら…
AtCoder Typical DP Contest の勧め
が待っております…
