Kyopro Encyclopedia of Algorithms

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /#noredirect を利用してください。

これは競プロの知見を収集するための査読付きの半共有 wiki である。 アルゴリズムについての説明が中心となっている。なお、データ構造については scrapbox.io/data-structures (通称: デ wiki) を利用するのがよいだろう。

個人ブログの記事として情報を書くと属人性が高すぎ、古い記事のメンテのコストが高く、記事が不正確なまま残りやすいという問題があった。一方で誰でも自由に編集できる共有 wiki であると属人性が低すぎ、誰が書いたのかが分かりにくいため適切なクレジットが行なわれず、また記事の正確性も担保されないという問題があった。 そこでこの半共有 wiki は、GitHub 上のプルリクエストとレビュープロセスという管理形態を用いて、これらの問題の解決を目指している。 もし興味があれば kmyk/algorithm-encyclopedia から編集に参加してほしい。


Aho-Corasick法
Aho-Corasick法とは、複数のパターン文字列をまとめて扱える文字列検索アルゴリズムのひとつ。まず前処理として、固定された $k$ 個のパターン文字列 $P_0, P_1, P_2, \dots, P _ {k-1}$ たちから Trie 木を作り、その上に適切に辺を張って $O(\sum \vert P_i \vert)$ でオートマトンを作る。その後与えられたテキスト文字列 $T$ に対して $O(\vert T \vert)$ で検索を行う。
Bellman-Ford 法
Bellman-Ford 法とは、単一始点最短経路問題を解くアルゴリズムのひとつ。負辺があっても動作する。計算量は $O(\vert V \vert \cdot \vert E \vert)$ である。
Boyer-Moore-Horspool法
Boyer-Moore-Horspool 法は、文字列検索アルゴリズムのひとつ。Boyer-Moore 法を簡略化したものである。
Boyer-Moore法
Boyer-Moore 法は、文字列検索アルゴリズムのひとつ。どこで不一致が起きたらパターン文字列をいくつずらせばよいかの情報を $O(\vert P \vert)$ かけて構築しておき、パターン文字列をその末尾から順にテキスト文字列と照合していく。ランダムな文字列に対しては $O(\vert T \vert / \vert P \vert)$ だが、最悪ケースでは $O(\vert P \vert \cdot \vert T \vert)$ かかる。
Chu-Liu/Edmonds' algorithm
Chu-Liu/Edmonds' algorithm とは、与えられた辺重み付き有向グラフ $G$ と頂点 $r$ に対し、$r$ を根とする最小全域有向木を $O(V E)$ で求めるアルゴリズムである。
DSU on tree
DSU on tree とは、それぞれの頂点 $x$ に可換 monoid $(M, +, 0)$ の要素の重み $a_x$ のついた木 $T$ のそれぞれの部分木について、その部分木内の重みの総和を全体で $O(n \log n)$ で求めるアルゴリズムである。ただし、その計算の過程において、monoid 演算 $+$ がある要素 $A \in M$ と頂点 $x$ に対し $A + a_x$ という形でしか出現しないという特徴がある。
Dial's algorithm
Dial's algorithm とは、単一始点最短経路問題を解くアルゴリズムのひとつ。非負かつ最大値の小さい整数重みのグラフについてしか動作しないが、重みの最大値を $k$ として $O(k \vert V \vert + \vert E \vert)$ で動く。キューの持ち方を工夫して Dijkstra 法をさらに高速化したものになっている。0-1 BFS の一般化でもあり、$k = 1$ のときは 0-1 BFS に一致する。
Dijkstra 法
Dijkstra 法とは、単一始点最短経路問題を解くアルゴリズムのひとつ。グラフに負の辺があると動作しない。辺が非負という仮定をもとに動的計画法を利用して高速に動作し、計算量は $O(\vert E \vert \log \vert V \vert)$ などである。
Eppstein's algorithm
Eppstein's algorithm とは、与えられたグラフ $G$ の $s-t$ 歩道であって $K$ 番目に短いものを $O(K + E + V \log V)$ で求めるアルゴリズムである。
Eratosthenes の篩
Eratosthenes の篩とは、素数判定アルゴリズムのひとつ。
Euclid の互除法
Euclid の互除法とは、ふたつの自然数の最大公約数を求めるアルゴリズムのひとつ。
Garner法
Garner 法とは、中国剰余定理で存在が示されるところの $\forall i. x \equiv a_i \pmod{m_i}$ を満たす整数 $x$ について、それを別の $M$ で割った余り $x \bmod M$ を求めるアルゴリズムである。計算の過程で現われる整数の大きさが $m_i$ や $M$ の $2$ 乗程度で抑えられることを特徴とする。
Karatsuba法
Karatsuba法とは、加算の回数を増やすかわりに乗算の回数を減らすことで多項式乗算などを $O(n^{\log_2 3})$ で行なうというアルゴリズムである。
Kitamasa法
Kitamasa 法とは、$k + 1$ 項間の線型漸化式で定まる数列の第 $N$ 項を $O(k^2 \log N)$ で求めるアルゴリズムである。高速 Kitamasa 法とは異なる。
Knuth-Morris-Pratt法
Knuth-Morris-Pratt法とは文字列検索アルゴリズムのひとつ。パターン文字列 $P$ の各 prefix について最長の border (prefix かつ suffix であるような文字列) を $O(\vert P \vert)$ で求めておくことで、与えられたテキスト文字列 $T$ に対する検索を $O(\vert T \vert)$ で行う。
Knuth-Yao speedup
Knuth-Yao speedup とは、Monge な $N \times N$ 行列 $f$ に対して $\mathrm{dp}(l, r) = \min \lbrace \mathrm{dp}(l, m) + \mathrm{dp}(m + 1, r) \mid l \le m \lt r \rbrace + f(l, r)$ (ただし $l \le r$) で定まる関数 $\mathrm{dp}$ のグラフを $O(N^2)$ で求めるアルゴリズムである。
Kruskal 法
Kruskal 法とは、最小全域木を求めるアルゴリズムのひとつ。
Lagrange 補間
Lagrange 補間多項式とは、与えられた点群 $\lbrace (x_i, y_i) \mid i \lt N \rbrace$ をすべて通る ($\forall i \lt N. f(x_i) = y_i$ を満たす) ような最小次数の多項式 $f$ のことである。Lagrange 補間をするとは、この多項式を求めることである。Lagrange 補間は $O(N^2)$ あるいは $O(N \log N)$ で行なうことができる。
Manacher 法
Manacher 法とは、与えられた文字列 $S$ に対して、そのすべての位置 $i$ (ただし $0 \le i \lt \vert S \vert$) について「$S$ における $i$ 番目の文字を中心とする最長の回文の半径」をまとめて $O(\vert S \vert)$ で求めるアルゴリズムのひとつ。そのままでは奇数長の回文についてのみしか求まらない。偶数長の回文についても求めたいときは、$S$ の各文字の間にダミーの文字列を計 $\vert S \vert - 1$ 個挿入してできる文字列 $S'$ に対してもう一度 Manacher 法をすることになる。
Mo's algorithm
Mo's algorithm とは、群 $G$ の要素の列 $(a_0, a_1, \dots, a _ {N-1})$ と区間の列 $\lbrack l_0, r_0), \lbrack l_1, r_1), \dots, \lbrack l _ {Q-1}, r _ {Q-1})$ が与えられたとき、それぞれの区間中の要素の総和 $\sum _ {i \in \lbrack l_j, r_j)} a_i$ を全体で $O(N \sqrt{Q})$ あるいは $O((N + Q) \sqrt{N})$ で求めるアルゴリズムである。ただし、その計算の過程において、群の演算 $\cdot$ が要素 $A \in G$ と添字 $i$ に対し $A \cdot a_i, A \cdot a_i^{-1}, a_i \cdot A, a_i^{-1} \cdot A$ のいずれかの形でしか出現しないという特徴がある。
Monotone minima
monotone minima とは、monotone な $H \times W$ 行列に対しその各行の最小値を $O(H + W \log H)$ で求めるアルゴリズムである。
Montgomery乗算
Montgomery 乗算とは、剰余環 $\mathbb{Z}/N\mathbb{Z}$ での乗算を高速に行うアルゴリズムである。
Prim 法
Prim 法とは、最小全域木を求めるアルゴリズムのひとつ。
Rabin-Karp法
Rabin-Karp 法とは、複数のパターン文字列をまとめて扱える文字列検索アルゴリズムのひとつ。固定された $k$ 個のパターン文字列 $P_0, P_1, P_2, \dots, P _ {k-1}$ のそれぞれについて $O(\sum \vert P_i \vert)$ などをかけてハッシュ値を求めておくことで、与えられたテキスト文字列 $T$ に対し平均 $O(\vert T \vert)$ などでこれらの検索ができる。ハッシュ関数は自由だが、ローリングハッシュが使われることが多い。
SMAWK algorithm
SMAWK algorithm とは、totally monotone な $H \times W$ 行列に対しその各行の最小値を $O(H + W)$ で求めるアルゴリズムである。
Shortest Path Faster Algorithm
Shortest Path Faster Algorithm (SPFA) とは、単一始点最短経路問題を解くアルゴリズムのひとつ。Bellman-Ford 法をキューを使って定数倍高速化したものであり、優先度付きキューでなく普通のキューを使う Dijkstra 法のようなものでもある。計算量は $O(\vert V \vert \cdot \vert E \vert)$ である。
Warshall-Floyd 法
Warshall-Floyd 法とは、全点対間最短経路問題を解くアルゴリズムのひとつ。負閉路が存在するなら検出できる。定数倍の軽い $O(\vert V \vert ^ 3)$ で動く。
Yen's algorithm
Yen's algorithm とは、与えられたグラフ $G$ の $s-t$ 単純路であって $K$ 番目に短いものを $O(K V (E + V) \log V)$ で求めるアルゴリズムである。
Z algorithm
Z algorithm とは、与えられた文字列 $S$ に対して、文字列 $S$ の $i$ 文字目以降の文字列 $S\lbrack i \colon \rbrack = (S _ i, S _ {i + 1}, \dots, S _ {\vert S \vert - 1})$ を考えたときの、すべての $i$ について「$S$ と $S\lbrack i \colon \rbrack$ の最長共通接頭辞の長さ」をまとめて $O(\vert S \vert)$ で求めるアルゴリズムのひとつ。
imos 法
imos 法とは、配列の区間に対する一様なたくさんの操作をまとめて高速に処理するための手法のひとつ。先に操作の結果として起こる差分だけを書き込んでおき、後からまとめて累積和をとることにより操作を全体に作用させる。
rerooting
rerooting とは、根付きでない木 $T$ と根付き木の畳み込み $f$ (いわゆる木 DP) が与えられたとき、それぞれの頂点 $r \in T$ に対しそれを根とした根付き木 $T_r$ に対する畳み込み結果 $f(T_r)$ を $O(N)$ ですべて求めるアルゴリズムである。全方位木 DP とも呼ばれる。
weighted-union heuristic
weighted-union heuristic とは、ふたつの集まりの間で要素を移動させてひとつにまとめる操作を繰り返す際に、常に要素が少ない方から多い方へと移すようにすると計算量が落ちるというテクである。具体的には、大きさ $a$ のものを大きさ $b$ のものへと $O(a)$ かけてマージし (中身を移し) て大きさ $a + b$ のものを作るという操作を使って、大きさの合計が $n$ であるようないくつかのものをひとつにマージしてまとめたいというような状況において、合計の計算量 $O(n \log n)$ でこれが可能である。データ構造をマージする一般的なテクとも呼ばれる。
しゃくとり法
しゃくとり法とは、ふたつの添字などを交互に動かして列を走査する手法のこと。
ダブリング
ダブリングとは、前処理をしておくことによって操作を複数回繰り返した結果を高速に求めるアルゴリズムのひとつ。事前に固定された関数 $f : N \to N$ に対して、関数 $f^0, f^1, f^2, f^4, f^8, \dots, f^{\lfloor \log K \rfloor}$ を繰り返し二乗法のようにして $O(N \log K)$ で事前に求めておく。すると、クエリとして与えられた $x \in N$ と $K$ 以下の自然数 $k$ に対して、$f^k(x)$ を $O(\log k)$ で求めることができる。これがダブリングである。ただし $N$ とは集合 $\lbrace 0, 1, 2, \dots, N - 1 \rbrace$ のことであり $f^k : N \to N$ は関数 $f^k(x) = \underbrace{f(f(\dots f(} _ {k ~\text{times}} x) \dots))$ のことである。
二分探索
二分探索とは、ソート済みの列に対する探索アルゴリズムのひとつ。探索すべき区間の中央の要素を調べることで探索すべき区間の長さを半々にし、区間の長さ $N$ に対し $O(\log N)$ で位置を特定する。
動的計画法
動的計画法とは、アルゴリズムの分類のひとつ。対象となる問題を複数の部分問題に分割して、部分問題の答えを記録しながらそのすべてを解くという形のアルゴリズムの総称である。動的計画法に分類されるようなアルゴリズムの実装方法の典型例として、配列をループで埋めていく実装や、メモ化を伴なう再帰による実装がある。
包除原理
包除原理とは、有限集合 $A, B$ について成り立つ $\vert A \cup B \vert = \vert A \vert + \vert B \vert - \vert A \cap B \vert$ という等式のこと。つまり、有限集合 $A, B$ の和集合 $A \cup B$ の要素数を求めるには、$A$ の要素数と $B$ の要素数の和から共通部分 $A \cap B$ の要素数を求めればよいという事実のことである。
半分全列挙
半分全列挙とは、組合せについて処理するときに使えるテクニックのひとつ。すべての要素を考えたときの組合せの全体は列挙するには多すぎるが、半分程度の数の要素に制限して考えたときの組合せであれば列挙できる、という場合に利用可能である。要素の全体をそれぞれ半分程度の大きさのふたつのグループに分け、それぞれのグループについて組合せを全列挙し、それらふたつの結果を組み合わせて全体に対する結果を得る。そのまま全列挙したときの計算量が $O(f(N))$ であるとき、半分全列挙を行ったときの計算量はたとえば $O(\sqrt{f(N)})$ や $O(\sqrt{f(N)} \log f(N))$ などになる。これを利用するアルゴリズムの代表的なものに baby-step giant-step がある。
幅優先探索
幅優先探索とは、グラフや木構造の上の探索に用いられるアルゴリズムのひとつ。
平方分割
平方分割とは、長さ $N$ の列を長さ $O(\sqrt{N})$ の列 $O(\sqrt{N})$ 個に分割して処理する手法のこと。
座標圧縮
座標圧縮とは、与えられた長さ $N$ の整数列 $a$ から、長さ $N$ の自然数列 $b$ であって要素の順序関係が $a$ と同じでかつ最大値 $\max_i b_i$ が最小であるような $b$ を作ること。ただし「要素の順序関係が同じ」とは、任意の $i, j$ に対し $a_i \le a_j \leftrightarrow b_i \le b_j$ を満たすことを言う。このような $b$ は常に一意に存在し、単純な方法により $O(N \log N)$ で構成できる。
数論変換
数論変換とは、特定の素数 $p$ による剰余環 $\mathbb{Z}/p\mathbb{Z}$ の上で行なわれる離散Fourier変換と同様の変換のこと、あるいはこの変換を高速Fourier変換と同様に $O(n \log n)$ で行うアルゴリズムのことである。
深さ優先探索
深さ優先探索とは、グラフや木構造の上の探索に用いられるアルゴリズムのひとつ。
累積和
累積和とは、ある数列の接頭辞の総和たちを要素とする数列のこと。長さ $N$ の数列 $a = (a_0, a_1, \dots, a _ N)$ に対する累積和とは $b_i = \sum _ {j \lt i} a_i$ であるような長さ $N + 1$ の数列 $b$ である。数列の要素が群の要素であるときには区間 $\lbrack l, r)$ の総和 $\sum _ {i \in \lbrack l, r)} a_i = b_r - b_l$ を $O(1)$ で計算することなどに用いることができる。
繰り返し二乗法
繰り返し二乗法とは、与えられた数 $a$ と自然数 $n$ に対し累乗 $a^n$ を $O(\log n)$ 回の乗算で求めるアルゴリズムのひとつ。$1 = a^0, a = a^1, a^2 = a \cdot a, a^4 = a^2 \cdot a^2, a^8 = a^4 \cdot a^4, \dots$ を計算し、これらを適切に掛け合わせることで、合計 $O(\log n)$ 回の乗算で $a^n$ が求まる。競技プログラミングにおいては行列などに対してもよく用いられる。
重心分解
重心分解とは、木を分解する手法のひとつである。木からその重心を削除することを再帰的に行う。重心の削除のたびに木の大きさが半分以下になる。分解の過程に沿って重心だった頂点の集合に木構造を入れたとき、元々の木の頂点数を $n$ とすると分解されてできた木の高さが $O(\log n)$ になることを特徴とする。
重軽分解
重軽分解とは、根付き木をパスの集合へ分解するテクニックのひとつである。根から始まる最も長いパスをひとつ選んで削除することを再帰的に行う。元々の根付き木上の親子関係によって分解されたパスの集合に木構造を入れたとき、元々の木の高さを $h$ とすると分解されてできた木の高さが $O(\log h)$ になることを特徴とする。
高速 zeta 変換
高速 zeta 変換とは、$n$ 要素の集合 $X$ の部分集合から可換 monoid $M$ への関数 $f : \mathcal{P}(X) \to M$ が与えられたとき、関数 $g(s) = \sum _ {s \subseteq T} f(T)$ の全体を $O(n 2^n)$ で求めるアルゴリズムである。累積和の $n$ 次元への一般化と理解できる。
高速Fourier変換
高速Fourier変換とは、離散Fourier変換を $O(n \log n)$ で行なうアルゴリズムである。高速な多項式乗算の実装などに用いられる。
高速Kitamasa法
高速 Kitamasa 法とは、$k + 1$ 項間の線型漸化式で定まる数列の第 $N$ 項を $O(k \log k \log N)$ で求めるアルゴリズムである。Kitamasa 法とは異なる。