これは何？

競プロ/ 分野別　初中級者が解くべき過去問精選 100 問のC言語による全問解答および解説。

全問題一覧

idx	問題名	難易度(1~5)	単元/comment by @E869120	方針/解答例
1	組み合わせの数	1	全探索/基本問題	全探索
2	AtCoder Beginner Contest 106 B - 105	1	全探索/-	全探索 or 手計算
3	AtCoder Beginner Contest 122 B - ATCoder	1	全探索/-	全探索, skip
4	パ研杯2019 C - カラオケ	2	全探索/免許皆伝問題	全探索
5	AtCoder Beginner Contest 095 C - Half and Half	2	全探索/-	考察
6	三井住友信託銀行プログラミングコンテスト 2019 D - Lucky PIN	2	全探索/-	全探索(要工夫), skip or 累積和
7	JOI 2007 本選 3 - 最古の遺跡	2	全探索/面白い	全探索(要工夫),二次元
8	Square869120Contest #6 B - AtCoder Markets	4	考察/全探索/工夫	全探索(要工夫),中央値
9	JOI 2008 予選 4 - 星座探し	3	全探索/-	全探索(要工夫),二次元
10	ALDS_5_A - 総当たり	1	全探索/基本問題	bit全探索 or DP
11	AtCoder Beginner Contest 128 C - Switches	3	全探索/-	bit全探索,ややこしい
12	AtCoder Beginner Contest 002 D - 派閥	2	全探索/-	bit全探索
13	JOI 2008 予選 5 - おせんべい	2	全探索/茶色コーダーにはやや難	縦に関してbit全探索
14	Square869120Contest #4 B - Buildings are Colorful!	4	全探索/難問	建物数に関してbit全探索
15	AtCoder Beginner Contest 145 C - Average Length	2	全探索/-	順列全探索
16	AtCoder Beginner Contest 150 C - Count Order	2	全探索/-	順列全探索
17	ALDS_13_A - 8 クイーン問題	3	全探索/面白い	順列全探索
18	ALDS_4_B - 二分探索	1	二分探索/基本問題, mapでも解ける	二分探索 or hash(map) or sort -> 線形探索
19	JOI 2009 本選 2 - ピザ	2	二分探索/-	環状は二周確保, 二分探索
20	AtCoder Beginner Contest 077 C - Snuke Festival	3	二分探索/面白い	二分探索(lower/upper bound)、中部を軸に or 二分探索,累積和
21	AtCoder Beginner Contest 023 D - 射撃王	5	二分探索/教育的に良い	解決め打ちで二分検索(lower bound)
22	AtCoder Regular Contest 054 B - ムーアの法則	3	二分探索/微分して二分法	二分法 or 手計算
23	JOI 2008 本選 3 - ダーツ	4	二分探索/チャレンジ問題	解決め打ちで二分検索(upper bound), 半分全列挙
24	ALDS_11_B - 深さ優先探索	1	深さ優先探索/基本問題	stack版DFS or 再帰版DFS
25	AOJ 1160 - 島はいくつある？	2	深さ優先探索/-	複数回DFS or 再帰DFS
26	AtCoder Beginner Contest 138 D - Ki	5	深さ優先探索/-	DFS, 累積和 or BFS, 累積和 or 木DP(再帰)
27	JOI 2009 予選 4 - 薄氷渡り	4	深さ優先探索/再帰関数を使って	再帰DFS(盤面なので)
28	ALDS_11_C - 幅優先探索	1	幅優先探索/基本問題	BFS
29	AtCoder Beginner Contest 007 C - 幅優先探索	2	幅優先探索/-	BFS
30	JOI 2011 予選 5 - チーズ	3	幅優先探索/-	複数回BFS
31	JOI 2012 予選 5 - イルミネーション	4	幅優先探索/実装が少し重い	BFS, 配列の添字に注意
32	AOJ 1166 - 迷図と命ず	4	幅優先探索/実装が少し重い	BFS
33	AtCoder Beginner Contest 088 D - Grid Repainting	3	幅優先探索/免許皆伝問題	BFS
34	ALDS_10_A - フィボナッチ数	1	動的計画法/超基本	DP(漸化式)
35	DPL_1_B - 0,1ナップザック問題	2	動的計画法/基本問題	DP
36	DPL_1_C - ナップザック問題	2	動的計画法/基本問題	インラインDP
37	DPL_1_A - コイン問題	2	動的計画法/基本問題	DP, 「必ず1を含む」を利用
38	ALDS_10_C - 最長共通部分列	3	動的計画法/基本問題	DP
39	JOI 2011 予選 4 - 1 年生	3	動的計画法/-	DP
40	JOI 2012 予選 4 - パスタ	5	動的計画法/-	DP, 三項間漸化式
41	JOI 2013 予選 4 - 暑い日々	4	動的計画法/-	DP, 添字に注意
42	JOI 2015 予選 4 - シルクロード	4	動的計画法/-	DP, 添字に注意
43	パ研杯2019 D - パ研軍旗	4	動的計画法/-	DP
44	AOJ 1167 - ポロック予想	3	動的計画法/-	DP
45	AOJ 2199 - 差分パルス符号変調	4	動的計画法/-	DP
46	ALDS_10_B - 連鎖行列積	3	動的計画法/基本問題	区間DP
47	JOI 2015 本選 2 - ケーキの切り分け 2	4	動的計画法/O(N^2)の区間DP	環状は二周確保,区間DP
48	AOJ 1611 ダルマ落とし	5	動的計画法/O(N^3)の区間DP	下からi個までのダルマについて都度区間DP
49	DPL_2_A - 巡回セールスマン問題	3	動的計画法/基本問題	bit DP
50	Square869120Contest #1 G - Revenge of Traveling Salesman Problem	4	動的計画法/巡回セールスマン問題の類題	bit DP
51	JOI 2014 予選 4 - 部活のスケジュール表	3	動的計画法/一応bitDPとして	bitDP
52	JOI 2017 予選 4 - ぬいぐるみの整理	5	動的計画法/少し難しい	bitDP, 累積和
53	DPL_1_D - 最長増加部分列	3	動的計画法/-	インラインDP, 二分探索 or LIS, 座標圧縮、セグメント木
54	AtCoder Beginner Contest 006 D - トランプ挿入ソート	3	動的計画法/-	53とほぼ同様。stack
55	AtCoder Beginner Contest 134 E - Sequence Decomposing	5	動的計画法/チャレンジ問題	groupの要素数をメンバにしたstack
56	GRL_1_A - 単一始点最短経路	3	ダイクストラ法/-	ダイクストラ+min heap or ベルマンフォード法
57	JOI 2008 予選 6 - 船旅	3	ダイクストラ法/ワーシャルフロイド法でも	ダイクストラ + min heap or ワーシャルフロイド法 or ベルマンフォード法
58	JOI 2016 予選 5 - ゾンビ島	4	ダイクストラ法/幅優先探索も使う。実装重め	BFS, ダイクストラ, min heap
59	JOI 2014 予選 5 - タクシー	5	ダイクストラ法/-	BFS, ダイクストラ, min heap
60	GRL_1_C - 全点対間最短経路	3	ワーシャルフロイド法/基本問題	ワーシャルフロイド法,重みの上限がシビア
61	AtCoder Beginner Contest 012 D - バスと避けられない運命	2	ワーシャルフロイド法/-	ワーシャルフロイド法
62	AtCoder Beginner Contest 079 D - Wall	3	ワーシャルフロイド法/-	2次元をgraphに見立ててワーシャルフロイド法, map
63	AtCoder Beginner Contest 074 D - Restoring Road Network	5	ワーシャルフロイド法/数学的考察が必要で難しいがおすすめ	ワーシャルフロイド2回
64	GRL_2_A - 最小全域木	2	最小全域木問題/基本問題	クラスカル法
65	JOI 2010 春合宿 - Finals(Day 3), 問題	4	最小全域木問題/JOI 春合宿の問題だが、比較的簡単	クラスカル法 + 一般のKの時の考察
66	AOJ 1127 - Building a Space Station	3	最小全域木問題/-	クラスカル法
67	AtCoder Beginner Contest 065 D - Built?	4	最小全域木問題/やや難しい。素朴な最小全域木ではO(N^2)で解けないが..	ソート -> クラスカル法
68	NTL_1_A - 素因数分解	1~2	高速な素数判定法/基本問題	単純なloopによる解法 or エラトステネスのふるい
69	AtCoder Beginner Contest 084 D - 2017-like Number	3	高速な素数判定法/-	エラトステネスのふるい + 累積和
70	NTL_1_B - べき乗	2	高速なべき乗計算/-	bit演算
71	Square869120Contest #1 E - 散歩	4	高速なべき乗計算/-	bit演算, いもす法
72	AtCoder Beginner Contest 034 C - 経路	3	逆元を使う問題/基本問題	二項係数の計算、逆元
73	Atcoder Beginner Contest 145 D - Knight	3	逆元を使う問題/-	考察、二項係数の計算、逆元
74	AtCoder Beginner Contest 021 D - 多重ループ	3	逆元を使う問題/-	考察、重複組合せ, 逆元
75	AtCoder Beginner Contest 149 F - Surrounded Nodes	5	逆元を使う問題/チャレンジ問題	辺の切断, 全て白の頂点の場合を考慮, DFS, 逆元
76	全国統一プログラミング王決定戦本戦 A - Abundant Resources	1	累積和/基本問題	累積和
77	JOI 2010 本選 1 - 旅人	2	累積和/-	累積和, 添字に注意 or いもす法
78	JOI 2011 本選 1 - 惑星探査	3	累積和/二次元累積和	二次元累積和
79	AtCoder Beginner Contest 106 D - AtCoder Express 2	3	累積和/-	二次元累積和 or 区間DP
80	GigaCode 2019 D - 家の建設	3	累積和/-	二次元累積和
81	AtCoder Beginner Contest 014 C - AtColor	3	いもす法/基本問題	いもす法
82	AOJ 2013 - 大崎	3	いもす法/-	いもす法
83	JOI 2015 本選 1 - 鉄道運賃	3	いもす法/-	いもす法、添字に注意
84	JOI 2012 本選 4 - 釘	5	いもす法/チャレンジ問題	いもす法, 3階差分
85	DSL_1_A - 互いに素な集合	2	Union-Find/基本問題	Union Find
86	AtCoder Beginner Contest 075 C - Bridge	3	Union-Find/深さ優先探索でもUnion Findでも解ける	複数回Union Find or 複数回DFS or 再帰版DFS
87	AtCoder Beginner Contest 120 D - Decayed Bridge	4	Union-Find/少し難しい	Union-Find, 累積和
88	JOI 2008 本選 1 - 碁石ならべ	3	圧縮/-	stack
89	JOI 2013 本選 1 - 電飾	3	圧縮/-	stack
90	Square869120Contest #5 B - Emblem	2	単純な幾何計算/-	sqrtを使用
91	AtCoder Beginner Contest 144 D - Water Bottle	2	単純な幾何計算/-	atanを使用
92	AOJ 1193 - 連鎖消滅パズル	3	実装問題/-	落ちゲー、解くだけ
93	Square869120Contest #3 B - 石落としゲーム	3	実装問題/-	落ちゲー, (WIDTH)×(HEIGHT-1)個シュミレート
94	AOJ 1149 - ケーキカット	4	実装問題/-	連結リスト
95	AtCoder Beginner Contest 149 B - Greedy Takahashi	1	数学的な問題/200-300 点問題の数学的問題の典型	簡単な考察
96	AtCoder Beginner Contest 139 D - ModSum	2	数学的な問題/考察一個	法則性をみつけるだけ
97	AtCoder Beginner Contest 150 D - Semi Common Multiple	3	数学的な問題/-	最小公倍数
98	三井住友信託銀行プログラミングコンテスト2019 予選 E - Colorful Hats 2	3	数学的な問題/-	数学的な考察, 配列
99	DDCC2020 予選 D - Digit Sum Replace	4	数学的な問題/考察一個	考察(数字の遷移方法は2パターンのうちどれか)
100	Tenka1 Programmer Beginner Contest D - Crossing	4	数学的な問題/やや難	部分集合の要素数を決めて構成, n=1も考慮

ヒント

(not yet)