Wiki

競技プログラミングをするときのまとめ。

基本BASIC

テンプレートtemplate

名称 問題 計算量
テンプレート -

アルゴリズムALGORITHM

グラフgraph

名称 問題 計算量
BFS 幅優先探索(2次元格子) $O(V + E)$
Dijkstra 単一始点最短路 $O(E\log V)$
Warshall-Floyd 全点対間最短路 $O(V^{3})$
Prim 最小全域木 $O(E\log V)$
Kruskal $O(E\log E)$
Primal Dual 最小費用流 $O(FE\log V)$
Dinic 最大流 $O(V^{2}E)$
Bipartite Matching 二部マッチング $O(VE)$
Topological sort トポロジカルソート $O(E+V)$
Strongly Connected Components 強連結成分分解 $O(E+V)$

木tree

名称 問題 計算量
Tarjan 最小共通祖先 構築 $O(V\log V + E)$
クエリ $O(\log V)$
Centroid Path Decomposition 重心分解 $O(E)$
木の直径 $O(E)$
木の高さ $O(E)$

数学mathematica

名称 問題 計算量
組み合わせ
写像12相		 nCr, 逆元
エラトステネスの篩 素数列 $O(N\log \log N)$
繰り返し二乗法 べき乗 $O(\log N)$
素因数分解 $O(\sqrt {N})$
多倍長演算 -

幾何geometory

名称 問題 計算量
テンプレート -

データ構造CONTAINER

配列array

名称 問題 計算量
1 次元累積和 区間の和 構築 $O(N)$
クエリ $O(1)$
2 次元累積和 区間の和 構築 $O(WH)$
クエリ $O(1)$

木tree

名称 問題 計算量
Segment Tree 区間加算,最小,最大,和 クエリ $O(\log N)$
Binary Indexed Tree 区間の和 クエリ $O(\log N)$
Union Find Tree 集合演算 構築 $O(N)$
クエリ $O(\alpha)$
RBST 平衡二分探索木 クエリ $O(\log N)$
Wavelet Matrix Wavelet 行列 クエリ $O(\log N)$

文字列string

名称 問題 計算量
Rolling Hash 一致判定, LCP 構築 $O(N)$
クエリ $O(\log N)$
Suffix Array いろいろ 構築 $O(N \log N)$

使えそうな標準関数USEFUL FUNCTION

C++

関数 機能
*max_element(v.begin(), v.end()) 最大値
*min_element(v.begin(), v.end()) 最小値
count(v.begin(), v.end(), x) 配列中の $x$ の個数
accumulate(v.begin(), v.end(), 0) 配列の総和
sort(v.begin(), v.end();
v.erase(unique(v.begin(), v.end()), v.end())		 配列中の重複要素削除
lower_bound(v.begin(), v.end(), x) $v_i \le x$ である最左位置
upper_bound(v.begin(), v.end(), x) $v_i \lt x$ である最左位置
do{ ... }while(next_permutation(v.begin(), v.end())); 順列
partial_sum(v.begin(), v.end(), v.begin()) 累積和
reverse(v.begin(), v.end()) 逆順
v.erase(remove(v.begin(), v.end(), x), v.end()) 配列中の $x$ を削除
replace(v.begin(), v.end(), x, y) 配列中の $x$ を $y$ に置換

リンク集LINKS

名称 概要
オンライン整数列大辞典 整数列データベース
WolframAlpha 計算知識エンジン