データ構造や数論的アルゴリズムまで、様々な分野のアルゴリズムたちを C++14 で実装しています。
アルゴリズム系の研究開発において計算機実験が必要になる場面や、
プログラミングコンテストに参加する場面などを想定して、
「実装例」または「ライブラリ」として使用することを念頭に置いています。
各種データ構造の実装です
- Union-Find 木 (union by size)
- Union-Find 木 (union by rank)
- 重みつき Union-Find 木
- 部分永続 Union-Find 木
- Quick Find
- Dynamic Connectivity
- セグメント木
- セグメント木 (遅延評価)
- Starry Sky 木 (俗称)
- マージソート過程保存木
- 等差数列区間加算木
- 二次元セグメント木
- RBST
- Treap 木
- AVL 木
- Splay 木
- 赤黒木
- 永続配列
- 完全永続 Union-Find 木
- 永続セグメント木
- 永続赤黒木
- ローリングハッシュ
- Zobrist hash
- 木に対する hash
- Skew Heap (マージ可能)
- Paring Heap (マージ可能)
- Radix Heap
- Fibonacci Heap
- Disjoint Sparse Table
- 並列二分探索
- Wavelet 木
- BinaryTrie 木
- Cartesian 木
ツリー上のクエリ処理のためのデータ構造たちの実装です
- LCA (ダブリング)
- LCA (Euler Tour)
- LCA (HL 分解)
- Euler Tour (頂点上)
- Euler Tour (辺上のクエリ)
- HL 分解
- 重心分解
- Link-Cut 木
- マージテク (俗称)
- DSU on Tree
- Level Ancester
定型的な動的計画法やその他の処理です
- 累積和
- 二次元累積和
- いもす法 (俗称)
- 二次元いもす法 (俗称)
- 三次元いもす法 (俗称)
- 座標圧縮
- スライド最小値
- 転倒数
- LIS
- LCS
- 編集距離
- 重みつき区間スケジューリング問題
- ヒストグラム長方形面積最大化
- 最適二分探索木
- Set Cover
- k-Cover (O(n 2^n))
- k-partition (O(n^3 2^n))
- ナップサック DP
- 区間分割型ナップサック DP
- bitDP
- 桁 DP
- 部分列 DP
- ダブリング DP
- 木 DP
- 全方位木 DP (俗称)
- 二乗の木 DP (俗称)
- 累積和
- スライド最小値
- インライン DP (俗称)
- Convex Hull Trick (傾き単調、クエリも単調)
- Convex Hull Trick (傾き単調)
- Convex Hull Trick (単調でなくてよい)
- Monotone Minima
- Divide and Conquer
- Monge
- Alien DP
- 戻す DP (俗称)
幾何ライブラリです
- 多角形の面積
- 点と多角形の包含判定
- 凸性判定
- 凸包
- 凸多角形の切断
- ボロノイ図 (単純ver, O(n^2))
- 凸多角形の直径
- 円と円の共通部分の面積
- 円と多角形との共通部分の面積
- 最近点対
- 最近円対
- 線分併合
- 線分アレンジメント
- 3 点を通る円
- アポロニウスの円
- 最小包含円
- 双対変換
- kd 木
グラフネットワークフロー関連のアルゴリズムです
- 最小費用流 (Primal-Dual 法, 正辺のみ)
- 最小費用流 (Primal-Dual 法, 負辺対応)
- 最小費用最大流 (Primal-Dual 法, 正辺のみ)
- 最小費用最大流 (Primal-Dual 法, 負辺対応)
- 最小費用循環流 (Cost-Scaling, 負閉路OK)
- 最小カット (= 最大流)
- 全域最小カット（Stoer-Wanger 法）
- 全頂点対間最小カット (Nagamochi-Ibaraki 法)
- Gomory-Hu 木
- 二部マッチング (Hopcroft-Karp 法)
- 重みつき二部マッチング (Hungarian 法)
- 一般グラフの最大マッチング (Edmonds 法)
- 一般グラフの最大マッチング (行列補間)
グラフ理論全般のアルゴリズムです
- DFS (連結成分を数える)
- BFS (重みなしグラフの最短路)
- トポロジカルソート (DFS)
- トポロジカルソート (BFS)
- サイクル検出 (DFS)
- サイクル検出 (BFS)
- サイクル検出 (Union-Find)
- 二部グラフ判定 (DFS)
- 二部グラフ判定 (BFS)
- 二部グラフ判定 (Union-Find)
- 強連結成分分解
- 橋, 関節点列挙 (Low-Link)
- 二重辺連結成分分解
- 二重頂点連結成分分解
- 2-SAT
- ツリーの直径
- ツリーの重心
- 重みなしグラフの最短路 (BFS)
- 重みが 0, 1 のみのグラフの最短路 (0-1 BFS)
- 単一始点最短路 (Dijkstra 法, 正辺のみ)
- 単一始点最短路 (Bellman-Ford 法, 負辺対応)
- 全頂点対間最短路 (Floyd-Warshall 法)
- 全頂点対間最短路 (Johnson 法)
- k-最短路
- SPFA
- 最小全域木 (Kruskal 法)
- 最小有向全域木 (Chu-Liu/Edmonds 法)
- 有向 Euler 路
- 無向 Euler 路
- 彩色数 (O(n2^n))
- 最大安定集合問題 (O(1.381^n))
- 最大クリーク列挙（O(1.443^n)）
- 最小シュタイナー木 (O(n 3^t + n^2 2^t + n^3))
行列計算など代数的計算に関するアルゴリズムです
- 行列 (基本演算)
- 行列累乗 (実数)
- 行列累乗 (mod. p)
- 行列累乗 (binary)
- 連立一次方程式 (実数)
- 連立一次方程式 (mod. p)
- 連立一次方程式 (binary)
- Toeplitz 行列 (乗算, 連立方程式が O(n^2))
- 巡回行列 (乗算が O(n^2))
- コンパニオン行列
- 三重対角行列 (連立方程式が O(n))
- Black Box Linear Algebra
- 二次方程式
- 多項式 (実数係数)
- 多項式 (mod. p 係数)
- きたまさ法 (俗称)
- きたまさ法 with FFT (俗称)
- 多項式補間
- FFT (高速フーリエ変換)
- NTT (高速剰余変換)
- 高速アダマール変換 (SRM 518 div1 hard)
- 高速ゼータ変換
- 高速メビウス変換
- Karatsuba 法
- 二分探索法 (方程式の解を 1 つ求める)
- 三分探索法
- 黄金探索法
- Newton 法
- 単体法
- 分枝限定法
組合せ論的アルゴリズムたちです
- mod 演算 (全部乗せ)
- 累乗
- 逆元
- 二項係数 (オーソドックス、n<=10^7, r<=10^7, p<=10^9)
- 二項係数 (愚直計算, n<=10^9, r<=10^7, p<=10^9)
- 二項係数 (漸化式計算, n<=10^9, r<=10^9, p<=10^7)
- mod の値が大きいとき
- 重複組合せ
- カタラン数
- 分割数
- スターリング数
- ベル数
- ベルヌーイ数
- クイックソート
- マージソート
- ヒープソート
- コムソート
- Radix ソート
- 挿入ソート
- その他のソート達
- マトロイド上の Greedy 法
- マトロイド交差
- Nim
- LIS and LDS
整数論的アルゴリズムたちです
- 素数判定
- 素因数分解
- 確率的素数判定 (Miller-Rabin 法)
- エラトステネスの篩
- エラトステネスの区間篩
- アトキンの篩
- 高速素因数分解 (ロー法)
- Euler のファイ関数
- メビウス関数
- 高速素因数分解 (エラトステネスの篩風)
- 高速ファイ関数 (エラトスネテスの篩風)
- 高速メビウス関数 (エラトスネテスの篩風)
- 中国剰余定理
- 中国剰余定理 (Garner 法)
- 連立一次合同方程式
- ペル方程式
- 離散対数
- 平方剰余
- 有理数
- Stern-Brocot 木
- 多倍長整数
文字列アルゴリズムです
- LL(1) 再帰降下パーサ
- ローリングハッシュ
- 二次元ローリングハッシュ
- 単一パターン検索 (KMP 法)
- 単一パターン検索 (Boyer-Moore 法)
- 複数パターン検索 (Aho-Corasick 法)
- Z 法
- Manacher 法
- Trie 木
- Suffix Array
- Suffix Array (SA-IS)
- Palindromic 木 (AOJ 2292)
- 各 index 以降で各文字が最初に登場する index を求める関数
- split 関数
- 二次元盤面に番兵追加
- 二次元盤面を 90 度回転
その他のアルゴリズムです
- α-β 探索
- 焼き鈍し法
- A*
- IDA*
- Baby-Step Giant-Step 法
- 平面走査法
- デバッグストリーム, chmin, chmax
- タイマー
- サイコロ
- 曜日
- 四面体 (AOJ 2060)