データ構造や数論的アルゴリズムまで、様々な分野のアルゴリズムたちを C++17 で実装しています。
アルゴリズム系の研究開発において計算機実験が必要になる場面や、
プログラミングコンテストに参加する場面などを想定して、
「実装例」または「ライブラリ」として使用することを念頭に置いています。
| 分類 | 内容 | 具体例 |
|---|---|---|
| DATA STRUCTURE | 各種データ構造 | Union-Find、Sparse Table など |
| DATA STRUCTURE : SEGMENT | 区間クエリに強いデータ構造 | セグメント木、BIT など |
| GEOMETRY | 計算幾何 | 円の交点など |
| GRAPH | グラフアルゴリズム | 強連結成分分解など |
| GRAPH : NETWORK FLOW | ネットワークフローアルゴリズム | Ford-Fulkerson 法など |
| MATH : ALGEBRA | 代数的アルゴリズム | 行列計算など |
| MATH : COMBINATORICS | 組合せ論的アルゴリズム | modint、Nim など |
| MATH : NUMBER THEORY | 整数論的アルゴリズム | 素因数分解、最大公約数など |
| OPTIMIZATION | 最適化や探索のアルゴリズム | 二分探索, 三分探索など |
| STRING | 文字列アルゴリズム | Suffix Array、KMP 法など |
| TREE | 木上のデータ構造とアルゴリズム | Euler ツアー、木の直径など |
| OTHERS | その他 | xorshift、サイコロなど |
各種データ構造の実装です
- (★☆☆☆) Union-Find (union by size)
- (★☆☆☆) Union-Find (union by rank)
- (★★☆☆) 重みつき Union-Find
- (★★★☆) 列挙可能 Union-Find
- (★★★☆) undo つき Union-Find
- (★★★☆) 部分永続 Union-Find
- (★☆☆☆) 二分ヒープ
- (★★☆☆) 削除可能 priority queue
- (★★★☆) 両端 priority queue (削除も可能)
- (★★★★) Skew Heap (マージ可能ヒープ)
- (★★★★) Paring Heap (マージ可能ヒープ)
- (★★★★) Radix Heap
- (★★★★) Fibonacci Heap
- (★★☆☆) ハッシュ
- (★★★☆) Zobrist ハッシュ
- (★★★☆) ローリングハッシュ
- (★★★★) 根付き木のハッシュ
- (★★★☆) BIT と BIT 上の二分探索
- (★★★★) 64 分木
- (★★★★) van Emde Boas 木
- (★★★★) 永続配列
- (★★★★) 完全永続 Union-Find
- (★★★★) 永続キュー
- (★★★★) 永続セグメント木
- (★★★★) 永続赤黒木
- (★★★☆) 区間の集合を set で管理する
- (★★★☆) 並列二分探索
- (★★★☆) Cartesian 木
- (★★★★) Binary Trie
- (★★★★) Dynamic Connectivity
セグメント木や BIT など、区間クエリに強いデータ構造の実装です
- (★★☆☆) セグメント木
- (★★★☆) セグメント木 (遅延評価)
- (★★☆☆) BIT
- (★★★☆) BIT (区間加算, 区間和取得に両対応)
- (★★★★) Segment Tree Beats (俗称)
- (★★☆☆) RMQ (セグメント木)
- (★★★☆) Starry Sky 木 (俗称)
- (★★★☆) マージソート過程木 (領域木)
- (★★★☆) 動的セグメント木
- (★★★☆) 二次元セグメント木
- (★★★☆) 二次元 BIT
- (★★★★) 二次元 BIT (領域加算, 領域和取得に両対応)
- (★★★★) 動的二次元セグメント木
- (★★★★) 動的二次元 BIT
- (★★★☆) Sparse Table
- (★★★★) Disjoint Sparse Table
- (★★★★) 二次元 Sparse Table
- (★★★★) ウェーブレット行列
- (★★★★) BIT on ウェーブレット行列 (一点加算対応)
- (★★★★) セグメント木 on ウェーブレット行列
- (★★★★) 動的ウェーブレット行列
- (★★★★) RBST
- (★★★★) Treap 木
- (★★★★) AVL 木
- (★★★★) Splay 木
- (★★★★) 赤黒木
幾何ライブラリです
- (★★★☆) 全部乗せ
- (★★☆☆) 基本要素 (点, 線分, 円)
- (★★☆☆) 偏角ソート
- (★★☆☆) 点と線分の位置関係 (ccw)
- (★★☆☆) 点と三角形の包含関係
- (★★☆☆) 射影
- (★★☆☆) 線分と線分の交差判定
- (★★☆☆) 線分と線分との距離
- (★★★☆) 接線
- (★★★☆) 共通接線 (2 円)
- (★★☆☆) 多角形の面積
- (★★☆☆) 点と多角形の包含判定
- (★★☆☆) 凸性判定
- (★★★☆) 凸包
- (★★★☆) 凸多角形の直径
- (★★★☆) 凸多角形の切断
- (★★★★) 凸多角形と直線の交点 O(log N)
- (★★★★) 円と円の共通部分の面積
- (★★★★) 円と多角形との共通部分の面積
- (★★★☆) ボロノイ図 (単純ver, O(N^3))
- (★★★★) ボロノイ図 (単純ver, O(N log N))
- (★★★★) ドロネーの三角形分割 (期待値 O(N^2))
- (★★★★) 三次元幾何一式
- (★★★☆) 最近点対
- (★★★☆) 線分併合
- (★★★☆) 線分アレンジメント
- (★★★☆) 3 点を通る円
- (★★★☆) アポロニウスの円
- (★★★☆) 双対変換
- (★★★★) 最小包含円
- (★★★★) kd 木
グラフアルゴリズムです
- (★☆☆☆) 連結成分の個数 (DFS)
- (★☆☆☆) 連結成分の個数 (BFS)
- (★☆☆☆) 二部グラフ判定 (DFS)
- (★☆☆☆) 二部グラフ判定 (BFS)
- (★★☆☆) トポロジカルソート (DFS)
- (★★☆☆) トポロジカルソート (BFS)
- (★★☆☆) 閉路検出 (サイクル検出)
- (★★☆☆) Functional グラフの閉路検出 (サイクル検出)
- (★★★☆) 強連結成分分解
- (★★★☆) 橋, 関節点列挙 (Low-Link)
- (★★★★) 二重辺連結成分分解 (Bridge-Block 木)
- (★★★★) 二重頂点連結成分分解 (Block-Cut 木)
- (★★★★) 三重辺連結成分分解 (SPQR 木)
- (★☆☆☆) 重みなしグラフの最短路 (BFS, O(E))
- (★★☆☆) 重みが 0, 1 のみのグラフの最短路 (0-1 BFS, O(E))
- (★★☆☆) 単一始点最短路 (Dijkstra 法, 正辺のみ, O(V + E log V))
- (★★☆☆) 単一始点最短路 (Bellman-Ford 法, 負辺対応, O(VE))
- (★★☆☆) 全頂点対間最短路 (Floyd-Warshall 法, O(V^3))
- (★★★☆) 全頂点対間最短路 (Johnson 法, O(EV log V))
- (★★★☆) SPFA
- (★★★★) 補グラフの最短路
- (★★★★) d-辺最短路
- (★★★★) Monge グラフ上の d-辺最短路
- (★★☆☆) 最小全域木 (Kruskal 法)
- (★★★☆) 有向 Euler 路
- (★★★☆) 無向 Euler 路
- (★★★★) 最小有向全域木 (Chu-Liu/Edmonds 法)
- (★★★★) 行列木定理
- (★★★★) 最小シュタイナー木 (O(V 3^t + V^2 2^t + V^3))
- (★★★☆) 最大安定集合問題 (O(1.381^V))
- (★★★★) 最大クリーク列挙（O(1.443^V)）
- (★★★★) 頂点彩色 (O(2^V V))
- (★★★★) 辺彩色
- (★★★★) 二部グラフの辺彩色 (Alon 法, O(E log E))
グラフネットワークフロー関連のアルゴリズムです
- (★★★☆) 最大流 (Ford-Fulkerson 法)
- (★★★☆) 最大流 (Dinic 法)
- (★★★☆) 下限容量つき最大流
- (★★★☆) 最小費用流 (Primal-Dual 法, 正辺のみ)
- (★★★☆) 最小費用流 (Primal-Dual 法, 負辺対応)
- (★★★★) 最小費用循環流 (Goldberg-Tarjan 法, by cost-scaling, 負閉路 OK)
- (★★★★) 最小費用 b-flow (下限容量つき, 供給点・需要点つき)
- (★★★★) 最小凸費用流
- (★★★☆) Project Selection Problem (俗称: 燃やす埋める)
- (★★★★) 2 変数劣モジュラ関数の和を表す最小カット (燃やす埋めるの一般化)
- (★★★★) 3 変数劣モジュラ関数の和を表す最小カット (燃やす埋めるの一般化)
- (★★★☆) 最小カット (= 最大流)
- (★★★★) 全域最小カット（Stoer-Wanger 法）
- (★★★★) 全頂点対間最小カット (Nagamochi-Ibaraki 法)
- (★★★★) Gomory-Hu 木
- (★★★☆) 二部マッチング (Hopcroft-Karp 法)
- (★★★☆) 重みつき二部マッチング (Hungarian 法)
- (★★★★) 一般グラフの最大マッチング (Edmonds 法)
- (★★★★) 一般グラフの最大マッチング (行列補間)
- (★★★★) 重み付き一般グラフの最大マッチング
行列計算など代数的計算に関するアルゴリズムです
- (★★★☆) 行列累乗, 連立一次方程式 (実数)
- (★★★☆) 行列累乗, ランク, 連立一次方程式 (mod. p)
- (★★★☆) 行列累乗, ランク, 連立一次方程式 (binary)
- (★★★★) Black Box Linear Algebra
- (★★★★) Toeplitz 行列 (乗算, 連立方程式が O(n^2))
- (★★★★) 巡回行列 (乗算が O(n^2))
- (★★★★) コンパニオン行列
- (★★★★) 三重対角行列 (連立方程式が O(n))
- (★★★☆) FFT (高速フーリエ変換)
- (★★★☆) NTT (高速剰余変換)
- (★★★★) 任意 mod 畳み込み
- (★★★★) 添字 GCD 畳み込み
- (★★★★) Karatsuba 法
- (★★★★) 多項式：全部乗せ
- (★★★☆) 多項式の乗算 (by NTT, O(N log N))
- (★★★★) 多項式の除算 (by NTT, inv of FPS, O(N log N))
- (★★★★) 多項式補間
- (★★★☆) Polynomial Taylor Shift
- (★★★★) 多項式 GCD
- (★★★★) 形式的冪級数：全部乗せ
- (★★★★) Sparse な形式的冪級数
- (★★★★) Bostan-Mori 法
- (★★★★) Fiduccia 法 (高速きたまさ法)
- (★★★★) Berlekamp-Massey 法
- (★★★★) 関数の合成
- (★★★★) 逆関数
- (★★★☆) floor sum
- (★★★★) Bk = Σ{i=0}^{n-1} i^k を係数とする多項式
- (★★★★) Σ{i=0}^{n-1} r^i i^d
- (★★★★) Σ{i=0}^{∞} r^i i^d
組合せ論的アルゴリズムたちです
- (★★☆☆) 二項係数 (オーソドックス, n<=10^7, r<=10^7, p<=10^9)
- (★★☆☆) 二項係数 (愚直計算, n<=10^9, r<=10^7, p<=10^9)
- (★★☆☆) 二項係数 (漸化式計算, n<=5000, r<=5000, p<=10^9)
- (★★★★) 二項係数 (任意 mod, n<=10^7, r<=10^7, m<=10^9)
- (★★☆☆) 重複組合せ
- (★★★☆) 分割数 P(N, K) (O(NK))
- (★★★★) 分割数 P(N) (O(N√N))
- (★★★☆) スターリング数
- (★★★☆) ベル数
- (★★★☆) カタラン数
- (★★★☆) ベルヌーイ数
- (★★★☆) モンモール数
- (★★★☆) 2-SAT
- (★★★☆) マトロイド上の Greedy 法
- (★★★★) マトロイド交差
- (★★★☆) 高速ゼータ変換
- (★★★★) 高速アダマール変換
- (★★★★) AND Convolution
- (★★★★) OR Convolution
- (★★★★) XOR Convolution
- (★★★★) Subset Convolution
- (★★★★) 集合冪級数の exp
- (★★★★) 集合冪級数の合成
- (★★★☆) Nim
- (★★★☆) LIS and LDS
- (★★★☆) 転倒数
整数論的アルゴリズムたちです
- (★★☆☆) a^n, a^{-1} (mod m)
- (★★☆☆) Modint
- (★★☆☆) 実行時に法が決まる Modint
- (★★★★) モンゴメリ乗算を用いた Modint (mod は 2^62 未満の奇数)
- (★☆☆☆) 約数列挙
- (★☆☆☆) 最大公約数 (Euclid の互除法)
- (★☆☆☆) 最小公倍数
- (★★☆☆) 拡張 Euclid の互除法
- (★☆☆☆) 素数判定
- (★☆☆☆) 素因数分解
- (★★★☆) Euler のトーティエント関数
- (★★★★) 確率的な高速素数判定 (Miller-Rabin 法)
- (★★★★) 確率的な高速素因数分解 (Pollard のロー法)
- (★★★★) 原始根
- (★★★★) 位数 (a^x ≡ 1 (mod p) となる最小の x)
- (★★★★) N 以下の素数の個数 (O(N^2/3))
- (★☆☆☆) エラトステネスの篩
- (★★☆☆) エラトステネスの区間篩
- (★★★☆) 高速素因数分解, 約数列挙, メビウス関数 (エラトステネスの篩風)
- (★★★★) 線形篩
- (★★★★) アトキンの篩
- (★★★☆) 一次合同方程式
- (★★★☆) 中国剰余定理
- (★★★☆) 中国剰余定理 (Garner 法)
- (★★★☆) 離散対数
- (★★★★) ペル方程式
- (★★★★) 平方剰余 (Tonelli–Shanks 法)
- (★★★☆) 128 ビット整数 (ラッパー)
- (★★★☆) 多倍長整数
- (★★★☆) 有理数
- (★★★★) ガウス整数
- (★☆☆☆) m で割って r 余る, x 以上の最小の整数
- (★★☆☆) 平衡三進法展開
- (★★★☆) Stern-Brocot 木
最適化や探索に関するアルゴリズムです
- (★★☆☆) next_combination (nCk 通りの全探索)
- (★★☆☆) 部分集合の部分集合 (3^N 通りの全探索)
- (★★☆☆) 数独ソルバー
- (★☆☆☆) ナップサック問題
- (★☆☆☆) LIS
- (★☆☆☆) LCS
- (★☆☆☆) 編集距離
- (★★☆☆) グリッドに含まれる最大正方形
- (★★★☆) ヒストグラム長方形面積最大化
- (★★★★) 最適二分探索木 (O(N^2), Monge 性を活かした区間 DP)
- (★★★★) 最適二分探索木 (O(N log N), Hu-Tucker 法)
- (★★★★) Slope Trick
- (★★★★) Monotone Minima
- (★★★★) Alien DP
- (★★★★) LARSCH
- (★★★☆) Convex Hull Trick (傾き単調, クエリも単調)
- (★★★☆) Convex Hull Trick (傾き単調)
- (★★★★) Convex Hull Trick (単調でなくてよい, Li Chao Tree)
- (★★☆☆) 二次方程式
- (★★☆☆) 二分探索法 (方程式の解を 1 つ求める)
- (★★☆☆) 三分探索法
- (★★☆☆) 黄金探索法
- (★★★☆) Newton 法
- (★★★★) 単体法 (二段階単体法)
- (★★★★) 分枝限定法
- (★★★☆) α-β 探索
- (★★★☆) 焼き鈍し法
- (★★★☆) A*
- (★★★☆) IDA*
- (★★★★) Set Cover
- (★★★★) k-Cover (O(2^N N))
- (★★★★) k-partition (O(2^N N^3))
文字列アルゴリズムです
- (★★★☆) LL(1) 再帰下降パーサ
- (★★★☆) Suffix Array
- (★★★☆) ローリングハッシュ
- (★★★☆) 単一パターン検索 (KMP 法)
- (★★★☆) 単一パターン検索 (Boyer-Moore 法)
- (★★★★) 複数パターン検索 (Aho-Corasick 法)
- (★★★☆) Z 法
- (★★★☆) Manacher 法
- (★★★☆) Trie 木
- (★★★★) Palindromic 木 (AOJ 2292)
- (★★☆☆) 各 index 以降で各文字が最初に登場する index を求める関数
- (★★★☆) 文字列の相異なる部分列の個数 (O(cN))
- (★★★☆) 文字列の相異なる連続部分文字列の個数 (O(N))
木上のクエリに答えるデータ構造や、木に関する問題を解くアルゴリズムの実装です
- (★★★☆) 木の走査 (部分木サイズ, LCA など)
- (★★★☆) 木の直径
- (★★★☆) 木の重心
- (★★★★) 木の Distance Frequency Table
- (★★☆☆) 木 DP
- (★★★☆) 二乗の木 DP (俗称)
- (★★★☆) 全方位木 DP
- (★★★☆) 全方位木 DP (辺に重みがある場合)
- (★★★☆) LCA (ダブリング)
- (★★★☆) LCA (Euler Tour)
- (★★★☆) LCA (HL 分解)
- (★★★☆) Euler Tour (頂点上のクエリ)
- (★★★☆) Euler Tour (辺上のクエリ)
- (★★★☆) HL 分解
- (★★★☆) 重心分解
- (★★★☆) DSU on Tree
- (★★★★) Link-Cut 木
- (★★★★) toptree
- (★★★☆) 強平衡二分木の Distance Frequency Table
- (★★★★) Level Ancester
その他のアルゴリズムです
- (★★★★) Fast IO
- (★☆☆☆) グリッドの 4 近傍, 8 近傍
- (★☆☆☆) ハニカムの 6 近傍
- (★★★★) ACL
- (★★☆☆) XorShift, ランダムシャッフル
- (★★☆☆) タイマー
- (★★☆☆) サイコロ
- (★★☆☆) 曜日
- (★★★☆) 四面体 (AOJ 2060)
These codes are licensed under CC0.
