solving-algorithms

アルゴリズムとデータ構造 解法リファレンス

競技プログラミング・アルゴリズム問題解決のための総合ガイド。 問題のタイプと入力サイズから最適なアルゴリズムを選択し、効率的に実装するための知識を提供する。

---

計算量（Big-O）早見表

O表記法の基本

O表記法は入力サイズ n に対するアルゴリズムの計算量を表す。 原則: 実装前に入力の上限から最悪計算量を見積もる。

O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

入力サイズ別 計算量比較

n	O(log n)	O(√n)	O(n log n)	O(n²)	O(2ⁿ)	O(n!)
5	2	2	10	25	32	120
10	3	3	30	100	1,024	3,628,800
20	4	4	80	400	~1,048,576	~2.4 × 10¹⁸
50	5	7	250	2,500	~10³⁰	~3.0 × 10⁶⁴
100	6	10	600	10,000	~10³⁰	~9.3 × 10¹⁵⁷
1,000	9	31	9,000	1,000,000	~10³⁰⁰	実用不可
10,000	13	100	130,000	10⁸	実用不可	実用不可
100,000	16	316	1,600,000	10¹⁰	実用不可	実用不可
1,000,000	19	1,000	19,000,000	10¹²	実用不可	実用不可

実用基準: 基本演算が 数百万〜数千万回以下 であれば数秒以内で処理可能。

代表的アルゴリズムの計算量一覧

カテゴリ	アルゴリズム	Time（最悪）	Space
ソート	挿入ソート / バブル / 選択	O(n²)	O(1)
	マージソート	O(n log n)	O(n)
	クイックソート（平均）	O(n log n)	O(log n)
	クイックソート（最悪）	O(n²)	O(n)
	計数ソート	O(n + k)	O(k)
	ヒープソート	O(n log n)	O(1)
探索	線形探索	O(n)	O(1)
	二分探索	O(log n)	O(1)
	ハッシュ探索	O(1) 平均	O(n)
	深さ優先探索（DFS）	O(V + E)	O(V)
	幅優先探索（BFS）	O(V + E)	O(V)
データ構造	スタック / キュー	O(1) push/pop	O(n)
	二分探索木（BST）	O(log n) 平均	O(n)
	ヒープ（優先度付きキュー）	O(log n)	O(n)
	Union-Find（互いに素な集合）	O(α(n)) ≈ O(1)	O(n)
動的計画法	DP（1次元）	O(n) 〜 O(n²)	O(n)
	DP（2次元 / LCS等）	O(nm)	O(nm)
	ナップザック問題	O(nW)	O(nW)
グラフ	ベルマン-フォード	O(VE)	O(V)
	ダイクストラ法	O((V+E)log V)	O(V)
	ワーシャル-フロイド	O(V³)	O(V²)
	プリム法 / クラスカル法	O(E log V)	O(V)
	トポロジカルソート	O(V + E)	O(V)
計算幾何学	凸包（Graham Scan）	O(n log n)	O(n)
	線分交差判定	O(1) / 1対	O(1)
整数論	素数判定（試し割り）	O(√n)	O(1)
	エラトステネスの篩	O(n log log n)	O(n)
	ユークリッド互除法（GCD）	O(log n)	O(1)
	繰り返し二乗法	O(log n)	O(1)

---

アルゴリズム選択フロー

ステップ1: 問題タイプの特定

問題文を読んで以下を判断:

1. 「整列・順番に並べる」          → ソートアルゴリズム
2. 「探す・存在するか確認」        → 探索アルゴリズム
3. 「最短経路・到達可能か」        → グラフアルゴリズム
4. 「最適解・最大/最小値を求める」  → 動的計画法 or 貪欲法
5. 「集合を管理・グループ化」      → Union-Find / BST
6. 「座標・図形の問題」           → 計算幾何学
7. 「素数・GCD・累乗」            → 整数論
8. 「すべての組み合わせを試す」    → 全探索 / 再帰 / バックトラック

ステップ2: 入力サイズから計算量を判定

入力サイズ (n)	許容できる最悪計算量	代表的なアルゴリズム
n ≤ 10	O(n!) or O(2ⁿ)	全探索・順列全列挙
n ≤ 20	O(2ⁿ)	ビット全探索・メモ化再帰
n ≤ 100	O(n³)	ワーシャル-フロイド・行列DP
n ≤ 1,000	O(n²)	挿入ソート・初等的DP・BFS/DFS
n ≤ 10,000	O(n² ) or O(n√n)	二重ループ・平方分割
n ≤ 100,000	O(n log n)	マージソート・ダイクストラ・BIT
n ≤ 1,000,000	O(n) or O(n log n)	線形アルゴリズム・二分探索

ステップ3: 問題タイプ × アルゴリズム対応表

問題タイプ	小 (n≤1,000)	中 (n≤100,000)	大 (n≤1,000,000)
数列のソート	挿入・選択ソート	マージ・クイックソート	計数ソート（条件付き）
要素の探索	線形探索	二分探索	ハッシュ探索
最短経路（単一）	ベルマン-フォード	ダイクストラ	ダイクストラ+ヒープ
最短経路（全点）	ワーシャル-フロイド	ワーシャル-フロイド	要最適化
最小全域木	クラスカル / プリム	クラスカル / プリム	クラスカル（Union-Find）
最適化問題	全探索	DP / 貪欲法	DP（1次元化）
集合の管理	配列・BST	BST / ハッシュ	Union-Find
グラフ連結性	DFS / BFS	DFS / BFS	Union-Find

---

競技プログラミングの問題解決プロセス

1. 問題文を読む
   ├─ 入力の上限 n を確認
   ├─ 求めるもの（最大/最小/存在/数え上げ）を特定
   └─ 制限時間・メモリ制限を確認

2. アルゴリズムを設計する（実装前）
   ├─ 上記「選択フロー」でアルゴリズムを絞る
   ├─ 最悪計算量を見積もり、制限内に収まるか確認
   └─ O(10⁷〜10⁸) 以下なら概ね安全

3. 実装する
   ├─ 擬似コードでアルゴリズムを確認してから実装
   ├─ コーナーケース（n=0, n=1, 最大値）を意識
   └─ デバッグ: 入出力例で検証

4. 提出 → 不正解なら
   ├─ TLE（時間超過）→ アルゴリズムの計算量を再検討
   ├─ WA（誤答）     → コーナーケース・ロジックの見直し
   └─ MLE（メモリ超過）→ Space計算量を削減

---

重要なデータ構造の使い分け

用途	推奨データ構造	時間計算量
LIFO の処理	スタック (Stack)	O(1) push/pop
FIFO の処理	キュー (Queue)	O(1) enqueue/deque
最大/最小値の取得	ヒープ（優先度付きキュー）	O(log n) insert
動的な集合の管理	BST / 平衡BST	O(log n) 平均
グループの合併・判定	Union-Find	O(α(n)) ≈ O(1)
範囲和・点更新	BIT (Fenwick Tree)	O(log n)
文字列の検索	ハッシュ / KMP	O(n) or O(n+m)

---

referencesファイル一覧

各トピックの詳細実装・典型問題・擬似コードは以下を参照:

ファイル	対象章	主な内容
SORTING.md	3章・7章	挿入/バブル/選択ソート、マージソート、クイックソート、計数ソート、安定ソート、反転数
DATA-STRUCTURES.md	4章・8章・9章・10章・14章	スタック・キュー・連結リスト、木構造・二分木、BST、ヒープ、Union-Find、領域探索
SEARCHING.md	5章・6章・19章	線形探索・二分探索・ハッシュ、再帰・分割統治、全探索・バックトラック、ヒューリスティック探索
DYNAMIC-PROGRAMMING.md	11章・17章	基礎DP（フィボナッチ・LCS・連鎖行列積）、応用DP（コイン問題・ナップザック・LIS・最大正方形）
GRAPHS.md	12章・13章・15章	グラフ表現・DFS・BFS・連結成分、最小全域木・最短経路、全点対最短経路・トポロジカルソート・関節点
COMPUTATIONAL-GEOMETRY.md	16章	点・ベクトル・線分・円・多角形、内積・外積、射影・反射・距離・交差判定、凸包
NUMBER-THEORY.md	18章	素数判定・エラトステネスの篩、最大公約数（ユークリッド互除法）、繰り返し二乗法

---

カテゴリ別 典型問題パターン

ソート系

• 逆順カウント（転倒数）→ マージソートで O(n log n)
• 安定ソートが必要な場面 → マージソート（クイックソートは不安定）
• 整数の範囲が小さい場合 → 計数ソート O(n + k)

探索系

• ソート済み配列で「以上/以下を満たす最初の値」→ 二分探索
• 最適値を二分探索で求める（答えで二分探索）→ O(n log n)
• 制約なしの最適解探索 → バックトラック + 枝刈り

グラフ系

• 無重み最短経路（ホップ数最小）→ BFS
• 重みあり最短経路（非負）→ ダイクストラ
• 重みあり最短経路（負の辺あり）→ ベルマン-フォード
• 全点対最短経路 → ワーシャル-フロイド
• 有向グラフの順序付け → トポロジカルソート
• グループ合併・連結判定（クエリ多数）→ Union-Find

DP系

• 部分問題の最適解が全体の最適解に使える → DP適用のサイン
• 1次元DP: 数列の最適化（LIS・最大部分和）
• 2次元DP: 文字列一致（LCS）・格子上の最適化
• ナップザック: 「重さ制限内で価値最大化」の定番

計算幾何系

• 直線の交差・距離 → 外積・内積で O(1)
• 点が多角形内部か → 半直線との交差数（偶数→外部・奇数→内部）
• 凸包が必要 → Graham Scan O(n log n)

---

計算量見積もりのチェックリスト

□ 入力サイズ n の上限を確認した
□ 設計したアルゴリズムの最悪計算量を計算した
□ 計算量が制限時間（目安: 10⁷〜10⁸ 回以下）に収まる
□ 空間計算量（メモリ）がメモリ制限内に収まる
□ 最善・平均・最悪ケースで動作が正しい
□ コーナーケース（n=0, n=1, 最大値, 負の値）で検証した

---

問題文キーワード → アルゴリズム対応表

問題文に登場する表現から、適用すべきアルゴリズムを素早く特定する。

問題文のキーワード・フレーズ	候補アルゴリズム
「最短経路」「最小コストで移動」	BFS（無重み）/ ダイクストラ（重みあり）
「全点間の距離」	ワーシャル-フロイド
「連結しているか」「同じグループか」	DFS / BFS / Union-Find
「順番に処理」「依存関係がある」	トポロジカルソート
「最小コストで全ノードを接続」	最小全域木（クラスカル / プリム）
「k番目に小さい」「中央値」	ヒープ / ソート
「部分和が最大」「選び方が最適」	動的計画法 / 貪欲法
「重さ制限内で価値最大」	ナップザック DP
「共通部分列」「編集距離」	2次元 DP（LCS / Levenshtein）
「増加部分列の最大長」	DP + 二分探索（LIS）
「ある条件を満たす最小/最大値を求める」	答えで二分探索
「逆順の組み数」「転倒数」	マージソート
「素数かどうか」「n以下の素数をすべて」	試し割り / エラトステネスの篩
「最大公約数」「最小公倍数」	ユークリッド互除法
「xのy乗をmodで求める」	繰り返し二乗法
「全パターンを列挙」「順列」	再帰 / バックトラック
「2点間の距離」「線分の交差」	計算幾何（ベクトル演算）
「凸な形の面積・外形」	凸包アルゴリズム

---

各アルゴリズムカテゴリの核心アイデア

ソートアルゴリズムの本質

なぜO(n log n)が最適か: 比較ベースのソートは情報理論的に O(n log n) が下界。 n個の要素の並び順はn!通りあり、2進探索木の深さはlog(n!)≒n log n となるため。

初等ソート（O(n²)）の選択基準:
  挿入ソート → ほぼソート済みデータに強い（最善 O(n)）
  バブルソート → 実装が単純、転倒数の計算に応用
  選択ソート → 交換回数が最小（O(n)回）

高等ソート（O(n log n)）の選択基準:
  マージソート → 安定・最悪O(n log n)保証・外部メモリO(n)必要
  クイックソート → 平均最速・インプレース・最悪O(n²)あり
  計数ソート   → 整数値の範囲kが小さい場合、O(n+k)で線形ソート可

探索アルゴリズムの本質

二分探索の条件: 配列がソート済みであること（or 単調性があること）。

二分探索の適用パターン:
  - ソート済み配列での値探索          O(log n)
  - 「x以上の最小値」lower_bound      O(log n)
  - 「条件を満たす最小/最大」答えで二分探索 O(n log n)

ハッシュの注意点:
  - 衝突の処理方式（チェイン / オープンアドレス）
  - 最悪O(n)になる場合があるため、ハッシュ関数の選択が重要

動的計画法（DP）の本質

DP適用の3条件:

1. 最適部分構造: 最適解が部分問題の最適解から構成できる
2. 重複部分問題: 同じ部分問題が繰り返し登場する
3. 無後効性: 現在の状態が決まれば、過去の経緯は関係ない

DP設計の手順:
  1. 「状態」を定義: dp[i] = ... の意味を明確にする
  2. 「遷移」を導出: dp[i] を dp[i-1], dp[i-2],... から求める式
  3. 「初期値」を設定: dp[0], dp[1] などの基底ケース
  4. 「計算順序」を確認: 依存する部分問題が先に計算される順序

メモ化再帰 vs ボトムアップ:
  メモ化再帰  → 自然な再帰構造を保てる・不要な部分問題をスキップ
  ボトムアップ → スタックオーバーフローなし・キャッシュ効率が良い

グラフアルゴリズムの本質

グラフの表現方法と適切な選択:

隣接行列 (V×V 配列):
  - メモリ: O(V²) → 頂点数が小さい場合（V ≤ 1,000）
  - 利点: 辺の存在確認 O(1)
  - 欠点: 疎グラフでは空間を無駄遣い

隣接リスト (各頂点の辺リスト):
  - メモリ: O(V + E) → 疎グラフに適する
  - 利点: 隣接頂点の列挙が効率的 O(degree(v))
  - 欠点: 辺の存在確認 O(degree(v))

DFS vs BFS の使い分け:

DFS（深さ優先）が適する:
  - パスの存在確認・連結成分の発見
  - トポロジカルソート
  - バックトラック（全探索）
  - 木の巡回

BFS（幅優先）が適する:
  - 無重みグラフの最短経路（ホップ数最小）
  - 最短距離の探索
  - 層別処理（二部グラフ判定等）

Union-Find（互いに素な集合）の核心

目的: 動的な集合の合併と所属判定を高速に行う

操作:
  find(x)  → x が属するグループの代表元を返す
  union(x, y) → x と y のグループを合併する

最適化:
  経路圧縮（path compression）: find 時に根への直結を行う
  ランクによる合併（union by rank）: 小さい木を大きい木に接続

計算量: α(n) ≈ 実質 O(1)（アッカーマン関数の逆数）

---

主要アルゴリズム 擬似コード一覧

二分探索

function binary_search(sorted_array, target):
    left = 0, right = length(array) - 1
    while left <= right:
        mid = (left + right) / 2
        if array[mid] == target: return mid
        if array[mid] < target:  left = mid + 1
        else:                    right = mid - 1
    return -1  // 見つからない

ダイクストラ法（優先度付きキュー版）

function dijkstra(graph, start):
    dist[v] = INF for all v; dist[start] = 0
    priority_queue Q  // (距離, 頂点) の最小ヒープ
    enqueue(Q, (0, start))

    while Q is not empty:
        (d, u) = dequeue_min(Q)
        if d > dist[u]: continue  // 古いエントリをスキップ
        for each edge (u, v, weight):
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                enqueue(Q, (dist[v], v))
    return dist

DP: ナップザック問題

// n個のアイテム、重さw[i]、価値v[i]、容量W
function knapsack(n, W, w[], v[]):
    dp[j] = 0 for all j in [0..W]

    for i = 0 to n-1:
        for j = W downto w[i]:  // 逆順で0-1ナップザック
            dp[j] = max(dp[j], dp[j - w[i]] + v[i])
    return dp[W]

Union-Find

parent[i] = i for all i  // 初期化: 各要素が自分の代表

function find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  // 経路圧縮
    return parent[x]

function union(x, y):
    px = find(x), py = find(y)
    if px != py: parent[px] = py  // 合併

マージソート

function merge_sort(array, left, right):
    if left >= right: return
    mid = (left + right) / 2
    merge_sort(array, left, mid)
    merge_sort(array, mid+1, right)
    merge(array, left, mid, right)  // 2つのソート済み列を合併

function merge(array, left, mid, right):
    L = array[left..mid], R = array[mid+1..right]
    i = 0, j = 0, k = left
    while i < len(L) and j < len(R):
        if L[i] <= R[j]: array[k++] = L[i++]
        else:             array[k++] = R[j++]
    // 残りを追加

---

計算量見積もりのチェックリスト

□ 入力サイズ n の上限を確認した
□ 設計したアルゴリズムの最悪計算量を計算した
□ 計算量が制限時間（目安: 10⁷〜10⁸ 回以下）に収まる
□ 空間計算量（メモリ）がメモリ制限内に収まる
□ 最善・平均・最悪ケースで動作が正しい
□ コーナーケース（n=0, n=1, 最大値, 負の値）で検証した