TODO
概要 †
- プロコンで考えるべきこと
- 解いた問題数を増やすのは良い事なんだけど、解いた問題数を増やすためだけに、簡単な問題を解きまくるのってすげえ時間の無駄
記録 †
下位ページ †
目次 †
参考 †
勉強すべきこと †
ライブラリ †
| アルゴリズムとリンク | 概要 | 計算量 |
| 二分探索 | 単調関数の境界面をlog(N)で計算。Nは探索空間。 | |
| Union Find | 「xとyの集合をまとめる」「xとyの集合が同じか判定」分割はできないのが重要な制約 | 構築O(n), union, findは両方O(A(n)) |
| BFS on tree | 幅優先探索で頂点rを始点とする最短距離を求める。 | O(V) |
| Bellman Ford | 1点から全点への最小コスト。負の閉路がない連結グラフを入力。あった場合は検出できる。 | O(V E) |
| Johnson | | 前処理 O(V E)． 中間処理 O(V E log V)． 後処理 O(V^2)． |
| Warshall Floyd | 全点から全点への最小コスト。 | O(V^3)、だが漸化式が単純なので速い。 |
| Dijkstra | 1点から全点への最小コスト。コストは正でなければならない。 | O(E log V) |
| K Shortest | | O(k E log V) |
| Prim | 最小重み無向全域木＝重みつき無向グラフの全域木の中で、重みが最小のものを求める。根は指定する。 | O(E log V) |
| Kruskal | 最小重み無向全域森＝重みつき無向グラフの全域木の中で、重みが最小のものを全て求める。 | O(E log V + A(r)) |
| Cuninghame-Green | 最小直径無向全域木＝重みつき無向グラフの全域木の中で，直径が最小のものを求める | 前処理O(V^3), 端点計算O(VE) |
| Chu-Liu/Edmond | 最小重み有向全域木＝重み付き有向グラフの全域木の中で、重みが最小のものを求める。根は指定する。 | O(VE) |
| Dreyfus-Wagner | 最小重みシュタイナー木＝頂点群Tを通る木の中で、重みが最小のものを求める。 | t=11が限界。時間O(n 3^t + n^2 2^t + n^3)．空間計算量 O(n 2^t)． |
| Ford Fulkerson | 有向最大流 | 辺容量が1ならこれ。F(E MAXFLOW) |
| Edmonds-Karp | 有向最大流 | O(E^2 V) |
| Dinic | 有向最大流 | O(E V^2) |
| Goldberg-Tarjan | 有向最大流 | O(V^2 sqrt(E)) |
| Nagamochi-Ibaraki | 無向グラフ最小カット | O(VE + V log V) |
| Primal Dual | 最小費用流＝費用と容量が定義された有向単純グラフの2頂点と、そこに品物を流す量が与えられた際，流すために掛かる総費用を最小にするためにはどのように輸送するとよいのかを決定する問題 | O(V^2 U C) Uは費用の総和、Cは容量の総和 |
| Gomory-Hu | 最大流 | O(V MAXFLOW) |
| 木の高さの最大値 | 木の直径が最小になるような根を計算 | O(E) |
| Double Sweep＝木の直径 | 葉と葉の最大距離を計算 | O(E) |
| 有向オイラー路存在判定 | すべての辺をちょうど一度通る閉路があるか判定 | O(E) |
| 無向オイラー路存在判定 | すべての辺をちょうど一度通る閉路があるか判定 | O(E) |
| 無向中国人郵便配達問題 | | O(o m log n + o^2 2^o), o=18が限度 |
| 最短ハミルトン路 | すべての頂点をちょうど一度通る閉路を求める。判定もNP困難。 | O(V^2 2^V), V=18が限度。全探索はO(V!)なので少し落ちてる |
| Fenwick Tree | 配列に、ある要素にvを足す・ある範囲の和を求める、をlog nで計算。 | 構築O(n)、位置和更新O(log n)、範囲和参照O(log n) |
| Segment Tree（和） | 配列に、ある範囲にvを足す・ある範囲の和を求める、をlog nで計算。Fenwickの上位互換 | 構築O(n)、範囲和更新O(log n)、範囲和参照O(log n)。範囲和のためには遅延評価を実装する必要あり。 |
| Segment Tree（最小値・最大値。Starry Sky木） | | 範囲和更新O(log n)、範囲最大最小参照O(log n)。範囲和のためには遅延評価を実装する必要あり。 |
| Segment Tree（加群） | | 範囲一般和更新O(log n)、範囲一般和参照O(log n)。範囲和のためには遅延評価を実装する必要あり。 |
| Interval Tree | 与えられた点 x を含む半開区間を全列挙, 与えられた半開区間 [a,b) と重なる半開区間を全列挙 | 構築O(n log n)．クエリO(log n + k), kはヒット数 |
| レンジ木 | | |
| AVL木 | 平衡二分木 | |
| Splay木 | 平衡二分木 | |
| 赤黒木 | 平衡二分木 | |
| Treap木 | 平衡二分木 | |
| Next Conmination | nCrのループを回す | 前処理O(n log n), 点クエリO(log n + k), 区間クエリO(log n + k)、kはヒット数 |
| Prime(エラトステネス・区間篩の構築) | エラトステネスを用いて、素因数分解する | 構築O(n log n)、参照O(log n)、素因数分解・約数計算O(log n) |
| Prime(構築なし) | 2^64までのオンライン素数判定 | O(1)*200 |
| RMQ | 配列を与えて構築する→範囲クエリを与えると最小値を返すようになる。構築後は変更不能 | 構築O(n log n)、クエリO(log log n) |
| Linear Programming | | |
| Tarjan's OLCA | グラフを構築すると、(u, v)の最小共通祖先をO(1)で計算できるようになる | 構築O(E A(V))、参照O(1) |
| Big Num | 多倍長演算 | |
| Rational | 分数 | |
| Mod | 割り算、combinationはmodが素数を前提。 | 法での累乗O(log n)、等差数列和O(log n)、階乗O(n)、掛け算、足し算、割り算を安全に計算 |
| Geometry | 幾何ライブラリ | 直線・線分・点間の距離、多角形と線分の包含判定、点群の凸包O(n log n)、凸多角形の直線切断O(n) |
| Interval Tree | | |
| imos法 | 範囲和更新から累積和構築 | 範囲和O(1), 累積和構築O(n)、構築後累積和参照O(1) |
| 範囲和 | [i, j)の累積和 | 累積和構築O(n), 範囲和参照O(1) |
| 二次元範囲和 | 二次元で[i, j)から[h, k)までの累積和 | 累積和構築O(n), 範囲和参照O(1) |
アルゴリズム各論 †
バケット法 †
- バケット法=平方分割＝sqrt(n)分木
- 範囲を扱う時に、平方に分割して記憶することで前処理O(n)、各クエリO(sqrt(n))を実現
- 応用力が高く、自分で考える部分が大きい。各バケットが2分探索木やBITを持ってたりする。
- 応用範囲は、バケット法>セグメント木。
- 速度はバケットO(sqrt(n))<セグメント木O(log n)
BIT・セグメント木 †
- 「データ型T, 二項結合演算op、単位元T0」が定義できると、構築O(n), 更新O(log n), 範囲参照O(log n)のデータ型が定義可能
- Fenwickは、「点更新」「範囲参照」
- Segment Treeは、「範囲更新」「範囲参照」（範囲更新はlazyによって実現）
| op | T | T0 |
| max | int | 0 |
| min | int | inf |
| (+) | int | 0 |
| (*) | int | 0 |
| sort.(++) | [int] | [] |
| ^（累乗） | int | 1 |
| and | bool | 1 |
| or | bool | 0 |
| xor | bool | 0 |
| (++) | string | "" |
| 集合和 | [int] | [] |
| 集合積 | [int] | 全体集合 |
| gcd | int | 0 |
| lcd | int | 1 |
- Fenwick Tree=BIT=Binary Indexed Tree
- セグメント木
- 応用力が高く、自分で考える部分が大きい。
- 平衡処理が必要ないので、計算量・実装量的に有利
- 使う時
- クエリ
- （平面）走査系
- DP加速＝漸化式に区間minが入ってるなど
- 具体的には？
| op | 使い道 |
| max, min | RMQ、DP加速 |
| (+) | DP加速、オイラーツアー |
- PekempeyさんのシンプルなSegment Tree。定数倍で遅かったら使おう。
const int N = 1 << 18;
typedef pair<long double, long double> P;
P seg[N * 2];
// cx+d . ax+b -> c(ax+b)+d = (ac)x+(bc+d)
P merge(P a, P b) {
return{ a.first * b.first, a.second * b.first + b.second };
}
void update(int k, long double a, long double b) {
k += N - 1;
seg[k] = { a, b };
while (k > 0) {
k = (k - 1) / 2;
seg[k] = merge(seg[k * 2 + 1], seg[k * 2 + 2]);
}
}
グラフ理論 †
- 頂点n辺n-1かつ連結なら必ず木構造
- 木構造はどこから見ても木構造、おぼえましたし
- このスライドめっちゃいい
- 本「離散凸解析の考え方」
- 葉を指定した最小全域木→Kruskalの変形
- 分散最小全域木、比最小全域木などは、パラメータ化して何かを止めると凸にする
- k-th最小全域木
| 名前 | 計算量 | アルゴリズム | 特徴 |
| ベルマンフォード法 | O(VE) | 前提：負の閉路がない連結グラフ。全辺を見て、現状より辺を通じたほうが良ければ更新。更新するものがなくなるまで行う | 負のコストを許容。負の閉路がなければOK。また、すべての負の閉路の検出も可能（更新が規定回数で止まらなかったら） |
| ダイクストラ法 | O(ElogV) | 前提：負のコストがない連結グラフ。コスト最小の未確定頂点を選び、そこから行ける頂点を更新して未確定頂点とする。これを未確定頂点がなくなるまで続ける。priority queueを使って実装する場合は「確定」の概念が明示的には入らず、コストが同じなら一番初めに処理した頂点が強いことで弾く | 負のコストを許容しない。 |
| 経路復元 | O(E)かO(V) | O(V)は以前の道を記憶する。O(E)は以前の道をあとから探す | E: d[j]=d[k]+cost[k][j]なるkを探す。V: 更新時prev[j]を記録する。 |
| プリム法 | O(ElogV) | 統合頂点群から未統合頂点への最小距離をメモする。未統合頂点のうち統合頂点群に最も近い頂点を探す。統合頂点群に追加する。頂点追加によって、最小距離が変わるので更新する。 | 最も近い頂点を貪欲的に追加する方法 |
| クラスカル法 | O(ElogV) | 辺をコストの小さい順に並べる。コストの低い順に見て、閉路ができないならば連結していく。閉路ができることは連結先と連結元がUnion-Findで同一かによって検知可能 | 最もコストの小さい辺を貪欲的に選び続ける方法 |
オイラーツアー †
- オイラーツアーはDFS順序とも呼ばれる。
- bfsの経路を添え時に直したもの
- 木を列で扱える！
- しかも、各頂点番号が最初に登場するインデックスと最後に登場するインデックスの間が部分木に。
- 上から下への辺の重みも、上から下への経路で無向グラフ辺を足したものとして表現できる。
- セグメント木などのデータ構造を扱えるようになる！
- 部分木のコストを変える・部分木のコストのsum, min, maxを求める。（無向辺のコストを両方向正にして実現）
- 辺（上から下へに限定）のコストを変える・u から v へのパスのコストのsum, min, maxを求める（無向辺のコストを片方1片方-1にして実現）
1 2 3 2 3 2 1 2 3 2 1 // オイラーツアー
1 [2 3 2 3 2] 1 2 [3] 2 1 // 頂点に対応する部分木
1 [2 3 2 3 2 1 2 3] 2 1 // 最小要素の判定区間→1が最小で、この区間で1を持つ頂点がLCA
DAGからフロンティア †
- フロンティア法の長い解説
- DAG
- Directed acyclic graphとは、閉路のない有向グラフ。
- トポロジカルソート
- BDD
- ROBDD
- Create Reduced Ordered Binary Decision Diagram (ROBDD)
- 変数に全順序関係が定義されている＆限界まで簡約化されている
- BDDというとROBDDを指すことも。
- 構築は二つのルールを適用し続ければROBDDになる。冗長な接点を全て削除。等価な接点を全て共有。
- BDD 同士の演算 (Family Algebra) and, or, xor, not, ... みたいな色々な BDD 同士の演算ができる，便利
- 組合せ集合（集合族）を表現する ZDD（Zero-Suppressed BDD）
- 「計算爆発お姉さん」の問題が、O(nB)(n: fのビット数、B: BDDの頂点数)
- お姉さん本
- 集合族を表現するZDD
- BDDと違うのは、頂点削除のルールのみ
- BDDは「ここが0でも1でも結果が変わらない→頂点削除」
- ZDDは「ここが1だったらどうやっても結果が0になる→頂点削除」
- 疎な部分集合族を表現するのに適している
- BDD同様、ZDD 同士の演算がそのままできる（Family Algebra）
- フロンティア法
- ZDDはめちゃめちゃメモリ食う（1頂点当たりO(V)）
- 実は、フロンティアの連結と次数だけ覚えれば十分
- その他
- 文字列集合を表現する SeqBDD (Sequence BDD)
- 置換の集合を表現する πDD (PiDD, Permutation DD)
メモ化再帰 †
- 返り値をメモするタイプの再帰（異常条件→メモ条件→遷移→メモ→return）
int f(int i, int j) {
if (i < 0 || j < 0 || i >= n || j >= n) return 0; // 入力異常条件
if (memo.count(P(i, j))) return memo[P(i, j)]; // もう答え知ってる
int ret = 0;
rep(d, 4) ret+=f(i+di[d], j+dj[d]);
memo[P(i, j)] = ret;
return ret;
}
- 一度来たところをメモするタイプの再帰（異常条件→メモ条件→メモ→自分→遷移→return）
int f(int i, int j) {
if (i < 0 || j < 0 || i >= n || j >= n) return 0; // 入力異常条件
if (field[i][j] != 'o') return 0; // 探し物じゃない
if (memo.count(P(i, j))) return 0; // もう来てた
memo[P(i, j)] = true; // 次からは来ない
int ret = 0;
ret += point[i][j]; // 自分を取って
rep(d, 4) ret+=f(i+di[d], j+dj[d]); // 近くのを取りに行く
return ret;
}
DP †
- 難しさ
- 分かったつもりで実際に問題をといても、アクセプトされない。
- デバッグしにくいので、しかも何でアクセプトされないかわからない。
DPの漸化式 †
- コツ
- 「i未満の添字を使って」という表現をする
- 「〜が確定している時」という表現をする
DPの種類 †
| 名前 | 特徴 | できること |
| 配るDP | 漸化式の関数が可換、かつ漸化式の関数に単位元が存在し、かつ更新前の添字から更新後の添字を計算可能 | 実装が楽。配れないならcontinueできる |
| 集めるDP | 更新後の添字から更新前の添字を計算可能 | 汎用的 |
| 前回のみに依存するDP | 空間計算量が抑えられる。DP配列を2だけ用意して偶数奇数で分ければいい。配る前回のみに依存するDPは初期化に注意 |
| 一方向に依存するDP | 前回のみに依存し、かつ更新式が後ろにのみ依存する場合、添字を前から後ろに回して、空間計算量を更に抑えられる。DP配列を使いまわせるので。 |
DPのデバッグ †
- コツ
- 変更後の状態を
- 別のループで
- 自明でないものだけ出す！
DPはメモ化再帰のループ版 †
- メモ化からの漸化式構築＝動的計画法
- 「これまでに得られる〜」をメモ化する
- 幅・深さ優先探索のメモ化のときに保存した状態と、ここで計算するテーブルの状態変数は一致する
- 「ありえない組み合わせ」というものが存在する
- DPは指数計算量探索の合流である
- 探索の「状態」と「合流法則」を抽出したものがDPとなる
- まず指数計算量探索を図示してみる
- 丸の中に状態（＝添字や重さや価値）を書いたグラフを書いてみる
- すると、合流を見つけることができる。合流のルール（＝その上流すべての情報の集め方）を抽出する
- 状態と合流から自動的にDPが計算できる
- 初期条件は初めが決まっていることも、深いところの拘束条件があることもある
- DPでは深いところしか決まっていないとやりづらい
- 場合の数も、初めに自明に決まる場合の数から始めるとDPが楽になる
何を考えるべきか †
- 1セット
- 状態を適当に定めてみる
- 今の状態から次の状態がどう決まるかを考えてみる
- 次の状態が今の状態から統合されるかを考える
- 何の情報が足りないかを考え、情報を状態に追加する
全探索との対応 †
| グラフ分析 | メモ化探索 | DP |
| 状態 | ノード | 引数 | DPテーブル添字 |
| 値 | ノードに付属する値 | 返り値 | DPテーブル |
| 遷移 | 上から下への操作 | 再帰関数（更新） | 漸化式（代入演算） |
| 結合法則 | 二つ以上のノードから一つへのリダクション | 再帰関数（結合） | 漸化式（左辺値） |
| 初期条件 | 初めのノード | 関数呼び出し | 境界条件 |
例：A未満の非負整数を数える †
- 桁DPが入門に非常によいと思う。
- A: N桁の数字
- dp[i][j]: 以下の状態の時の場合の数
- i: 上からi桁目の自然数集合において (i=0, 1, ..., N, inclusive. つまりi=0では空集合を見ている)
- j: A未満であることが確定している (j = 0, 1)
#include <iostream>
#include <string>
#define rep(i, a) for (int i = 0; i < (a); i++)
using namespace std;
const int mod = 1e9 + 7;
int dp[101010][2]; // pos, less
int main() {
string A;
cin >> A;
int n = A.length();
dp[0][0] = 1;
rep (i, n) rep (j, 2) { // DPテーブルの結合則の数 「DPテーブルから決まっていく様子を想像する」というのはこれを思い浮かべること。
int lim = j ? 9 : A[i] - '0';
rep (d, lim + 1) { // DPテーブルの結合則の具体的な計算数。「DPテーブルから決まっていく様子を想像する」というのはこれを思い浮かべること。
(dp[i + 1][j || d < lim] += dp[i][j]) %= mod;
}
// dp[i + 1][0] = dp[i][0]; d[i + 1][1] = (A[i] - '0') * dp[i][0] + 10 * dp[i][1];
// でもいいはず。でも与えられたdによってDPテーブル添字が一意に決まるので、上のようにdで全探索している
}
int ans = 0;
rep (j, 2) (ans += dp[n][j]) %= mod;
cout << ans << endl;
return 0;
}
実装の構造 †
dp[初期状態] = 初期値;
for (状態) {
for (遷移) {
次の状態 = 遷移(状態);
dp[次の状態] = dp[状態];
}
}
// ↓のようにコメントを書いておくとよい
dp[i + 1][k][j] = (dp[i][k][j] //i番目は選ばない
+ dp[i][k - 1][(j - i + N) % N]) % MOD //i番目を選ぶ
初期値 †
- 探索がベースの DP はどこから始めれば全列挙ができるか考えると自然に初期値が定まる
- 初期値を定めることは探索ベースの時の関数呼び出しに相当する！初期値
- 初期値はDPの定義外．（そうじゃないと，空集合に対する場合の数みたいなのって扱われるべき？i=0, つまりAが空集合の時の場合の数が自明になる？A未満であることが確定している(j = 1)、「空集合」の元である自然数の場合の数は？→0A未満であることが確定していない(j = 0)、「空集合」の元である自然数の場合の数は？→1？？？本当に？？？みたいな悩み方をすることになる）
- ナップザックのような数え上げの問題では，初期値は0となる．
一方向に依存するDP †
- DPで漸化式が前にのみ依存している＝ループを逆に回せば、後にのみ影響するDPを実現可能
- 一方向にのみ依存するDPは、用意する配列を1つだけに抑えることができる＝漸化式が後にのみ依存している場合、i+1->iとして同じ配列を使いまわしていい（なぜかというと、DPの材料が必ず新鮮だから）
- d[i+1][j] = d[i][j]+d[i][j+1];
- i: 0 1 2 3 4 5
- 0: 0 2 7 5 3 2
- 1: 2 9 12 17 20 22
累積和 †
- コツ
- n要素配列の累積和なら、n+1個用意して0番目を単位元にする。
- 二次元でも累積和できる。
- imos法
Priority Queue †
- クエリ突っ込みながらソートしたい！という時のため。
- これだけだと、二分探索木(STLのmap)もできるが、これはもっと静的でクエリ解消はできない
- priority_queue
- 何も指定しないと最大がtopになる。普通のソートとは直感が逆なので注意。
priority_queue<ll, vector<int>, greater<int>> q; // topが最小
priority_queue<ll> q; // topが最大
- デバッグ
- 出力は、イテレータが使えないので、コピーして全部取り出さないといけない。auto q_tmp = q; while (!q_tmp.empty()) {cout << q_tmp.top() << " "; q_tmp.pop(); } cout << "#" << endl;
二分探索 †
while (1) {
ll t; cin >> t;
cout << check(t) << endl;
}
Link Cut Tree †
Segment Tree †
- コツ
- 非遅延セグメントツリーは、結合二項演算と単位元だけあればできる。
- Do Use Segment Tree
- 遅延評価
- 永続ってなに？
- セグメントツリー中級に良さそう
しゃくとり法 †
- 「ある区間で特性関数を満たすならば、区間を右に伸ばしても必ず満たす」時、条件を満たす区間をO(n)で全列挙するアルゴリズム
- 例題
Union Find †
FFT †
三角数乗 †
- 2^(n*n)は、三角数乗を順に求めるとO(n), 二分累乗だとO(n log n)？
ビームサーチ †
座標圧縮 †
http://algoogle.hadrori.jp/algorithm/compress.html
Range Tree †
- 特に、指定された区間や点にオーバーラップする全ての区間を探すという問題を効率的に解くことができる。
- 例えば、表示されている地図内に見えている全ての道路を求めるとか、3次元のシーンで見えている全てのオブジェクトを求めるといった用途に使われる。
加群の行列演算 †
- 零元と単位元が何かをものすごく気をつける必要あり。意識しないと死ぬ。
- 零元「足し算すると変わらない、かつ掛け算すると0になる」
- 単位元「掛け算すると変わらない」
- 普通の行列演算でいう0を零元、1を単位に書き換えないといけない。
二分木 †
- やりたいことは「ソートしながらデータを持つ」データ構造
- 追加も削除もある場合の頻出テク
- クエリの(平方)分割
- がんばって動的になんとかする
愚直な方法 †
- 頂点の左は必ず小、頂点の右は必ず大
- クエリ
- insert(x): 頂点がxより小さければ左遷移、大きければ右遷移、を繰り返してNULLポインタにあたったらそこにnew
- erase(x): まずxを探す(頂点p)。次にxを超えない最大の頂点を左右右…右の要領で探す(頂点q)。pを消して、qをpの場所に張り替える
平衡二分木 †
- 基本だと、1,2,3,4,5,...,nの入力でなんかヤバくなる
- どんなものが平衡二分木？
- 赤黒木(std::map)、スプレー木(Link-cut Treeに使う。ならしO(log n)だが最悪時間O(n)なので注意)、Treap、AVL木、くらい覚えとけばよさそう
- 平衡
- 左右の深さが偏らないように回転 (rotation)
- 回転＝順序を保存したまま木構造を変形。
- 順序を保存＝同じ順序関係を表す二分木であるという意味。参考(111ページ)
- Left Rotationが左を下げること、Right Rotationが右を下げること。
- クエリ
- insert, erase
- split, merge: [0, k)と[k, n)の2つの列に分割、マージ
- 値に関する質問・更新: sum, addなど
- 各論
- Treap: キーと一緒に「優先度」を持つ。キーを見ると二分探索木、優先度を見ると二分ヒープ（常に親が子より大きい）になるように木を構成
- Splay: 2つ親までを見れば、回転によって平衡化が可能なことを利用した平衡木。頂点xを根の場所まで移動させてできる木を返す
Link Cut Tree †
- Link-cut Treeのなりたち（下に行くほど実装が重い）
- 頂点vから根へのパスをつなげる（expose, 必須で平衡二分探索木のsplit, mergeを使う）
- 頂点の親を変更(link)、削除(cut)
- 木の根を求める(root), 木の根を変更(evert)
- パスに対する頂点・枝の値のクエリ（sum, max, 更新）
- コンセプト
- ツリーを分解してパスにします。
- パスをsplay木で管理します（パスの順序さえあってればいいので、根は自由に選べる。よく実線をsplay木内部の辺、点線をsplay木間の辺として表記する）
永続 †
- 永続(persistent)＝バージョン管理して、undoできる！
ゼータ変換 †
FFT †
- 畳み込み和列挙を多項式の掛け算と解釈して、フーリエ変換で解く方法
Grudy数とNim †
二部マッチング †
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
