Luzhiled's memo - 西尾泰和の外部脳

Luzhiled's memo

Luzhiled's memo

簡潔に計算量の話がまとまってて便利なのでよく参照する

グラフ

オイラー路(Eulerian-Trail)

グリッド上の幅優先探索(Grid-BFS)

ハンガリアン法(Hungarian)

二部グラフの最大マッチング(Bipartite-Matching)

二部グラフの最大マッチング(Hopcroft-Karp)

二重辺連結成分分解(Two-Edge-Connected-Components)

二重頂点連結成分分解(Bi-Connected-Components)

全点対間最短路(Warshall-Floyd)

単一始点最短路(Bellman-Ford)

単一始点最短路(Dijkstra)

単一始点最短路(SPFA)

強連結成分分解(Strongly-Connected-Components)

彩色数(Chromatic-Number)

最大クリーク(Maximum-Clique)

最大流(Dinic)

最大流(Ford-Fulkerson)

最大流(Push-Relabel)

最大独立集合(Maximum-Independent-Set)

最小全域有向木(Chu-Liu/Edmond)

最小全域木(Borůvka)

最小全域木(Kruskal)

最小全域木(Prim)

最小流量制限付き最大流

最小費用流(Primal-Dual)

橋/関節点(LowLink)

データ構造

BIT(Binary-Indexed-Tree)

Convex-Hull-Trick-Add-Monotone

Link-Cut木部分木クエリ(Link-Cut-Tree-Subtree)

Link-Cut木(Link-Cut-Tree)

ウェーブレット行列(Wavelet-Matrix)

スパーステーブル(Sparse-Table)

スライド区間の昇順k個の和(Priority-Sum-Structure)

セグメント木(Segment-Tree)

トライ木(Trie)

マージ可能ヒープ(Skew-Heap)

列の平方分割(Sqrt-Decomposition)

平衡二分探索木(RBST)

平衡二分探索木(Red-Black-Tree)

永続配列(Persistent-Array)

素集合データ構造(UnionFind)

文字列

ローリングハッシュ(Rolling-Hash)

接尾辞配列(Suffix-Array)

最長共通接頭辞(Z-Algorithm)

最長回文(Manacher) 回文

複数文字列検索(Aho-Corasick)

木

HL分解(Heavy-Light-Decomposition)

全方位木DP(ReRooting)

最小共通祖先(Doubling-Lowest-Common-Ancestor)

木の直径(Tree-Diameter)

木の重心分解(Centroid-Decomposition)

根付き木に変換(Convert-Rooted-Tree)

数学

Mod-Int

べき乗(Mod-Pow)

オイラーのφ関数(Euler’s-Phi-Function)

オイラーのφ関数テーブル(Euler’s-Phi-Function-Table)

ベル数(Bell-Number)

ラグランジュ補間(Lagrange-Polynomial)

二項係数(Binomial)

二項係数テーブル(Binomial-Table)

任意mod畳み込み(Arbitrary-Mod-Convolution)

分割数(Partition)

分割数テーブル(Partition-Table)

商列挙(Quotient-Range)

形式的冪級数(Formal-Power-Series) 形式的べき級数

拡張ユークリッドの互除法(Extended-Euclidean-Algorithm) 拡張ユークリッド互除法

第2種スターリング数(Stirling-Number-Of-The-Second-Kind)

約数列挙(Divisor)

素因数分解(Prime-Factor)

素数テーブル(Prime-Table)

素数判定(Is-Prime)

組合せ(Combination)

行列演算(Matrix)

進数変換(Convert-Base)

階乗(Factorial)

離散対数問題(Mod-Log)

高速フーリエ変換(Fast-Fourier-Transform)

動的計画法

Divide-And-Conquer-Optimization

Monotone-Minima

スライド最小値(Slide-Min)

一次元累積和(Cumulative-Sum)

二次元累積和(Cumulative-Sum-2D)

個数制限付きナップサック(Knapsack-Limitations)

最大長方形(Largest-Rectangle)

最適二分探索木(Hu-Tucker)

最長増加部分列(Longest-Increasing-Subsequence)

メモ

ダブリング

燃やす埋める問題燃やす埋める

その他

Mo’s Algorithm

Offline-Dynamic-Connectivity

辺の追加削除クエリがオフラインで与えられる場合は、Undo可能Union-Findを用いることで効率的に処理できる。

座標圧縮(Compress)

アルゴリズム