sumik5/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, 最大値, 負の値）で検証した