Atcoder トレーニング

Atcoder 初中級者が解くべき過去問精選100問

No	contest/problem	category	remark	ans
1	ITP1-7/B	全探索:全列挙		ruby, kotlin
2	ABC106/B	全探索:全列挙		ruby, kotlin
3	ABC122/B	全探索:全列挙	尺取法	ruby, kotlin
-	ABC355/D	全探索:全列挙	尺取法, 余事象	ruby
4	PAKENCAMP-2019-DAY3/C	全探索:全列挙		ruby
5	ABC095/C	全探索:工夫して通り数を減らす全列挙		ruby
6	SUMITRUST2019/D	全探索:工夫して通り数を減らす全列挙		ruby1, ruby2
8	S8PC-6/B	全探索:工夫して通り数を減らす全列挙		ruby
9	JOI2008YO/D	全探索:工夫して通り数を減らす全列挙		ruby
10	ALDS1-5/A	全探索:ビット全探索		ruby
11	ABC128/C	全探索:ビット全探索		ruby
12	ABC002/D	全探索:ビット全探索		ruby
13	JOI2008YO/E	全探索:ビット全探索		ruby
-	ABC354/E	全探索:ビット全探索	後ろから考える	ruby
15	ABC145/C	全探索:順列全探索		ruby
16	ABC150/C	全探索:順列全探索		ruby
17	SLDS1-13/A	全探索:順列全探索	バックトラック法	ruby
18	ALDS1-4/B	二分探索		ruby
19	JOI2009HO/B	二分探索		ruby
20	ABC077/C	二分探索		ruby
21	ABC023/D	二分探索		ruby
23	JOI2008HO/C	二分探索		ruby
24	ALDS1-11/B	深さ優先探索		ruby
26	ABC138/D	深さ優先探索		ruby
27	JOI2009YO/D	深さ優先探索		ruby
-	ABC311/C	深さ優先探索, 閉路		ruby
-	ABC282/D	深さ優先探索, 二部グラフ, 余事象		ruby
-	ABC348/E	深さ優先探索, 木の重心		ruby
-	ABC350/F	深さ優先探索		ruby
28	ALDS1-11/C	幅優先探索		ruby
29	ABC007/C	幅優先探索		ruby
30	JOI2011YO/E	幅優先探索		ruby
34	ALDS1-10/A	動的計画法:ナップザックDP		ruby
35	DPL-1/B	動的計画法:ナップザックDP		ruby
36	DPL-1/C	動的計画法:ナップザックDP		ruby
37	DPL-1/A	動的計画法:ナップザックDP		ruby
38	ALDS1-10/C	動的計画法:ナップザックDP	最長共通部分列(LCS)	ruby
39	JOI2011YO/D	動的計画法:ナップザックDP		ruby
40	JOI2012YO/D	動的計画法:ナップザックDP		ruby
41	JOI2013YO/D	動的計画法:ナップザックDP		ruby
42	JOI2015YO/D	動的計画法:ナップザックDP		ruby
46	ALDS1-10/B	動的計画法:区間DP	連鎖行列積	ruby
47	JOI2015HO/B	動的計画法:区間DP		ruby
48	AOJ-1611	動的計画法:区間DP	ダルマ落とし, バックトラック法	ruby
49	DPL-2/A	動的計画法:bitDP	巡回セールスマン問題	ruby
50	S8PC-1/G	動的計画法:bitDP	巡回セールスマン問題	ruby, kotlin
51	JOI2014YO/D	動的計画法:bitDP		ruby
52	JOI2017YO/D	動的計画法:bitDP		ruby
53	DPL-1/D	動的計画法:その他	最長増加部分列(LIS)	ruby
54	ABC006/D	動的計画法:その他	最長増加部分列(LIS)	ruby
55	ABC134/E	動的計画法:その他	最長増加部分列(LIS)	ruby
-	ABC354/F	動的計画法:その他	最長増加部分列(LIS), 前後を考える	ruby
-	ABC336/E	動的計画法:その他	両端から計算	ruby
-	ABC340/E	動的計画法:その他	フェニック木	ruby
-	ABC216/G	動的計画法:その他	フェニック木	ruby
-	ABC312/G	動的計画法:その他	括弧列の成立条件	ruby
-	ABC350/E	動的計画法:期待値DP	メモ化再帰	ruby
56	GRL-1/A	最短経路問題	ダイクストラ法	ruby
57	JOI2008YO/F	最短経路問題	ダイクストラ法	ruby1, ruby2
59	JOI2014YO/E	最短経路問題	ダイクストラ法, 幅優先探索, 優先度付キュー	ruby
-	ABC305/E	最短経路問題	変形ダイクストラ法, 優先度付キュー	ruby
-	ABC325/E	最短経路問題	ダイクストラ法, 幅優先探索, 二分探索法	ruby
-	ABC222/F	最短経路問題	ダイクストラ法, 幅優先探索, 優先度付キュー, 木の直径	ruby
60	GRL-1/C	最短経路問題	ワーシャルフロイド法	ruby
61	ABC012/D	最短経路問題	ワーシャルフロイド法	ruby
62	ABC079/D	最短経路問題	ワーシャルフロイド法	ruby
64	GRL-2/A	最小全域木	クラスカル法(貪欲法 + Union Find)	ruby
65	JOISC2010/FINALS	最小全域木	クラスカル法(貪欲法 + Union Find)	ruby
-	ABC355/F	最小全域木	Union Find	ruby
-	ABC325/D	貪欲法	優先度付きキュー	ruby
68	NTL-1/A	素因数分解		ruby
-	ABC254/D	素因数分解	平方数	ruby1,ruby2
70	NTL-1/B	高度なべき乗計算		ruby
71	S8PC-1/E	高度なべき乗計算	累積和	ruby
72	ABC034/C	逆元		ruby
73	ABC145/D	逆元		ruby
76	NIKKEI2019-FINAL/A	累積和		ruby
77	JOI2010HO/A	累積和		ruby
78	JOI2011HO/A	累積和:二次元		ruby
78	ABC106/D	累積和:二次元	区間DP	ruby
80	ABC014/C	累積和	二分探索	ruby
-	ABC347/E	累積和	横ではなく縦で考える	ruby
81	ABC014/C	累積和:いもす法		ruby
83	JOI2015HO/A	累積和:いもす法		ruby
-	ABC338/D	累積和:いもす法		ruby
85	DSL-1/A	Union Find		ruby
86	ABC075/C	Union Find	DFS, Low Link	ruby1, ruby2, kotlin1, kotlin2
87	ABC120/D	Union Find		ruby
-	ABC350/D	Union Find	DFS	ruby1, ruby2
88	JOI2008HO	圧縮		ruby
89	JOI2013HO/1	圧縮		ruby
90	S8PC-5/B	その他		ruby
-	ABC353/E	その他	トライ木	ruby
95	ABC149/B	数学的な問題		ruby
96	ABC139/D	数学的な問題		ruby
97	ABC150/D	数学的な問題		ruby
98	SUMITRUST2019/E	数学的な問題		ruby
-	ABC337/E	数学的な問題	ビット	ruby
-	ABC338/E	数学的な問題	スタック	ruby
-	ABC320/B	数学的な問題	回文, manacher	ruby
-	ABC346/E	数学的な問題	後ろから考える	ruby
-	ABC347/C	数学的な問題	条件を変換する	ruby

Educational DP Contest/DPまとめコンテスト

No	problem	category	remark	ans
A	Frog1			ruby, kotlin, ruby
B	Frog2			ruby, kotlin, ruby
C	Vacation			ruby, kotlin, ruby
D	Knapsack1	ナップザックDP		ruby, kotlin, ruby
E	Knapsack2	ナップザックDP		ruby, kotlin
F	LCS		最長共通部分列(LCS), 復元	ruby, kotlin
G	Longest Path		トポロジカルソート	ruby, kotlin
H	Grid 1			ruby, kotlin
I	Coins	確率DP		ruby
J	Sushi	期待値DP	メモ化再帰	ruby, kotlin
K	Stones		ゲーム必勝法	ruby
L	Deque	区間DP	バックトラック法	ruby
M	Candies		累積和	ruby
N	Slimes	区間DP	累積和	ruby
O	Matching	bitDP		ruby
P	Independent Set	木DP		ruby
Q	Flowers		セグメント木	ruby
S	Digit Sum	桁DP		ruby, JS
T	Permutation	挿入DP		ruby
U	Grouping	bitDP		ruby
V	Subtree	全方位木DP	累積積	ruby, kotlin
X	Tower			ruby
Y	Gride 2		包除原理	ruby, kotlin
Z	Frog 3		Convex-Hull Trick(CHT)	ruby

Typical DP Contest

No	problem	category	remark	ans
A	コンテスト			ruby
B	ゲーム		バックトラック法	ruby
D	サイコロ			ruby
E	数	桁DP		ruby
F	準急			ruby
G	辞書順			ruby