はじめに
典型問題を解けるか？
競技プログラミングを学ぶ上で、多くの参加者が直面する課題は 「解法の引き出しが足りない」 という問題だ。
過去問演習を繰り返すだけでは、新しい問題に対する対応力は養われにくい。
実際、AtCoderやCodeforcesでは、ある特定の 典型アルゴリズム に基づく問題が頻繁に出題される。
この記事では、競プロにおける 5つの主要なアルゴリズム を整理し、各問題に対するアプローチを明確にする。
1. 配列操作の基本技術
配列は最も基本的なデータ構造の一つだが、その扱い方を工夫することで、多くの問題を効率的に解決できる。
特に 累積和 や スライディングウィンドウ などの手法を使いこなせるかが重要となる。
解法例：最大部分積問題
問題
「配列の部分列の積が最大となる区間を O(n) で求めよ」
解法
- 最小値・最大値の管理
連続した区間の最大積を求める際、負の数の扱いが重要になる。
負の数同士の積が正になることを考慮しながら、区間内の最小値・最大値を適切に管理する。 - ゼロの扱い
要素が 0 を含む場合、その部分で区間を分割し、個別に最大値を求める。
このように、単なる配列の走査にとどまらず、データの特性を考慮したアルゴリズム設計 が求められる。
2. グラフ探索
グラフ構造は、多くの問題で活用される概念であり、特に 最短経路問題 や 到達判定問題 でよく登場する。
代表的なアルゴリズム
- 幅優先探索（BFS）
最短経路や到達可能性を調べる際に有効。
例：「無向グラフにおいて、頂点 A から頂点 B への最短距離を求める」 - 深さ優先探索（DFS）
再帰的な探索を用いて、木構造や再帰的な問題を解決する。
例：「グラフの連結成分を数える」
また、より複雑な問題では ダイクストラ法 や ベルマンフォード法 などの 重み付きグラフに適用可能な手法 も求められる。
| アルゴリズム | 計算量 | 用途 |
|---|---|---|
| BFS | O(V+E) | 最短経路探索（無向グラフ） |
| DFS | O(V+E) | 到達判定、連結成分の探索 |
| ダイクストラ法 | O((V+E)logV) | 正の重み付きグラフの最短経路 |
| ベルマンフォード法 | O(VE) | 負の重みを含む最短経路 |
3. 動的計画法（DP）
動的計画法（Dynamic Programming）は、問題を 小さな部分問題に分割 し、それらの解を再利用することで、計算量を削減する手法である。
代表的な問題
- ナップサック問題
「重さと価値を持つアイテムの中から、重さの制約内で価値が最大となる組み合わせを求める」 dp[i+1][w] = max(dp[i][w], dp[i][w-weight[i]] + value[i])- 状態圧縮を用いることで O(nW) → O(W) に改善可能
-
編集距離（レーベンシュタイン距離）
文字列 A を B に変換する際の最小操作回数を求める。 dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + cost)
計算量の管理が重要 であり、制約を意識しながら効率的な手法を選択する必要がある。
4. 貪欲法
貪欲法は、局所的に最適な選択を行いながら、最終的な解を導く手法である。
ただし、常に正しく動作するわけではなく、適用可能な条件を見極める ことが求められる。
代表的な問題
- 区間スケジューリング問題
できるだけ多くの仕事をスケジュールする場合、終了時間の早い順に選ぶと最適解を得られる。 - 終了時間昇順ソート → 貪欲に選択
- ハフマン符号化
頻度の高い要素を短いビット列に割り当てることで、全体のデータサイズを圧縮する。
貪欲法は 必ずしも最適解を保証しない が、適切な条件下では DP よりも計算量が小さく、実装も容易なため、有力な選択肢となる。
5. 二分探索
二分探索は、ソート済みデータに対して 対数時間 O(log n) の高速探索 を可能にする技術である。
代表的な応用
- 通常の二分探索
整数xがソート済み配列Aに含まれるかどうかを調べる。 - 答えの二分探索
「ある値Xが条件を満たすか？」という関数を定義し、最適なXを探索する。
例：「制約を満たす最小の時間を求める」
また、二分探索を使う際には、終了条件の設計 や オーバーフロー回避 などの注意点がある。
まとめ
競技プログラミングで頻出する 5つの基本アルゴリズム を整理した。
| 技術 | 主な用途 |
|---|---|
| 配列操作 | スライディングウィンドウ、累積和 |
| グラフ探索 | 最短経路、連結判定 |
| 動的計画法 | 部分問題の最適解利用 |
| 貪欲法 | 局所最適解の積み重ね |
| 二分探索 | 高速探索、境界値判定 |
これらの技術を体系的に理解し、問題ごとに 適切な手法を選択できる力 を身につけることが、競技プログラミングでの成長につながる。
コメント