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も考慮 |