競技プログラミング アルゴリズム集

AtCoderなどの競技プログラミングで使える、アルゴリズムの概要と実装例を紹介するリポジトリです。

📚 対象レベル

初心者から上級者まで、全レベルの競技プログラマーを対象としています。

🗂️ ディレクトリ構成

algorithms/
├── algorithm/         # 基本的なアルゴリズム
├── data_structures/   # データ構造
├── graph/             # グラフ理論
├── dp/                # 動的計画法
└── math/              # 数学・整数論

📖 実装済みアルゴリズム

基本アルゴリズム (algorithm/)

• 二分探索 - 配列検索・答えで二分探索
• 累積和 - 区間和の高速計算
• いもす法 - 区間加算の高速処理
• 尺取り法 - 条件を満たす区間の探索

データ構造 (data_structures/)

• Union-Find - 素集合データ構造
• セグメント木 - 区間クエリ・要素更新
• BIT (Binary Indexed Tree) - 累積和・区間和

グラフ理論 (graph/)

• BFS (幅優先探索) - 最短経路（重みなし）
• DFS (深さ優先探索) - グラフ探索・連結成分
• ダイクストラ法 - 単一始点最短経路（非負辺）
• ベルマンフォード法 - 単一始点最短経路（負辺対応）
• 最小全域木 - クラスカル法・プリム法

動的計画法 (dp/)

• ナップサック問題 - 0-1ナップサック
• LCS (最長共通部分列) - 文字列の類似度
• メモ化再帰 - トップダウンDP
• ビットDP - 集合の状態管理
• 区間DP - 区間の最適化
• 木DP - 木構造でのDP

数学・整数論 (math/)

• GCD/LCM - 最大公約数・最小公倍数
• エラトステネスの篩 - 素数列挙・素因数分解

💡 使い方

各アルゴリズムのフォルダには以下が含まれています：

• README.md - アルゴリズムの概要、計算量、使用場面の説明
• *.cpp - C++による実装例

実装例はそのままコピーして使用できるほか、理解を深めるための学習教材としても利用できます。

📊 アルゴリズム一覧（レベル別）

初心者向け（茶色〜緑色）

• 累積和、二分探索、尺取り法
• DFS/BFS、Union-Find

中級者向け（緑色〜水色）

• ダイクストラ法、最小全域木
• セグメント木、BIT
• メモ化再帰、いもす法

上級者向け（水色〜青色以上）

• ベルマンフォード法
• ビットDP、区間DP、木DP
• 全方位木DP

🎯 アルゴリズム選択ガイド

最短経路を求めたい

• 重みなし → BFS
• 非負の重み → ダイクストラ法
• 負の重み → ベルマンフォード法

区間を扱いたい

• 区間和 → 累積和、BIT、セグメント木
• 区間加算 → いもす法
• 区間最小/最大 → セグメント木

集合を扱いたい

• グループ管理 → Union-Find
• 部分集合の最適化 → ビットDP

文字列を扱いたい

• 部分列 → LCS
• 編集距離 → メモ化再帰

🔗 参考リンク

• AtCoder
• AtCoder Problems

📝 ライセンス

本リポジトリのコードは自由に使用・改変できます。