chuka231's blog: Dynamic Problems list in AtCoder:

1.Linear DP / １次元状態DP
https://atcoder.jp/contests/abc004/tasks/abc004_4
https://atcoder.jp/contests/abc104/tasks/abc104_d
https://atcoder.jp/contests/abc162/tasks/abc162_f

2.Knapsack&Index DP / ナップサック・インデックスDP
https://atcoder.jp/contests/arc042/tasks/arc042_c
https://atcoder.jp/contests/abc159/tasks/abc159_f
https://atcoder.jp/contests/abc032/tasks/abc032_d
https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_d

https://atcoder.jp/contests/arc057/tasks/arc057_b

https://atcoder.jp/contests/agc020/tasks/agc020_c
https://atcoder.jp/contests/abc153/tasks/abc153_e

https://atcoder.jp/contests/abc145/tasks/abc145_e

https://atcoder.jp/contests/abc054/tasks/abc054_d

https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_d

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_b

https://atcoder.jp/contests/dp/tasks/dp_d

https://atcoder.jp/contests/dp/tasks/dp_e

https://atcoder.jp/contests/dp/tasks/dp_m

https://atcoder.jp/contests/dp/tasks/dp_x

https://atcoder.jp/contests/tdpc/tasks/tdpc_knapsack

https://atcoder.jp/contests/joi2012yo/tasks/joi2012yo_c

https://atcoder.jp/contests/maximum-cup-2018/tasks/maximum_cup_2018_d

https://atcoder.jp/contests/joi2011ho/tasks/joi2011ho2

F - Limited Xor Subset (atcoder.jp)

F - Potion (atcoder.jp) (mod)

B - IOI饅頭（IOI Manju） (atcoder.jp)

3.Multi-dimension / DP多次元状態DP
https://atcoder.jp/contests/abc145/tasks/abc145_f
https://atcoder.jp/contests/arc067/tasks/arc067_c
https://atcoder.jp/contests/tenka1-2019-beginner/tasks/tenka1_2019_d

https://atcoder.jp/contests/abc008/tasks/abc008_4

https://atcoder.jp/contests/abc082/tasks/arc087_b

https://atcoder.jp/contests/abc113/tasks/abc113_d

https://atcoder.jp/contests/joi2013yo/tasks/joi2013yo_d

https://atcoder.jp/contests/joi2011yo/tasks/joi2011yo_d

https://atcoder.jp/contests/joi2015yo/tasks/joi2015yo_d

https://atcoder.jp/contests/joi2012yo/tasks/joi2012yo_d

https://atcoder.jp/contests/dp/tasks/dp_c

https://atcoder.jp/contests/indeednow-finala-open/tasks/indeednow_2015_finala_c

https://atcoder.jp/contests/tdpc/tasks/tdpc_semiexp

https://atcoder.jp/contests/tdpc/tasks/tdpc_cat

https://atcoder.jp/contests/tdpc/tasks/tdpc_game

https://atcoder.jp/contests/past202004-open/tasks/past202004_k (*)

https://atcoder.jp/contests/pakencamp-2019-day3/tasks/pakencamp_2019_day3_d

https://atcoder.jp/contests/wupc2012/tasks/wupc2012_4

https://atcoder.jp/contests/joi2013ho/tasks/joi2013ho2

G - 友達以上恋人以下 (atcoder.jp)

E - Union (atcoder.jp)

D - テンキー (Tenkey) (atcoder.jp)

D - Friction (atcoder.jp)

C - ビーム (atcoder.jp) (Manhattan Distance)

nile - ナイルドットコム (Nile.Com) (atcoder.jp)

4.Interval DP / 区間DP
https://atcoder.jp/contests/agc021/tasks

https://atcoder.jp/contests/dp/tasks/dp_l

https://atcoder.jp/contests/dp/tasks/dp_n

B - ケーキの切り分け２ (Cake 2) (atcoder.jp)

B - Three Coins (atcoder.jp)

5.bit DP / ビットDP
https://atcoder.jp/contests/arc056/tasks/arc056_c

https://atcoder.jp/contests/abc142/tasks/abc142_e

https://atcoder.jp/contests/abc041/tasks/abc041_d

https://atcoder.jp/contests/keyence2020/tasks/keyence2020_d

https://atcoder.jp/contests/tenka1-2014-quala/tasks/tenka1_2014_qualA_c

https://atcoder.jp/contests/past201912-open/tasks/past201912_i
https://atcoder.jp/contests/dp/tasks/dp_o

https://atcoder.jp/contests/dp/tasks/dp_u

https://atcoder.jp/contests/joi2014yo/tasks/joi2014yo_d

https://atcoder.jp/contests/joi2017yo/tasks/joi2017yo_d

E - Traveling Salesman among Aerial Cities (atcoder.jp)

G - Revenge of Traveling Salesman Problem (atcoder.jp)

E - Magical Ornament (atcoder.jp)

D - ディスクの節約 (atcoder.jp)

G - Teishoku (atcoder.jp)

F - Coprime Present (atcoder.jp)

E - Permutation (atcoder.jp)

6.Digit DP / 桁DP
https://atcoder.jp/contests/abc007/tasks/abc007_4
https://atcoder.jp/contests/dp/tasks/dp_s
https://atcoder.jp/contests/code-formula-2014-qualb/tasks/code_formula_2014_qualB_d

https://atcoder.jp/contests/arc052/tasks/arc052_d

https://atcoder.jp/contests/abc138/tasks/abc138_f

https://atcoder.jp/contests/code-festival-2014-quala/tasks/code_festival_qualA_d

https://atcoder.jp/contests/abc155/tasks/abc155_e

https://atcoder.jp/contests/dp/tasks/dp_s

https://atcoder.jp/contests/tdpc/tasks/tdpc_number

C - 半分 (atcoder.jp)

F - Valid payments (atcoder.jp)

F - Digits Paradise in Hexadecimal (atcoder.jp)

E - Digit Products (atcoder.jp)

7.DP on Trees / 木DP
- Simple
https://atcoder.jp/contests/arc028/tasks/arc028_3

https://atcoder.jp/contests/apc001/tasks/apc001_e

https://atcoder.jp/contests/agc010/tasks/agc010_c

https://atcoder.jp/contests/agc009/tasks/agc009_b

https://atcoder.jp/contests/dp/tasks/dp_p

https://atcoder.jp/contests/tdpc/tasks/tdpc_tree

E - Peddler (atcoder.jp)

C - DFS Game (atcoder.jp)

D - Teleporter (atcoder.jp)

committee - 委員会 (Committee) (atcoder.jp)

Problem - E - Codeforces (Merge technique)

- Square DP on Tree
https://atcoder.jp/contests/discovery2016-final/tasks/discovery_2016_final_c
https://atcoder.jp/contests/arc083/tasks/arc083_c

-All-round DP on Tree
https://atcoder.jp/contests/abc160/tasks/abc160_f
https://atcoder.jp/contests/dp/tasks/dp_v

https://atcoder.jp/contests/tdpc/tasks/tdpc_eel

8.Matrix Power / 行列累乗
https://atcoder.jp/contests/abc009/tasks/abc009_4
https://atcoder.jp/contests/dp/tasks/dp_r

https://atcoder.jp/contests/tdpc/tasks/tdpc_fibonacci

https://atcoder.jp/contests/tdpc/tasks/tdpc_house

D - DISCO! (atcoder.jp)

9.String DP / 文字列DP
https://atcoder.jp/contests/arc081/tasks/arc081_c
https://atcoder.jp/contests/tdpc/tasks/tdpc_lexicographical
https://atcoder.jp/contests/code-festival-2017-qualc/tasks/code_festival_2017_qualc_d

https://atcoder.jp/contests/tdpc/tasks/tdpc_string

https://atcoder.jp/contests/tdpc/tasks/tdpc_concatenation

https://atcoder.jp/contests/tdpc/tasks/tdpc_iwi

A - YahooYahooYahoo (atcoder.jp)

10.Probability DP / 確率DP

https://atcoder.jp/contests/dp/tasks/dp_i

https://atcoder.jp/contests/tdpc/tasks/tdpc_dice

https://atcoder.jp/contests/tdpc/tasks/tdpc_tournament

11.Expectation DP / 期待値DP
https://atcoder.jp/contests/dp/tasks/dp_j

https://atcoder.jp/contests/tdpc/tasks/tdpc_ball

D - increment of coins (atcoder.jp)

D - 無刻印キーボード (atcoder.jp)

F - Fork in the Road (atcoder.jp)

F - Sugoroku2 (atcoder.jp)

C - ソーシャルゲーム (atcoder.jp)

12.Classic DP / 典型的DP
-LIS:最長増加部分列
https://atcoder.jp/contests/abc006/tasks/abc006_4
https://atcoder.jp/contests/abc038/tasks/abc038_d

https://atcoder.jp/contests/tdpc/tasks/tdpc_target

https://atcoder.jp/contests/joisc2007/tasks/joisc2007_buildi

L - 長方形 β (atcoder.jp)

F - LIS on Tree (atcoder.jp)

-LCS:最長共通部分列

https://atcoder.jp/contests/dp/tasks/dp_f

https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_a

https://atcoder.jp/contests/joi2008ho/tasks/joi2008ho_b

E - Sequence Matching (atcoder.jp)

E - Common Subsequence (atcoder.jp)

-Cadane's Algorithm (Consecutive SubArray):部分和

-Hashmap (Consecutive SubArray):部分和

-Brackets Editing: 括弧対応

B - 天下一魔力発電 (atcoder.jp)

-2D Grid Traversal / グリッド探索

https://atcoder.jp/contests/abc175/tasks/abc175_e

https://atcoder.jp/contests/abc147/tasks/abc147_e

https://atcoder.jp/contests/agc046/tasks/agc046_b

https://atcoder.jp/contests/dp/tasks/dp_h

https://atcoder.jp/contests/tdpc/tasks/tdpc_grid

https://atcoder.jp/contests/joi2007yo/tasks/joi2007yo_f

https://atcoder.jp/contests/kupc2018/tasks/kupc2018_b

https://atcoder.jp/contests/joi2010yo/tasks/joi2010yo_e

E - Queen on Grid (atcoder.jp)

C - Infinite Grid (atcoder.jp)

C - Robot on Grid (atcoder.jp)

E - 森林伐採（Deforestation） (atcoder.jp) (Dijkstra like)

- Cumulative Sum / 累積和

13.SOS DP / 耳DP
https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d

14. DP + Alpha (Tricks/Data Structures)
https://atcoder.jp/contests/abc017/tasks/abc017_4
https://atcoder.jp/contests/abc158/tasks/abc158_f
https://atcoder.jp/contests/abc056/tasks/arc070_b
https://atcoder.jp/contests/abc132/tasks/abc132_f
https://atcoder.jp/contests/code-festival-2014-morning-middle/tasks/code_festival_morning_med_d
https://atcoder.jp/contests/arc097/tasks/arc097_c
https://atcoder.jp/contests/abc146/tasks/abc146_f

https://atcoder.jp/contests/dp/tasks/dp_q (BIT)

https://atcoder.jp/contests/dp/tasks/dp_z (CHull)

D - Leaping Tak (atcoder.jp) (imos)

B - Numbers on Papers (atcoder.jp) (PrefixSum, Lower_Bound)

D - Number of Multisets (atcoder.jp)

stairs - 階段 (Stairs) (atcoder.jp) (Lower_Bound)

D - Multiset Mean (atcoder.jp) (Mean Convert)

D - Shortest Path on a Line (atcoder.jp) (Segment Tree)

C - 蛍光灯 (atcoder.jp) (Segment Tree)

E - イルミネーション (Illumination) (atcoder.jp) (Imos, Multiset, Segment Tree)

15. Both Ends DP / 両端DP
https://atcoder.jp/contests/abc163/tasks/abc163_e

E - Traveler (atcoder.jp)

16.Insertion DP / 挿入DP
https://atcoder.jp/contests/dp/tasks/dp_t

17.Graph DP / グラフ関連

https://atcoder.jp/contests/agc012/tasks/agc012_b (Bubble DP)

https://atcoder.jp/contests/dp/tasks/dp_g (Longest Path)

https://atcoder.jp/contests/tdpc/tasks/tdpc_graph

E - Independence (atcoder.jp)

I - 避難計画 (atcoder.jp)

18.Combinatorics / 数え上げ
https://atcoder.jp/contests/dp/tasks/dp_y

F - チーム分け (atcoder.jp)

C - Kill/Death (atcoder.jp) (Partition Number)

E - LEQ and NEQ (atcoder.jp) (包除原理)

19.Inline DP / インラインDP

https://atcoder.jp/contests/dp/tasks/dp_w (Seg)

20.Memoization / メモ化再帰

E - 尾根 (Ridge) (atcoder.jp)

21. Binary Lifting / ダブリング

22. Math / 数学

23. Monge-DP

24. Alien-DP

25. Game Theory

D - Game in Momotetsu World (atcoder.jp)

chuka231's blog

Friday, July 3, 2020

Dynamic Problems list in AtCoder:

No comments:

Post a Comment