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
-	ABC366/E	全探索:全列挙	尺取法, マンハッタン距離	ruby
-	ABC229/D	全探索:全列挙	尺取法, 累積和	ruby
-	ABC377/D	全探索:全列挙	尺取法	ruby
-	ABC381/D	全探索:全列挙	尺取法	ruby
-	ABC383/D	全探索:全列挙	尺取法, 素数, 約数列挙, エラトステネスの篩	ruby
-	ABC384/D	全探索:全列挙	尺取法, 累積和, ループ	ruby
-	ABC124/D	全探索:全列挙	尺取法, ランレングス圧縮	ruby
-	ABC416/D	全探索:全列挙	尺取法, 除くものを考える	ruby
-	ABC246/D	全探索:全列挙	尺取法	ruby
-	ABC430/C	全探索:全列挙	尺取法, 条件分離	ruby
4	PAKENCAMP-2019-DAY3/C	全探索:全列挙		ruby
-	ABC390/D	全探索:全列挙	ベル数, 深さ優先探索	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
14	S8PC4/B	全探索:ビット全探索		ruby
-	ABC310/D	全探索:ビット全探索	深さ優先探索	ruby
-	ABC354/E	全探索:ビット全探索	後ろから考える	ruby
-	ABC356/C	全探索:ビット全探索		ruby
-	ABC424/D	全探索:ビット全探索	ポップカウント事前計算	ruby
-	ABC359/D	全探索:ビット全探索系		ruby
-	ABC404/D	全探索:ビット全探索系	3進数で全探索	ruby
-	ABC427/C	全探索:ビット全探索	二部グラフの判定	ruby
15	ABC145/C	全探索:順列全探索		ruby
16	ABC150/C	全探索:順列全探索		ruby
17	SLDS1-13/A	全探索:順列全探索	バックトラック法	ruby
-	ABC332/D	全探索:順列全探索	幅優先探索	ruby
18	ALDS1-4/B	二分探索		ruby
19	JOI2009HO/B	二分探索		ruby
20	ABC077/C	二分探索		ruby
21	ABC023/D	二分探索		ruby
22	ARC054/B	二分探索	黄金分割探索, 微分	ruby1, ruby2
23	JOI2008HO/C	二分探索		ruby
-	ABC397/D	二分探索		ruby
-	NIKKEI2019/C	二分探索	マンハッタン距離の総和を最小値は、中央値を使う	ruby
-	ABC364/D	二分探索	さらに二分探索	ruby
-	ABC217/D	二分探索	sorted_setの代わり, セグメント木, unshift	ruby1, ruby2
-	ABC388/E	二分探索	決め打ち二分探索	ruby
-	ABC267/E	二分探索	決め打ち二分探索, 最小値の最大化	ruby
-	ABC374/E	二分探索	決め打ち二分探索, 最小値の最大化	ruby
-	ABC389/E	二分探索	決め打ち二分探索, 最小値の最大化	ruby
-	ABC390/E	二分探索	決め打ち二分探索, 最小値の最大化	ruby
-	ABC270/E	二分探索	決め打ち二分探索	ruby
-	ABC400/C	二分探索	平方根を求める	ruby
24	ALDS1-11/B	深さ優先探索		ruby
25	1160	深さ優先探索		ruby
26	ABC138/D	深さ優先探索		ruby
27	JOI2009YO/D	深さ優先探索		ruby
-	ABC311/C	深さ優先探索, 閉路		ruby
-	ABC282/D	深さ優先探索, 二部グラフ, 余事象		ruby
-	ABC398/E	深さ優先探索, 二部グラフ	奇閉路がない	ruby
-	ABC348/E	深さ優先探索, 木の重心, 全方位木DP		ruby1, ruby2
-	ABC350/F	深さ優先探索		ruby
-	ABC357/C	深さ優先探索	3進法	ruby
-	ABC213/D	深さ優先探索	オイラーツアー	ruby
-	ABC239/E	深さ優先探索	オイラーツアー, 必要数分のみ保持	ruby
-	ABC220/F	深さ優先探索	オイラーツアー, 幅優先探索, 始点の移動	ruby
-	ABC382/D	深さ優先探索	枝切り	ruby
28	ALDS1-11/C	幅優先探索		ruby
29	ABC007/C	幅優先探索		ruby
30	JOI2011YO/E	幅優先探索		ruby
-	ABC428/E	幅優先探索	木の直径, 両端は全ての頂点の最遠距離	ruby
-	ABC213/E	幅優先探索	01-BFS	ruby
-	ABC400/D	幅優先探索	01-BFS	ruby
-	ABC431/E	幅優先探索	01-BFS	ruby
-	ABC387/D	幅優先探索	パリティ, 状態管理	ruby
33	ABC088/D	幅優先探索		ruby
-	ABC405/D	幅優先探索	多始点BFS	ruby
-	ABC425/D	幅優先探索	同時更新, 多始点BFS	ruby
-	ABC429/D	幅優先探索	多始点BFS	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	動的計画法:ナップサック		ruby
40	JOI2012YO/D	動的計画法:ナップサックDP		ruby
41	JOI2013YO/D	動的計画法:ナップサックDP		ruby
42	JOI2015YO/D	動的計画法:ナップサックDP		ruby
43	PAKENCAMP2019DAY3/D	動的計画法:ナップサックDP		ruby
-	ABC364/E	動的計画法:ナップサックDP	キーと値を入れ替える	ruby
-	ABC410/E	動的計画法:ナップサックDP	キーと値を入れ替える	ruby
-	DPL-1/G	動的計画法:ナップサックDP	個数制限付きナップサックDP	ruby, kotlin
-	DPL-1/I	動的計画法:ナップサックDP	個数制限付きナップサックDP, 貪欲法, スライド最小値	ruby, kotlin
-	ABC431/D	動的計画法:ナップサックDP	次元を下げる	ruby
46	ALDS1-10/B	動的計画法:区間DP	連鎖行列積	ruby
47	JOI2015HO/B	動的計画法:区間DP		ruby
48	AOJ-1611	動的計画法:区間DP	ダルマ落とし, バックトラック法	ruby
49	DPL-2/A	動的計画法:ビットDP	巡回セールスマン問題	ruby
50	S8PC-1/G	動的計画法:ビットDP	巡回セールスマン問題	ruby, kotlin
51	JOI2014YO/D	動的計画法:ビットDP		ruby
52	JOI2017YO/D	動的計画法:ビットDP		ruby
-	ABC215/E	動的計画法:ビットDP		ruby
-	ABC326/E	動的計画法:期待値DP	累積和	ruby
-	ABC350/E	動的計画法:期待値DP	メモ化再帰	ruby
-	ABC402/E	動的計画法:期待値DP	ビットDP	ruby
-	ABC184/D	動的計画法:期待値DP	ビットDP	ruby
-	ABC410/D	動的計画法:期待値DP	ビットDP	ruby
-	ABC387/C	動的計画法:桁DP		ruby
-	ABC394/F	動的計画法:木DP		ruby
-	ABC397/E	動的計画法:木DP		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	動的計画法:その他	フェニック木, Fenwick Tree, BIT	ruby
-	ABC216/G	動的計画法:その他	フェニック木, Fenwick Tree, BIT	ruby
-	ABC389/F	動的計画法:その他	フェニック木, Fenwick Tree, BIT	ruby
-	ABC392/F	動的計画法:その他	フェニック木, Fenwick Tree, BIT, 二分探索法, 後ろから考える	ruby
-	ABC392/F	動的計画法:その他	フェニック木, Fenwick Tree, BIT, 二分探索法, 座標圧縮	ruby
-	ABC312/D	動的計画法:その他	括弧列の成立条件	ruby
-	ABC357/E	動的計画法:その他	強連結成分分解	ruby, JS
-	ABC358/E	動的計画法:その他	組み合わせ, 逆元	ruby
-	ABC425/E	動的計画法:その他	組み合わせ, パスカルの三角形	ruby
-	ABC362/E	動的計画法:その他	等差数列	ruby
-	ABC375/E	動的計画法:その他	ループを１つ減らす	ruby
-	ABC403/D	動的計画法:その他		ruby
-	ABC417/D	動的計画法:その他	累積和, 二分探索法, 後ろから考える	ruby
-	ABC419/D	動的計画法:その他	長さLの連続部分列の総和がMの倍数	ruby
-	ABC427/D	動的計画法:その他	ゲーム必勝法, 後ろから考える	ruby
56	GRL-1/A	最短経路問題	ダイクストラ法	ruby
57	JOI2008YO/F	最短経路問題	ダイクストラ法	ruby1, ruby2
59	JOI2014YO/E	最短経路問題	ダイクストラ法, 幅優先探索, 優先度付キュー	ruby
-	ABC305/E	最短経路問題	変形ダイクストラ法, 優先度付キュー	ruby
-	ABC325/E	最短経路問題	ダイクストラ法, 幅優先探索, 二分探索法	ruby
-	ABC222/F	最短経路問題	ダイクストラ法, 幅優先探索, 優先度付キュー, 木の直径	ruby
-	ABC361/E	最短経路問題	ダイクストラ法, 幅優先探索, 優先度付キュー, 木の直径	ruby
-	ABC395/E	最短経路問題	ダイクストラ法, 幅優先探索, 優先度付キュー	ruby
-	ABC217/E	優先度付キュー	二重構造	ruby
-	ABC234/D	優先度付キュー	データ構造	ruby1, ruby2
-	ABC384/E	優先度付キュー		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
67	ABC065/D	最小全域木	クラスカル法(貪欲法 + Union Find), XとYを別々に考える	ruby
-	ABC383/E	最小全域木	クラスカル法(貪欲法 + Union Find)	ruby
-	ABC355/F	最小全域木	Union Find	ruby
-	ABC214/D	最小全域木	Union Find, 主客転倒	ruby
-	ABC325/D	貪欲法	優先度付きキュー	ruby
-	ABC230/D	貪欲法	区間スケジューリング問題	ruby
68	NTL-1/A	素因数分解		ruby
-	ABC254/D	素因数分解	平方数	ruby1,ruby2
-	ABC400/E	素因数分解	平方数	ruby
69	ABC084/D	素因数分解	平方数, 累積和	ruby
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
-	ABC233/D	累積和		ruby
-	ABC308/E	累積和	MEX, 3つ組は真ん中固定, セグメント木	ruby
-	ABC405/C	累積和		ruby
-	ABC418/C	累積和	面積	ruby
78	JOI2011HO/A	累積和:二次元		ruby
79	ABC106/D	累積和:二次元	区間DP	ruby
-	ABC366/D	累積和:三次元		ruby
80	GIGACODE2019/D	累積和	二分探索	ruby
-	ABC347/E	累積和	横ではなく縦で考える	ruby
-	ABC356/E	累積和	答えから考える	ruby
-	ABC375/D	累積和	3つ組は真ん中固定	ruby1, ruby2
81	ABC014/C	累積和:いもす法		ruby
83	JOI2015HO/A	累積和:いもす法		ruby
-	ABC338/D	累積和:いもす法		ruby
-	ABC221/D	累積和:いもす法		ruby
-	ABC388/D	累積和:いもす法		ruby
-	ABC188/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
-	ABC372/E	Union Find	必要数分のみ保持	ruby
-	CODE_THANKS_FESTIVAL_2017_OPEN/H	Union Find	部分永続Union Find	ruby1, ruby2
-	ABC404/C	Union Find	サイクルグラフ	ruby
88	JOI2008HO/A	圧縮		ruby
89	JOI2013HO/1	圧縮		ruby
90	S8PC-5/B	その他		ruby
-	ABC353/E	その他	トライ木, tri木, Rolling Hash	ruby1, ruby2
-	ABC430/E	その他	z-algorithm, Rolling Hash	ruby1, ruby2
-	ABC189/C	その他	スタック, ヒストグラム最大長方形	ruby
-	DPL-3/B	その他	スタック, ヒストグラム最大長方形	ruby
-	ABC359/E	その他	スタック, ヒストグラム最大長方形	ruby
-	ABC372/D	その他	スタック, ヒストグラム最大長方形	ruby
-	ABC379/F	その他	スタック, ヒストグラム最大長方形, フェニック木, 二分探索法	ruby1, ruby2
-	ABC352/D	その他	スライド最小, スライド最大, dequeue	ruby
-	ABC349/D	その他	セグメント木の考え方, 深さ優先探索	ruby1,ruby2
-	ABC302/E	その他	Set	ruby
-	ABC402/C	その他	Set, 後ろから考える	ruby1, ruby1
-	ABC393/D	その他	転倒数, マンハッタン距離の総和を最小値は、中央値	ruby1, ruby2
-	ABC403/E	その他	trie木	ruby
-	ABC407/E	その他	括弧列の成立条件, 優先度付きキュー	ruby
-	DSL/F	その他	遅延セグメント木, 区間最小値, 区間更新	ruby
-	DSL/G	その他	遅延セグメント木, 区間和, 区間加算	ruby
-	DSL/H	その他	遅延セグメント木, 区間最小値, 区間加算	ruby
-	DSL/I	その他	遅延セグメント木, 区間和, 区間更新	ruby
-	ABC407/F	その他	カルテジアン木, いもす法, 累積和	ruby
-	ABC422/E	その他	乱択	ruby
-	ABC272/E	その他	オーダーの見積もり	ruby
-	ABC426/D	その他	最長連続区間, ランレングス圧縮	ruby
-	ABC287/E	その他	辞書順	ruby
95	ABC149/B	数学的な問題		ruby
96	ABC139/D	数学的な問題		ruby
97	ABC150/D	数学的な問題		ruby
98	SUMITRUST2019/E	数学的な問題		ruby
100	TENKA12018/D	数学的な問題	完全グラフ	ruby
-	ABC337/E	数学的な問題	ビット	ruby
-	ABC365/E	数学的な問題	ビット, XOR, 累積和	ruby
-	ABC396/E	数学的な問題	ビット, XOR, ビット毎に独立で考える	ruby
-	ABC338/E	数学的な問題	スタック	ruby
-	ABC320/B	数学的な問題	回文, manacher	ruby
-	ABC398/F	数学的な問題	回文, manacher	ruby
-	ABC346/E	数学的な問題	後ろから考える	ruby
-	ABC347/C	数学的な問題	条件を変換する	ruby
-	CHOKUDAI_S001/J	数学的な問題	転倒数	ruby
-	ABC396/F	数学的な問題	転倒数	ruby
-	ABC357/D	数学的な問題	等比数列の和の公式, 逆元	ruby
-	ABC367/F	数学的な問題	Schwartz–Zippel lemma, Zobrist Hash	ruby
-	ABC377/E	数学的な問題	ダブリング, 鳩の巣原理, グラフ, 循環, 周期	ruby
-	ABC379/E	数学的な問題	下の桁から確定してく, 巨大な桁数	ruby
-	ABC381/C	数学的な問題	ランレングス圧縮	ruby1, ruby2
-	ABC393/E	数学的な問題	約数列挙	ruby
-	ABC398/D	数学的な問題	全体移動は座標移動, 相対位置	ruby
-	ABC402/D	数学的な問題	余事象, 平行条件, 中点	ruby
-	ABC405/E	数学的な問題	フェルマーの小定理, 基準となるものを決める	ruby
-	ABC405/E	数学的な問題	フェルマーの小定理, 基準となるものを決める, 累積和, ヴァンデルモンドの畳み込み	ruby
-	ABC164/D	数学的な問題	累積和, 互いに素, 剰余	ruby
-	ABC230/E	数学的な問題	整数, 反比例	ruby
-	ABC428/D	数学的な問題	整数, 平方数, 1桁ずつ計算	ruby

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

No	problem	category	remark	ans
A	Frog1			ruby, kotlin, JS
B	Frog2			ruby, kotlin, JS
C	Vacation			ruby, kotlin, JS
D	Knapsack1	ナップサックDP		ruby, kotlin, JS
E	Knapsack2	ナップサックDP	キーと値を入れ替える	ruby, kotlin
F	LCS		最長共通部分列(LCS), DP復元	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