各アルゴリズムに対して超簡潔なアイデアだけ示したもので、秒で思い出して実装したいときに役立つと思ってまとめました。
オーダー
$f(n) = O(g(n))$ $f(n)$は$g(n)$で上からおさえられる
$f(n) = \Omega(g(n))$ $f(n)$は$g(n)$で下からおさえられる
$f(n) = \Theta(g(n))$ $f(n)$は$g(n)$で上下からおさえられる
グラフ
最短経路
| オーダー | アイデア | |
|---|---|---|
| 単一始点最短路 (Bellman–Ford法) | $O(VE)$ | 更新出来なくなるまで全ての点を更新 V回目に更新した⇒負閉路が存在 |
| 単一始点最短路 (Dijkstra法) | $O(ElogV)$ | 負辺なしのとき 始点からの距離最小の点⇒最短経路 |
| k-最短路 | ||
| 全点対間最短路 (Warshall–Floyd法) | $O(V^3)$ | $d_{ij} = min(d_{ij}, d_{ik}+d_{kj})$ |
| 全点対間最短路 (Johnson) | ||
| 経路復元 | $O(E)$ | ゴールから近傍の点の始点からの最短距離とコストでルート判別 |
| 経路復元 | $O(V)$ | 更新時、ひとつ前の頂点を記録 |
全域木
| オーダー | アイデア | |
|---|---|---|
| 最小全域木 (Prim法) | $O(ElogV)$ | 領域から最短の点 |
| 最小全域森 (Kruskal法) | $O(ElogV)$ | 最短順に辺を追加、閉路を作らないように注意 |
| 最小直径全域木 (Cuninghame-Green) | ||
| 最小全域有向木 (Chu-Liu/Edmonds) | ||
| 最小シュタイナー木 (Dreyfus-Wagner) |
フロー・カット
| オーダー | アイデア | |
|---|---|---|
| 最大流 (Ford-Fulkerson) | O(FE) | 最大流-最小カット定理 |
| 最大流 (Edmonds-Karp) | ||
| 最大流 (Dinic) | ||
| 最大流 (Goldberg-Tarjan) | ||
| 無向グラフの全域最小カット (Nagamochi-Ibaraki/Stoer-Wagner) | ||
| Gomory-Hu 木 | ||
| 最小費用流 (Primal Dual) |
マッチング
二部グラフの最大マッチング
二部グラフの最小重み最大マッチング
二部グラフの辺彩色
最大マッチング
最小重み最大マッチング
NP困難
巡回セールスマン問題
ハミルトン閉路問題
連結成分
関節点，二重頂点連結成分分解
橋，二重辺連結成分分解
強連結成分分解
ツリー
木の同型性判定
オフライン最小共通先祖 (Tarjan)
木の高さ
木の直径
周遊路
有向オイラー路
無向オイラー路
有向中国人郵便配達問題
無向中国人郵便配達問題
最短ハミルトン路
その他
トポロジカルソート
グラフの同型性判定
データ構造
Union Find
$O(α(n))$
同グループかどうか⇔同じ根かどうか
キーワード
par rank init(n) find(x) unite(x,y) same(x,y)
二部探索木
二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜
AVL木 赤黒木
Splay木
Treap
区分木
Fenwick木
Range Minimum Query
セグメント木
| オーダー | アイデア | |
|---|---|---|
| セグ木 | $O(logn)$ | 完全二分木で区間管理 |
| 遅延セグ木 | $O(logn)$ | 区間更新を遅延配列に保存し、ノードにアクセスしたとき更新する |
| BIT/Fenwick Tree | $O(logn)$ | 累積和＋セグ木をビット演算使って実装 |
k 番目の値を高速に取り出せるデータ構造のまとめ - BIT上二分探索や平衡二分探索木など
文字列
Z algorithm
LCP(longest common prefix)
一番後ろまで探索した最初と最後を覚えて、探索開始位置をなるべく後ろにずらす
基本操作
std::string の基本操作
文字列検索
単一パターン検索 (Shift And)
単一パターン検索 (Knuth-Morris-Pratt)
単一パターン検索 (Boyer-Moore)
複数パターン検索 (Aho-Corasick)
二次元パターン検索 (Baker-Bird)
文字列検索その他
正規表現
ワイルドカードマッチング
文字列系データ構造
Directed Acyclig Word Graph
Trie
Suffix Array (Larsson-Sadakane)
文字列処理その他
最長繰り返し部分文字列(Karp Miller Rosenberg)
二乗判定
最長回文 (Manacher)
再帰下降型構文解析 ( LL(1) )
DP
n次元配列で再帰的に状態管理
平面幾何
平面幾何の基本要素
点の進行方向 (ccw)
直線・線分
交差判定など
距離など
多角形
端点
点-多角形包含判定
多角形の面積
多角形の摂動変形
単純多角形の三角形分割 (耳分解)
凸多角形
凸包 (Andrew's Monotone Chain)
凸性判定
凸多角形の切断
凸多角形の共通部分
凸多角形の直径
凸多角形の端点
点-凸多角形包含判定
幾何グラフ
ドロネー三角形分割
線分アレンジメント
可視グラフ
線分交差問題 (嘘平面走査)
線分併合
点位置決定 (スラブ分解)
領域探索 (kd 木)
最近点対
双対変換
線分串刺し直線
直線アレンジメント走査
未整理
空間幾何
空間幾何の基本要素
最小包含球 (move-to-front heuristics)
ソート
クイックソート
k 番目の要素の選択
マージソート
バブルソートの交換回数
計数ソート
整数
| 型 | 2 | 10 |
|---|---|---|
| int | $-2^{31}$ 〜 $2^{31}$ | $-2.1 \times 10^9$〜$2.1 \times 10^9$ |
| unsigned int | $0$ ～ $2^{32}$ | $0$〜$4.3 \times 10^9$ |
| long long | $-2^{63}$ ～ $2^{63}$ | $-9.2 \times 10^{18}$〜$9.2 \times 10^{18}$ |
| unsigned long long | $0$ ～ $2^{64}$ | $0$〜$1.8 \times 10^{19}$ |
| 型 | 範囲 |
|---|---|
| 多倍長整数 karatuba法 | |
| 区間ふるい | |
| 確率的素数判定 | |
| ガウス素数判定 | |
| 法演算 | |
| ユークリッドの互除法 | |
| 逆元 | |
| 線型連立合同式 | |
| べき剰余 | |
| ヤコビ記号 | |
| 平方剰余 | |
| 数論的関数 | |
| オイラーのφ関数 | |
| メビウスのμ関数 | |
| カーマイケルのλ関数 |
有理数
Stern-Brocot 木
有理数型
行列演算
行列
LU分解
固有値・固有ベクトル
最適化
上凸関数の最大値 (黄金探索法)
単調関数の零点 (二分法)
線型計画法 (二段階単体法)
無制約非線型最適化 (準Newton法)
割り当て問題 (ハンガリアン法)
その他
高速フーリエ変換
典型動的計画法
連鎖行列積問題
最長増加部分列 ( O(n log n) )
最長増加部分列 ( O(n^2) )
最長共通部分列 ( O( (n+r) log n ) )
最長共通部分列 ( O(n^2) )
硬貨両替問題
配列アラインメント (Needleman-Wunsch)
部分集合和問題
ナップサック問題
典型バックトラック
支配集合問題
その他
さいころ
ポーカー役判定
区間が覆う長さ
対和からの復元
ハニカム構造
日付関連
2充足可能性問題
半順序集合の最小鎖分割
安定マッチング
区間スケジューリング
brainfuckインタプリタ
探索
深さ優先探索
幅優先探索
両側探索
A^* 探索
反復深化
二部グラフの最小点被覆、最大安定集合 (最大独立集合)、最小辺被覆を総整理！
実世界で超頻出！二部マッチング (輸送問題、ネットワークフロー問題）の解法を総整理！
ツリーの重心分解 (木の重心分解) の図解