様々なアルゴリズムの実装例

データ構造や数論的アルゴリズムまで、様々な分野のアルゴリズムたちを C++23 で実装しています。
アルゴリズム系の研究開発において計算機実験が必要になる場面や、プログラミングコンテストに参加する場面などを想定して、「実装例」または「ライブラリ」として使用することを念頭に置いています。

分類	内容	具体例
DATA STRUCTURE : BASIC	基礎的なデータ構造	Union-Find など
DATA STRUCTURE : SEGMENT	区間クエリに強いデータ構造	セグメント木、BIT など
DATA STRUCTURE : ADVANCED	その他の高度なデータ構造	永続データ構造など
GEOMETRY	計算幾何	円の交点など
GRAPH	グラフアルゴリズム	強連結成分分解など
MATH : LINEAR ALGEBRA	線形代数アルゴリズム	行列計算など
MATH : POLYNOMIAL	多項式・FPS アルゴリズム	多項式補間、FPS 合成など
MATH : COMBINATORICS	組合せ論的アルゴリズム	modint、Nim など
MATH : NUMBER THEORY	整数論的アルゴリズム	素因数分解、最大公約数など
NETWORK FLOW	ネットワークフローアルゴリズム	Ford-Fulkerson 法など
OPTIMIZATION	最適化のアルゴリズム	動的計画法など
SEARCH	探索のアルゴリズム	全探索, 二分探索など
STRING	文字列アルゴリズム	Suffix Array、KMP 法など
TREE	木上のデータ構造とアルゴリズム	Euler ツアー、木の直径など
OTHERS	その他	xorshift、サイコロなど

難易度表記の目安

(★☆☆☆)：一般教養、NoviSteps グレード基準で 2Q 以下相当
(★★☆☆)：初等典型、NoviSteps グレード基準で 1Q, 1D 相当
(★★★☆)：中堅典型、NoviSteps グレード基準で 2D, 3D 相当
(★★★★)：高度典型、NoviSteps グレード基準で 4D 以上相当

基礎的なデータ構造 (DATA STRUCTURE : BASIC)

Union-Find など、基礎的なデータ構造の実装です。

Union-Find

ヒープ・キュー

ハッシュ・ハッシュテーブル

順序付き集合

(★★☆☆) 順序付き集合 (by std::set)
(★★☆☆) N 以下の非負整数の順序付き集合 (by BIT)
(★★★☆) N 以下の非負整数の順序付き集合 (by 64 分木)
(★★★☆) Binary Trie
(★★★☆) 区間の集合を set で管理するテク (del と add が互いに逆操作である必要がある場合)
(★★★☆) 区間の集合を set で管理するテク (del と add が互いに逆操作でなくてもよい場合)

その他

(★☆☆☆) 累積和
(★☆☆☆) 二次元累積和
(★★☆☆) オンライン二部グラフ判定
(★★★☆) スライド最小値
(★★★☆) SWAG
(★★★☆) Mo 法

区間系データ構造 (DATA STRUCTURE : SEGMENT)

セグメント木や BIT など、区間クエリに強いデータ構造の実装です。

セグメント木

(★★☆☆) セグメント木
(★★★☆) 双対セグメント木
(★★★☆) 遅延評価セグメント木
(★★★☆) 二次元セグメント木
(★★★★) Segment Tree Beats (俗称)

さまざまなセグメント木

BIT (Binary Indexed Tree)

セグメント木・BIT の応用

Sparse Table

(★★★☆) Sparse Table
(★★★★) Disjoint Sparse Table
(★★★★) 二次元 Sparse Table

ウェーブレット行列

Splay 木

(★★★★) Splay 木
(★★★★) 遅延伝播反転可能 Splay 木

赤黒木

(★★★★) 赤黒木

その他平衡二分探索木

(★★★★) RBST
(★★★★) Treap
(★★★★) AVL 木
(★★★★) 遅延伝播反転可能 RBST
(★★★★) 遅延伝播反転可能 Treap

高度なデータ構造 (DATA STRUCTURE : ADVANCED)

その他の高度なデータ構造の実装です。

高度なヒープ

(★★★★) Skew Heap (マージ可能ヒープ)
(★★★★) Paring Heap (マージ可能ヒープ)
(★★★★) Radix Heap
(★★★★) Fibonacci Heap

動的データ構造

(★★★★) 動的 bitset
(★★★★) 動的 Union-Find
(★★★★) 動的セグメント木
(★★★★) 動的二次元セグメント木
(★★★★) 動的 BIT
(★★★★) 動的二次元 BIT
(★★★★) 動的ウェーブレット行列

並列データ構造

(★★★☆) 並列二分探索
(★★★★) 並列 Union-Find

永続データ構造

(★★★★) 永続配列
(★★★★) 永続 queue
(★★★★) 永続セグメント木
(★★★★) 完全永続 Union-Find
(★★★★) 永続赤黒木

その他

(★★★☆) 根付き木のハッシュ
(★★★★) 領域 Union-Find
(★★★★) Dynamic Connectivity

幾何 (GEOMETRY)

幾何アルゴリズムです。

(★★★☆) 幾何全部乗せ

基本要素

(★☆☆☆) 基本要素 (点, 線分, 円)
(★☆☆☆) 偏角ソート

点, 線分, 三角形などの位置関係

(★☆☆☆) 点と線分の位置関係 (ccw)
(★☆☆☆) 点と三角形の包含関係

射影, 交差判定, 距離

(★☆☆☆) 射影
(★☆☆☆) 線分と線分の交差判定
(★☆☆☆) 線分と線分との距離

直線や円の交点

(★☆☆☆) 直線と直線の交点
(★★☆☆) 円と直線の交点
(★★☆☆) 円と円の交点
(★★☆☆) 円と線分の交点

多角形

(★☆☆☆) 多角形の面積
(★★☆☆) 点と多角形の包含判定
(★★☆☆) 凸性判定
(★★☆☆) 凸包
(★★★☆) 凸多角形の直径
(★★★☆) 凸多角形の切断
(★★★☆) 凸多角形と直線の交点 O(log N)

円

(★★☆☆) 接線
(★★★☆) 共通接線 (2 円)
(★★★☆) 3 点を通る円
(★★★☆) アポロニウスの円
(★★★☆) 円と円の共通部分の面積
(★★★☆) 円と多角形の共通部分の面積
(★★★★) 最小包含円

ボロノイ図

(★★★☆) ボロノイ図 (単純ver, in O(N^3))
(★★★★) ボロノイ図 (O(N log N))
(★★★★) ドロネーの三角形分割 (期待値 O(N^2))

三次元幾何

(★★★☆) 三次元幾何一式

その他

(★★☆☆) 垂直二等分線
(★★★☆) 最近点対
(★★★☆) 線分併合
(★★★☆) 線分アレンジメント
(★★★☆) 双対変換
(★★★★) kd 木

グラフ (GRAPH)

グラフアルゴリズムです

グラフ

(★☆☆☆) グラフテンプレート
(★★★☆) ランダムツリー生成
(★★★☆) ランダムグラフ生成

グラフ探索

連結成分分解

(★★☆☆) 強連結成分分解
(★★★☆) 橋, 関節点列挙 (Low-Link)
(★★★☆) 二重辺連結成分分解 (Bridge-Block 木)
(★★★☆) 二重頂点連結成分分解 (Block-Cut 木)
(★★★★) 三重辺連結成分分解 (SPQR 木)

最短路問題

(★☆☆☆) 重みなしグラフの最短路 (BFS, in O(E))
(★☆☆☆) 重みが 0, 1 のみのグラフの最短路 (0-1 BFS, in O(E))
(★☆☆☆) 単一始点最短路 (Dijkstra 法, 正辺のみ, in O(V + E log V))
(★☆☆☆) 単一始点最短路 (Bellman-Ford 法, 負辺対応, in O(VE))
(★☆☆☆) 全頂点対間最短路 (Floyd-Warshall 法, in O(V^3))
(★★★☆) 全頂点対間最短路 (Johnson 法, in O(EV log V))
(★★★☆) SPFA (Shortest Path Faster Algorithm)

全域木, 路

(★★☆☆) 最小全域木 (Kruskal 法)
(★★★☆) 有向 Euler 路
(★★★☆) 無向 Euler 路
(★★★★) 最小有向全域木 (Chu-Liu/Edmonds 法)
(★★★★) 無向グラフの全域木の個数 (行列木定理)

グラフ上の指数時間アルゴリズム

(★★★☆) 最大安定集合問題 (in O(1.381^V))
(★★★☆) 最大クリーク列挙（in O(1.443^V)）
(★★★☆) 頂点彩色 (in O(2^V V))
(★★★★) 辺彩色
(★★★★) 最小シュタイナー木 (in O(V 3^t + V^2 2^t + V^3))

一般グラフのマッチング

(★★★★) 重みなし一般グラフの最大マッチング (行列補間, in O(V^3))
(★★★★) 重みなし一般グラフの最大マッチング (Edmonds 法, in O(V^3))
(★★★★) 重み付き一般グラフの最大マッチング (Edmonds 法, in O(V^3))

その他

(★★★☆) サイクル基底 (XOR 和をとるもの)
(★★★★) 補グラフの最短路
(★★★★) 二部グラフの辺彩色 (Alon 法, in O(E log E))

線形代数 (MATH : LINEAR ALGEBRA)

行列計算など、線形代数に関するアルゴリズムです

体上の行列

環上の行列

(★★★☆) 半環上の行列 (加法・乗法, 行列累乗)
(★★★★) Euclid 環上の行列 (加法・減法・乗法, 行列累乗, 行列式 (in O(N^3 log M)))
(★★★★) Fp 係数の多項式行列 (加法・減法・乗法, 行列累乗, 行列式 (in O(N^3 D)))
(★★★★) 一般の可換環上の行列 (加法・減法・乗法, 行列累乗, 行列式 (in O(N^4)))

行列式

(★★★★) 任意 mod 行列式 (by Euclid 環上の行列式計算 in O(N^3 log M)))
(★★★★) Fp 体上の行列の特性多項式 (in O(N^3))
(★★★★) Fp 体上の行列の行列式 det(M0 + M1x) (in O(N^3))

F2 体上の線形代数

(★★★☆) F2 体上の行列 (with bitset 高速化)
(★★★☆) XOR 基底 (俗称：noshi 基底)
(★★★☆) F2 ベクトル空間の交差

その他の行列アルゴリズム

(★★★★) Strassen 法
(★★★★) 余因子行列
(★★★★) 多項式行列の prefix product M(0)M(1)...M(K-1)
(★★★★) ハフニアン (完全マッチングの個数に帰着)
(★★★★) パフィアン

さまざまな行列

(★★★★) Black Box Linear Algebra (行列式計算 in O(N^2 + N T(N)))
(★★★★) 巡回行列 (行列式計算 in O(N^2))
(★★★★) 上三角 Toeplitz 行列 (行列式計算 in O(N^2))
(★★★★) K 重対角行列 (行列式計算 in O(NK^2))
(★★★★) 二項係数行列の作用
(★★★★) スターリング数行列の作用

多項式・FPS (MATH : POLYNOMIAL)

多項式や FPS に関するアルゴリズムです

(★★★★) 多項式・FPS 全部乗せ

FFT, NTT, Convolution

(★★★☆) FFT (高速フーリエ変換)
(★★★☆) NTT (高速剰余変換)
(★★★☆) 任意 mod Convolution (mod < 10^9)
(★★★★) mod 2^64 Convolution
(★★★★) Relaxed Convolution
(★★★★) 二次元 FFT
(★★★★) 多変数巡回 FFT

形式的冪級数 (FPS)

(★★★★) Inv of FPS
(★★★★) Exp of FPS
(★★★★) Log of FPS
(★★★★) Pow of FPS
(★★★★) Sqrt of FPS

FPS のアルゴリズム

(★★★★) Bostan-Mori 法
(★★★★) Berlekamp-Massey 法
(★★★★) Power Projection
(★★★★) FPS の合成 (Kinoshita-Li 法, in O(N (log N)^2))
(★★★★) FPS の逆関数 (Kinoshita-Li 法, in O(N (log N)^2))
(★★★★) pow 列挙
(★★★★) 部分分数分解
(★★★★) 常微分方程式
(★★★★) 三角関数

さまざまな FPS

(★★★★) オンライン FPS
(★★★★) 多変数 FPS

多項式の基底変換

(★★★☆) Polynomial Taylor Shift (in O(N log N))
(★★★☆) Lagrange 補間 (f(0), f(1), ..., f(D) -> f(x))
(★★★★) 多項式補間 (in O(N(log N)^2))
(★★★★) 多項式補間 (等比数列のとき) (in O(N log N))
(★★★★) Multipoint Evaluation (in O(M(log M)^2 + N log N))
(★★★★) Multipoint Evaluation (等比数列のとき) (by chirp z-transform, in O(N log N))
(★★★★) 多項式の基底変換：Monomial 基底 → Newton 基底 (in O(N(log N)^2))

多項式のアルゴリズム

(★★★☆) 多項式マージテク (次数の総和が D の多項式の総積 in O(D (log D)^2))
(★★★☆) 多項式の累乗 f(x)^e mod g(x)
(★★★☆) 多項式の middle product (c[i] = sum_j a[i+j]b[j])
(★★★★) 多項式の評価点シフト (in O((N + M)log(N + M))
(★★★★) 多項式の除算 (by NTT, inv of FPS, in O(N log N))
(★★★★) 多項式 GCD (by half-gcd, in O(N(log N)^2))
(★★★★) 多項式の零点を求める (mod 998244353)

さまざまな値の高速計算

(★★★★) 自然数の k 乗和 (Faulhaber の公式)
(★★★★) Σ{i=0}^{n-1} r^i i^d
(★★★★) Σ{i=0}^{∞} r^i i^d
(★★★★) Σ{i=0}^{n-1} a^i f(i)
(★★★★) N! mod P (by FPS, O(√P log P))
(★★★★) Tetration
(★★★★) 二項係数の prefix sum の多点評価
(★★★★) Karatsuba 法

組合せ (MATH : COMBINATORICS)

数え上げなど、組合せ数学に関するアルゴリズムです。

Modint

(★☆☆☆) Modint
(★★☆☆) 実行時に法が決まる Modint
(★★★☆) モンゴメリ乗算を用いた Modint (mod は 2^62 未満の奇数)

二項係数

(★☆☆☆) 二項係数 (オーソドックス, 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)

写像12相

(★★☆☆) 重複組合せ
(★★★☆) カタラン数
(★★★☆) 分割数 P(N, K) (in O(NK))
(★★★★) 分割数 P(N) (in O(N√N))
(★★★☆) 第一種スターリング数
(★★★☆) 第二種スターリング数
(★★★☆) ベル数

その他の数

(★★★☆) ベルヌーイ数
(★★★☆) モンモール数

集合冪級数 (SPS)

(★★★☆) 高速ゼータ変換・高速メビウス変換
(★★★★) 高速アダマール変換
(★★★★) AND Convolution
(★★★★) OR Convolution
(★★★★) XOR Convolution
(★★★★) Subset Convolution
(★★★★) 集合冪級数の exp
(★★★★) 集合冪級数の合成

ゲーム

(★★☆☆) Nim
(★★☆☆) Grundy 数
(★★★★) Nim Product
(★★★★) Grundy 数と多項式環の変換
(★★★★) 超現実数

その他

(★★☆☆) LIS and LDS
(★★★★) プリューファーコード
(★★★★) 半環

整数 (MATH : NUMBER THEORY)

整数論的アルゴリズムです。

約数, 倍数

(★☆☆☆) 約数列挙
(★☆☆☆) 最大公約数 (Euclid の互除法)
(★☆☆☆) 最小公倍数

modpow, modinv

(★☆☆☆) 拡張 Euclid の互除法
(★☆☆☆) a^n, a^{-1} (mod m)

素数

原始根, 位数, 離散対数

(★★★☆) 原始根
(★★★☆) 位数 (a^x ≡ 1 (mod p) となる最小の x)
(★★★☆) 離散対数

エラトステネスの篩

(★☆☆☆) エラトステネスの篩
(★★☆☆) エラトステネスの区間篩
(★★☆☆) 高速素因数分解, 約数列挙, メビウス関数 (エラトステネスの篩風)
(★★★★) 線形篩
(★★★★) アトキンの篩

乗法的関数

(★★☆☆) Euler のトーティエント関数
(★★★★) Euler のトーティエント関数の和
(★★★★) 高速ゼータ変換：約数倍数関係
(★★★★) 添字 GCD Convolution
(★★★★) 添字 LCM Convolution
(★★★★) Multivariate Multiplication
(★★★★) 乗法的関数の列挙
(★★★★) 乗法的関数の prefix sum の列挙
(★★★★) 無平方数の個数
(★★★★) N 以下の素数の個数 (O(N^{2/3}))

方程式

(★★★☆) 中国剰余定理
(★★★☆) 中国剰余定理 (Garner 法)
(★★★★) ペル方程式
(★★★★) 平方剰余 (Tonelli–Shanks 法)
(★★★★) Kth Root (MOD) (Tonelli–Shanks 法)

多倍長整数

(★★☆☆) 128 ビット整数
(★★★☆) 多倍長整数 (ナイーブ)
(★★★★) 多倍長整数 (高速)
(★★★★) 多倍長整数の分数
(★★★★) 多倍長整数の最大公約数

有理数

(★★★☆) 有理数
(★★★☆) Stern-Brocot 木
(★★★★) Enumerate Convex
(★★★★) Enumerate Quotients

その他

(★☆☆☆) 平衡三進法展開
(★★★☆) floor sum
(★★★★) ガウス整数

ネットワークフロー (NETWORK FLOW)

ネットワークフロー関連のアルゴリズムです。

(★★★★) フロー全部乗せ

最大流

(★★★☆) 最大流 (Ford-Fulkerson 法)
(★★★☆) 最大流 (Dinic 法, in O(V^2E))
(★★★☆) 最大流 (Push-Relabel 法, in O(V^2√E))
(★★★☆) フローの s-t パス・サイクルへの分解

最小カット

(★★★☆) 最小カット (= 最大流)
(★★★★) 全域最小カット (Stoer-Wanger 法, in O(V^3))
(★★★★) Gomory-Hu 木

最小費用流

(★★★☆) 最小費用流 (Primal-Dual 法, 正辺のみ)
(★★★☆) 最小費用流 (Primal-Dual 法, 負辺対応 by ポテンシャル, 負閉路 NG)
(★★★★) 最小費用循環流 (Goldberg-Tarjan 法, by cost-scaling, 負閉路 OK)
(★★★★) 費用流の s-t パス・サイクルへの分解

b-flow

(★★★★) 最小流量制約付き最大流
(★★★★) 最小流量制約付き最小費用 b-flow (by primal-dual, 負閉路 NG)
(★★★★) 最小流量制約付き最小費用 b-flow (by cost-scaling)
(★★★★) 最小流量制約付き最小費用 b-flow (by ネットワーク単体法)

二部マッチング

(★★★☆) 二部マッチング (Hopcroft-Karp 法, in O(E√V))
(★★★☆) 重み付き二部マッチング (Hungarian 法)
(★★★★) 二部マッチングの bitset 高速化
(★★★★) アンバランス重み付き二部マッチング (in O((K^2 log N + K^3)N))

二部マッチングの応用

劣モジュラ関数のグラフ表現

(★★★☆) Project Selection Problem (俗称：燃やす埋める)
(★★★☆) 2 変数 2 値の劣モジュラ関数の和の最小化
(★★★★) 3 変数 2 値の劣モジュラ関数の和の最小化
(★★★★) 2 変数 K 値の Monge 関数の和の最小化

series-parallel グラフ上の最小費用流の slope trick 帰着

(★★★☆) 2 端子 + Line グラフ上の最小費用流

最小費用流の応用

(★★★★) 最小凸費用 b-flow (by primal-dual)
(★★★★) 最小費用テンション (最小費用流問題の双対問題)
(★★★★) Longest Shortest Path

最適化 (OPTIMIZATION)

最適化に関するアルゴリズムです。

(★★★★) Monge 全部乗せ
(★★★★) マトロイド全部乗せ

動的計画法

(★☆☆☆) ナップサック問題
(★☆☆☆) LIS
(★☆☆☆) LCS
(★☆☆☆) 編集距離
(★★☆☆) グリッドに含まれる最大正方形
(★★★☆) ヒストグラム長方形面積最大化
(★★★★) 最適二分探索木 (Hu-Tucker 法, in O(N log N))

制約付き最適化

(★★★☆) 最短路問題の双対問題 (俗称：牛ゲー)
(★★★★) Alien's Trick --- min: f(x) s.t. g(x) = K (by ラグランジュ緩和)
(★★★★) 単体法 (二段階単体法)
(★★★★) 分枝限定法

区分線形凸関数の活用 1 ： Convex Hull Trick

(★★★☆) Convex Hull Trick (直線：傾き単調, in O(log N)) (クエリも単調なら O(1))
(★★★★) Convex Hull Trick (直線：傾き単調でなくてよい, by Li Chao Tree, in O(log N))
(★★★★) Convex Hull Trick (直線：傾き単調でなくてよい, by Line Container, in O(log C))
(★★★★) 2D Line container (max(ax + by) クエリ)

区分線形凸関数の活用 2 ： Slope Trick

(★★★☆) Slope Trick (傾きの変化点を管理 by priority queue)
(★★★★) Dual Slope Trick (各区間の傾きを管理 by priority queue)
(★★★★) Super Slope Trick (by Splay 木)

区分線形凸関数の活用 3 ： Min Plus Convolution

(★★★☆) Min Plus Convolution (凸と凸)
(★★★★) Min Plus Convolution (凸と任意)
(★★★★) Min Plus Convolution (凹と任意)
(★★★★) Axiotis-Tzamos Knapsack

行最小値問題・単一始点最短路問題

(★★★☆) Monotone 行最小値問題 (Monotone Minima, in O(H + W log H))
(★★★☆) Monotone 単一始点最短路問題 (D&D Monotone Minima, in O(N (log N)^2))
(★★★☆) TM 行最小値問題 (SMAWK 法, in O(H + W))
(★★★☆) TM 単一始点最短路問題 (D&D SMAWK 法, in O(N log N))
(★★★☆) Monge 単一始点 d-辺最短路の d = 1, 2, ..., D における列挙 (by SMAWK 法, in O(ND))
(★★★★) 辺コストのスライドアクセスへの対応 (Monotone Minima OK, SMAWK NG)

Monge 最短路問題

(★★★★) Monge 単一始点最短路問題 (by LARSCH 法, in O(N))
(★★★★) Monge 単一始点最短路問題 (by noshi's 簡易 LARSCH 法, in O(N log N))
(★★★★) Monge 単一始点最短路問題スライドアクセス版 (by noshi's 簡易 LARSCH 法, in O(N log N))
(★★★★) Monge 単一始点 d-辺最短路問題 (by Alien DP, in O(N log N) / O(N (log N)^2))
(★★★★) Monge 全点間最短路問題 (in O(N^2))
(★★★★) anti-Monge 単一始点最短路問題 (by D&D SMAWK 法, in O(N log N))

その他 Monge 性, L 凸性

(★☆☆☆) Monge 性の判定 (in O(NM))
(★★★☆) Monge 行列の積 (in O(N^2))
(★★★☆) Monge 行列の min-plus 合成 (in O(N^2))
(★★★☆) Monge 性 & 単調性を満たす区間 DP の Knuth-Yao Speedup (in O(N^2))
(★★★★) Monge Convex Hull Trick (by Li Chao Tree, in O(log N))

マトロイド, M 凸性

(★★★☆) マトロイド上の Greedy 法
(★★★★) マトロイド交差

探索 (SEARCH)

探索に関するアルゴリズムです。

さまざまな全探索

(★★☆☆) next_combination (nCk 通りの全探索)
(★★☆☆) 下位集合の列挙 (3^N 通りの全探索)
(★★☆☆) 上位集合の列挙
(★★☆☆) 数独ソルバー

SAT

(★★★☆) 2-SAT
(★★★★) SAT Solver

ヒューリスティック探索

(★★★☆) α-β 探索
(★★★☆) 焼き鈍し法
(★★★☆) A*
(★★★☆) IDA*

指数時間アルゴリズム

(★★★★) Set Cover
(★★★★) k-Cover (O(2^N N))
(★★★★) k-partition (O(2^N N^3))

文字列 (String)

文字列アルゴリズムです。

構文解析

(★★☆☆) LL(1) 再帰下降パーサ

文字列検索

(★★☆☆) ローリングハッシュ
(★★★☆) 単一パターン検索 (KMP 法)
(★★★★) 複数パターン検索 (Aho-Corasick 法)
(★★★★) 二次元ローリングハッシュ
(★★★★) セグメント木上のローリングハッシュ

Suffix Array

(★★★☆) Suffix Array
(★★★☆) Suffix Tree
(★★★☆) Suffix Automation

さまざまな文字列アルゴリズム

(★★☆☆) Z 法
(★★★☆) Manacher 法
(★★★☆) Run Enumerate

さまざまな文字列データ構造

(★★★☆) Trie 木
(★★★★) Palindromic 木 (AOJ 2292)

有名問題

(★★★☆) 文字列の相異なる subsequence の個数 (by 集める DP, in O(N))
(★★★☆) 文字列の相異なる substring の個数 (by Suffix Array, in O(N))
(★★★☆) N 個の文字列の concat のうち、辞書順最小のもの

その他

(★☆☆☆) ランレングス圧縮
(★★★★) ワイルドカードパターンマッチング

木 (Tree)

木上のクエリに答えるデータ構造や、木に関する問題を解くアルゴリズムの実装です

木

(★★★☆) 木の走査 (部分木サイズ, LCA, Euler tour など)
(★★★☆) LCA (by ダブリング)
(★★★☆) 木の直径
(★★★☆) 木の中心
(★★★☆) 木の重心
(★★★★) 木の Distance Frequency Table

木の亜種 (Functional Graph など)

木 DP

(★★☆☆) 木 DP
(★★★☆) 二乗の木 DP (俗称)
(★★★☆) 全方位木 DP
(★★★☆) 全方位木 DP (辺に重みがある場合)

Euler Tour

(★★★☆) Euler Tour
(★★★☆) LCA (by Euler Tour)
(★★★☆) 部分木加算 (by Euler Tour)

HL 分解

(★★★☆) HL 分解
(★★★☆) LCA (by HL 分解)

重心分解

(★★★☆) 重心分解

Link-Cut 木

(★★★★) Link-Cut 木
(★★★★) 部分木加算 (by Link-Cut 木)
(★★★★) 遅延伝播 Link-Cut 木

toptree

(★★★★) toptree

さまざまな木

(★★★☆) Union-Find のマージ過程を表す木
(★★★☆) Cartesian Tree
(★★★☆) Auxiliary Tree
(★★★☆) Inclusion Tree

その他の問題

(★★★☆) 強平衡二分木の Distance Frequency Table
(★★★☆) DSU on Tree
(★★★☆) 動的直径
(★★★☆) 動的 rerooting
(★★★★) Level Ancester

その他 (OTHERS)

その他のアルゴリズムです

入出力

(★★★★) Fast IO

グリッド

(★☆☆☆) グリッドの 4 近傍, 8 近傍
(★☆☆☆) ハニカムの 6 近傍

不等式の処理

(★☆☆☆) 負数にも対応した floor, ceil
(★★☆☆) x^K <= N となる最大の整数 x

ソート

(★☆☆☆) クイックソート
(★☆☆☆) マージソート
(★☆☆☆) ヒープソート
(★☆☆☆) 計数ソート
(★☆☆☆) 挿入ソート
(★☆☆☆) 選択ソート
(★☆☆☆) バブルソート
(★☆☆☆) シェルソート
(★☆☆☆) コムソート
(★☆☆☆) ボゴソート

その他

(★★★★) ACL
(★★☆☆) XorShift, ランダムシャッフル
(★★☆☆) タイマー
(★★☆☆) サイコロ
(★★☆☆) 曜日
(★★★☆) 四面体 (AOJ 2060)

コードテンプレート

License

These codes are licensed under CC0.

Name		Name	Last commit message	Last commit date
DataStructureAdvanced		DataStructureAdvanced
DataStructureBasic		DataStructureBasic
DataStructureSegment		DataStructureSegment
Geometry		Geometry
Graph		Graph
MathCombinatorics		MathCombinatorics
MathLinearAlgebra		MathLinearAlgebra
MathNumberTheory		MathNumberTheory
MathPolynomial		MathPolynomial
NetworkFlow		NetworkFlow
Optimization		Optimization
Others		Others
Search		Search
String		String
Tree		Tree
LICENSE		LICENSE
README.md		README.md
template_atcoder.cpp		template_atcoder.cpp
template_minimum.cpp		template_minimum.cpp

Latest commit

History

Folders and files

Repository files navigation