はまやんはまやんはまやん

hamayanhamayan's blog

Educational DP Contestの勧め

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 の勧め
が待っております…