TODO
概要 †
- プロコンで必要となる知識のまとめ。
- 特にこのページはアルゴリズムのまとめ。
- 解いた問題数を増やすのは良い事なんだけど、解いた問題数を増やすためだけに、簡単な問題を解きまくるのってすげえ時間の無駄
- アルゴリズムが判ってない、計算量が判ってないから、「○○は遅いからダメ」みたいなのをあらゆる状況で言っちゃう人は割と多い。必要なところだけ早くすればいい。
記録 †
下位ページ †
目次 †
参考 †
勉強すべきこと †
重要 †
- Cartesian Tree
- monge
- ウェーブレット木
- 動的ウェーブレット木
- 永続ウェーブレット木
- 動的永続ウェーブレット木
- ウェーブレット行列
- Blackbox Algebra
- Link-Cut Tree（木で最強）
- インタバル木
- Dancing Links
- マージ可能ヒープ
- skew, 乱択、フィボナッチ、Pairingソートなど
- 分割統治法，逐次構成法，
- 平面走査法
- Gray Code
- 永続
- 動的
- セグメントツリー
- 遅延セグメントツリー
- 永続遅延セグメントツリー
- しゃくとり法
- ベルマンフォードって何のために使うの？(LatteさんのSelf-constructing witchが1つの解答になるかも)
- AhoCorasick?
そこそこ †
- カタラン数
- 山登り法
- マルチスタートローカルサーチ（ローカルサーチのスタート地点を複数点設けます）
- 焼き鈍し法
- 遺伝的アルゴリズム
- タブーサーチ
- モンゴメリ乗算
- 高速アダマール変換
- 区間ふるい
- MCS
- DM分解
どうでもいい †
- ADS
- 2-SAT
- Treap, RBST(k-th tree), 平衡二分木
- デク・優先度付キュー
- ボロノイ図とデローネイ三角形分割
- 美術館問題
- 最短路問題
- 埋め込み
- Stern-Brocot木
- ベルヌーイ数列挙 O(n^2)
- 分割数 O(n√n)
- スターリング数 O(n^2)
- Chordal graph
- Cograph
- Stoer-Wagner
- 永持-茨木法 (全点対最小カット)
- 有向木の部分木のハッシュ
- Knuth-Morris-Pratt
- Aho-Corasick
- CIPR (最長共通部分列)
- 編集距離 O(nm)
- 部分回文列挙
- Segment Treeでローリングハッシュ
- Segment treeでflip/count: !libuwi/utils/structure/segtree/SegmentTreeRXQ.java
- Segment treeで点更新・範囲le/geカウント
- Skip List
- Van Emde Boas tree (vEB tree)
- Fixed Universe Structures
- 永続的平衡2分探索木
- BK-tree
- Trie
- Meldable heap
- 削除・更新のできる2分ヒープ
- Double-ended priority queue
- キュー with minimum
- Shunting-yard algorithm
- 平面グラフ 双対なものが構成できる。
- 木について
(1) 頂点uの値をxに変える
(2) 頂点u, vを結ぶ最短パスの頂点のうち、最小値を答える
というクエリを、O(log n)で処理できないという結論に至った。（今の僕には）
ライブラリ †
- はむこのライブラリ
- TODO
- エラトステネスのかわりに区間篩を使って実装。
- 区間篩じゃないとかなり大きい範囲の素数全列挙はできないという噂
| アルゴリズム | 概要 | 計算量 | | 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) | | 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)． | | Edmonds-Karp | 有向最大流 | O(E^2 V) | | Goldberg-Tarjan | 有向最大流 | O(V^2 sqrt(E)) | | Nagamochi-Ibaraki | 無向グラフ最小カット | O(VE + V log V) | | 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!)なので少し落ちてる | | レンジ木 | | | | Splay木 | 平衡二分木 | | | Interval Tree | | |
アルゴリズム各論 †
全探索 †
n^k †
- rep(i, ni) rep(j, nj) rep(h, nh) rep(k, nk) cout << i + j + h + k << endl;
深さ・幅優先探索 †
| 名前 | データ構造 | デメリット | メリット | | DFS | stack | 最適性は保証されない | 省メモリで全探索可能 | | BFS | queue | メモリをいっぱい使う | HITしたものが最短経路経路であることが保証される |
- 深さをメモするqueueの実装は、unordered_mapやmapが必要
- AOJ Reverse Sort
- そもそも深さ付きDFSはvectorをqueueとして使ったほうが楽
- queueでやりたいなら、queueに突っ込むnodeのunordered_mapを用意して、node tmp = q.top(); ll cost = depth[tmp]; q.pop();とかやるしかない。
グローバルにデータを持つDFS, BFS †
- 木の持つデータが大きい場合、「逆操作が軽い」DFSならば、メモリ使用量をO(1)に出来る。
- もし操作が「戻れる」なら、再帰関数を呼ぶ前と後に状態変化を書くことで、グローバルにデータを持てばよい
n! †
nCr †
- next_combination
- めんどい場合はnext_permutationを使っても良い
総和を固定する全探索 †
- 数列aに対して、総和Sが含まれる評価式を満たすaを1つ挙げたい
- なぜ難しいか？
- aを動かすと、Sが動いてしまうこと
- 前から貪欲に決めていこうとしても、途中の更新で今まで確定していたと思っていた添字がだめになるケースがある。
- どうすればいいか？
- Sを固定すればいい！
- Sを固定した条件で、a[i]を構成していき、総和Sを実現できるかを見れば比較的簡単に全探索できる。
- SRM 697
- aの小さい方から確定させようとします。a[0:m-1]がすべてa[i]×(b[i]+1)>=Sを満たしていてa[m]が満たしていない時、a[m]をa[m]' = a[m]+kに更新するとa[m]'が条件を満たすとします。ここでa[0:m-1]の、もう確定したと思っていたものは確定したとは言い切れない気がします。なぜなら、以前に確定させたp<=m-1の添字に関する条件は、a[p]x(b[p]+1)>=S'=S+kとなり、元よりも条件が厳しくなるからです。
- しかし、S固定すると貪欲に取れて、最終的に構成されたa[i]<=Sならばa[n-1]をS-sum(a[0:n-2])とすれば合計がSのaが構成可能
状態 †
- アルゴリズムでは「状態」が重要である。
- 全探索は状態を全て走査する
- DPは状態と遷移の組み合わせを考察する
- ゲーム理論ならgrundy数には状態が必須
- 状態の抽象度
- 一見n!であっても、上手く見ると状態を減らせる、というのが非常に重要
- 順序 n!
- 被覆+最後 n 2^n
- 被覆とは、集合のどれかを選ぶという意味。
- 巡回セールスマン問題
- 被覆 2^n
- 区間 n^k
- 1次元の区間は[l, r)で表される。
- 2次元の区間は[(a, b), (c, d))で表される
- 個数 n
- mod n
- 偶奇 2
基本 †
二分探索 †
while (1) {
ll t; cin >> t;
cout << check(t) << endl;
}
- 実装
- 二分探索の変数名をpassとfailとすると超わかりやすい
- l, rは厳しい
- パラレルバイナリサーチ＝クエリまるごと二分探索
- Incrementalなデータ構造に対して、「〜であるのはいつか？」というクエリをQ個処理するのが基本形。
- O((Q q+t)log T)(qはクエリ応答計算量、tはデータ構造の構築時間)
- 永続の特殊バージョンの場合に使える二分探索
- クエリQ個を、IncrementalもしくはDecrementalな構築途中のデータ構造の時間に対して二分探索したいが、二分探索のための構築に時間がかかる時に使う
- より形式的には、Q個のクエリ先読み可能＋クエリが時間に対して単調な場合、時間幅Tの永続データ構造に相当する機能を、省メモリでO((Q q+t)log T)で計算できるもの、と認識している
- Atcoder AGC 02D, yukicoder 416
しゃくとり法 †
- しゃくとり法
- 「各lに対してf([l,r))が単調増加二値関数の時、が真になる最小のrを計算」
- 区間から真偽を返すfが「f(S)が真ならf(広(S))は真かつ、f(S)が偽→f(狭(S))が偽かつ、f(空)=偽」を満たす時、真となる区間をこれ以上狭められないような区間を全列挙するアルゴリズム
- ある関数fは区間X=[l,r)→真偽値（例：ある区間和がS以上）
- fの単調性：f([l,r))が真→f([l-1,r])もf([l,r+1])も真。f(空)=偽
- f([l,r])が真かつf([l+1,r])もf([l,r-1])も偽となる、「もうこれ以上削れない区間」を全列挙する-例題
- 例題
- 非常に基本的な問題
- ARC 22B（39ページ目）
- ARC 30C
- 数学的解釈
- paiza
- 例題
- paiza
- 素数の楽しそうな例題
- 例題
ダブリング †
- ダブリングは、f(x)=f(f(x-1))なる関数であれば、f(x)の計算がO(log n)で計算できる
- なぜなら、f(2^{k+1})=f(f(2^k))だから、f(2^k)を求めることが簡単。
- ダブリング上での二分探索は「〜を超えない最大の添字」を探す、と覚えると良い
- 例
- 木やFunctional Graphのある頂点から、n個上の親・n個上までの加算・n個上までのminを求める
問題の見方 †
- アルゴリズムの重要なことは、脳内の整理
- 図や表を多用しまくることが重要
基本的なこと †
- 凸凹してたら
- 全探索
- DP
- 半分全列挙
- 分枝限定法
- 枝刈り全探索
- マッチング
- フロー
- 二部グラフ（結局これもやってることはフロー）
- 割り当て（全体の拘束のもと、満足度を最大化）
- 「5歩で」「10回で」
- 半分全列挙
- AOJ Reverse sort, yukicoder 五輪ピック
- 「辞書順最小で」
- 辞書順は取れるときにとれば最適になる
- 待っていても良い物がこないし、一回一回で最適なものを選べばいいだけだから
- 「n<200のグラフ」
- Nが小さいグラフはとりあえずワーシャルフロイドで全点から全点にすぐ行けると思うと良い
- 「全て異なる」
- 割り当て問題。「n人の人がm個の仕事をする。人iが仕事jをするときの達成度vのリストが与えられる。全体で最大の達成度はなにか。同じ仕事は複数人で受けられない。」
- 厳密に小さいと全て異なることになる。全部異なるものを仕事側とすると、割り当て問題の「同じ仕事は複数人で受けられない」に相当することになる。
- AOJ Dangerous Tower
問題の図示 †
##
###
#######
########
変数の動きの整理 †
int a; cin >> a;
b = a * a;
c = a * b + (a > 0);
a b c
--------
-1 1 -1
0 0 0
1 1 2
用語 †
- multiset
- 同じ要素が複数入っていても良いデータ構造。eraseでは全部ではなく1個だけ消す(Codeforces 367 D2D)
- 部分列(subsequence)は、部分文字列(substring)とは異なることに注意する。前者は元の列の連続した項からなる必要はない。
データ構造の数学的構造 †
俯瞰 †
- データ構造Gと演算○のセットを、(G, ○)という。
- これがどのような代数的構造を持っているかで、適用可能なアルゴリズムを限定できる。
- アルゴリズム構築に重要な代数的構造は以下である
| 名前 | 特徴 | 具体例 | | モノイド | 並列処理可能性 | (整数, min), (整数, max) | | 群 | 0-indexだけ計算すればi-indexに出来る | (整数, +) | | ベクトル空間 | 行列演算可能性 | (実数, +, *) |
代数的構造のまとめ †
- 環からは、2つの演算子に関する代数的構造。
- 下に行くほど、制約が強い
| 名前 | 定義 | 具体例 | | マグマ | (S, ○)が全域性を持つ＝演算結果も集合Sに入る。集合Sを台集合という | | | 半群 | ○が結合則を満たすマグマ(S, ○) | | | モノイド | 単位元eを持つ半群(S, ○) | (自然数, +), (自然数, *) | | 群 | 逆元を認めるモノイド(G, ○) | | | アーベル群 | ○が可換な群(G, ○) | (整数, +), (有理数から0を除いた集合, *), (実数から0を除いた集合, *) | | 半環 | (R,•,+)、+下の可換モノイド、•下の半群, +上の•の分配性。逆元がなくてもOK | (自然数, *, +)。max-plus代数=(整数, +, max)は+が乗算なのが面白い！ | | 環 | (R,•,+)、+下のアーベル群、•下の半群, +上の•の分配性 | Nは任意の自然数としてZ/NZ=(Z, * mod N, + mod N)は環、これは余剰環と呼ばれる。 | | 単位環 | •について単位元1を持つ環 | | | 可換環 | •の可換性を持つ環 | | | 整域 | •に対する非ゼロ因子付き単位元を持つ可換環 | | | 体 | 非ゼロ元の•に対する逆元を持つ可換環 | Z/pZ=(Z, * mod p, + mod p)は余剰体と呼ばれる。ただしpは素数に限る。またp=2の余剰体はブール体と呼ばれてZ/2Z=B=(Z, AND, XOR) |
- イデアル
- 環の特別な部分集合
- 「何を取ってきても、自分と乗算すると自分になっちゃう」（例: (整数, *, +)で、偶数はイデアル。どんな整数を取ってきても、偶数と掛け算すると偶数になっちゃう）
- 環は可換性を前提しないので、左イデアルと右イデアルがある。両側イデアルを単にイデアルと呼ぶ
- ベクトル空間について
- 体Fを複数連結した「体Fのベクトル」に関して加群であればベクトル空間になる。
- 「Vを体F上のベクトル空間とする」などと表現する
| 名前 | 定義 | 具体例 | | 環上の加群 | 左R-加群Mの定義を行う。アーベル群(R, +)と、RxM->Mを定義するスカラー乗法*について、+の分配則・スカラー乗法の結合則・*に対する単位源の存在を満たすならば、Mは左R-加群。 | | | ベクトル空間 | 体(G, *, +)に対して、+の分配則・スカラー乗法の結合則・*に対する単位源の存在を満たす | |
- annihilate
- 日本語では「零化」
- Rを環、Mを左R-加群、SをMの部分集合とする（大体R=実数, M=ベクトルの集合, S=ベクトル部分集合だと思えばいい）
- Rに関してAnn(S)={r in R | 左からrをかけるとSの全ての元が0になる}
- Ann(S)は左イデアルであるため、これを日本語では「零化イデアル」と呼ぶこともある。
モノイド †
| 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 |
- 非自明モノイド
- [l, r)の連続部分列の総和の最大、はモノイド(AOJ Do use segment tree)
データ構造の機能の名称 †
- 動的
- 木・配列・グラフなどの構造そのものが変わること。
- 動的凸包、動的kd-Tree、動的Ford Fulcarsonの場合、「削除ができること」という意味。
- オンライン
- 永続
- データ構造の途中結果に、更新が終わったあとにアクセスできること。
- 入門には永続Union-findが一番わかりやすい。
- だいたいのデータ構造は永続にできる。永続配列、永続平衡二分木(RBSTがよく使われる)、永続union-find、永続set、永続セグメントツリー、永続ウェーブレット木…
- 範囲更新
- [s, e)までに演算を行う、木の頂点sを根とする部分木全てに演算を行う、木の頂点sから木の頂点eの最短パスの全てに演算を行う、など。
永続 †
DFSでできる永続 †
- 逆操作が簡単な永続データ構造は、ただ「グローバルにデータを持つ」DFSを掛けばよいだけ。
クエリ先読み＋単調なデータ構造に対してできる永続の代替 †
- 単調＝Incremental, Decrementalという意味
- パラレルバイナリサーチ
- Q個のクエリ先読み可能＋クエリが時間に対して単調な場合、時間幅Tの永続データ構造に相当する機能を、省メモリでO((Q q+t)log T)で計算できる
mod †
分数のmod †
Z/pZ体の逆元 †
- *a^(p-2)が逆元となる。
- 重要なのは、pが素数でない場合には、必ず逆元が存在しないこと！
- 逆元が存在しない場合は、ダブリングのようなもので代用することを考える。
N^M (mod p) †
- pは素数なのでフェルマーの小定理より、N^M=(N%p)^(M%(p−1)) (mod p)
nCr †
- n!と1/n!をO(n log mo)で前計算することで、nCrはO(1)で計算可能
拡張ユークリッドの互除法 †
- 拡張ユークリッドの互除法を、非再帰のユークリッド互除法→Blankinship's algorithm→線形方程式の求解として見る→単因子標準形、と拡張する。
素数 †
- 素数系のライブラリは、隣接性を利用したものと、しないものを明確に分けなければならない。
- 隣接性利用: O(n log log n)
- 隣接性非利用: O(n sqrt(n))
構築付き素数判定 †
- エラトステネスのふるい
- 長い配列を用意して、必要のないところにはそもそも試し割りしないようにしながら素数を列挙する
- O(n log log n)
連続する素数に関する問題は速く解ける †
- 具体的にはO(n sqrt(n)) -> O(n log log n)に落ちる。
- エラトステネスのふるいと同じようなアイディアで、試し割りするともに素因数の数を数えることで、隣接100万くらいの素因数なら全列挙できる。
- 具体的には、SRM 565 D1Mのように隣接100万個の素因数の数え上げはO(n log log n)と高速である一方、構築後の素因数を一つ一つ見るのでO(n sqrt(n))となりn=100万では無理。
非構築素数判定 †
- Millar-Rabin Test
- O(20)くらいで構築なし、64bitの素数判定ができる！
区間篩 †
約数全列挙 †
- sqrt(n)まで試し割りして、全部の割れたものに関して(i, n/i)を全列挙すればOK
範囲クエリ †
演算 †
| 演算 | 結合 | 可換 | 可逆 | | + | o | o | o | | * | o | o | o | | min | o | o | | | 行列積 | o | | | | 拡大回転行列積 | o | | o |
まとめ †
| 名称 | 結合 | 可換 | 可逆 | 構築後のデータ変更 | 構築 | 参照クエリ | 更新クエリ | 範囲更新 | 備考 | | Fenwick Tree = BIT | o | o | | o | O(n) | O(log n) 0-indexのみ | O(log n) | x | | | Fenwick Tree = BIT | o | o | o | o | O(n) | O(log n) i-indexも可能 | O(log n) | x | | | Sparse Table | o | o | | x | O(n) | O(log log n) | - | - | 出力の選択性を要求(演算はmin, 2番目のようなもののみ) | | Segment Tree | o | | | o | O(n) | O(log n) | O(log n) | x | | | Lazy Segment Tree | o | | | o | O(n) | O(log n) | O(log n) | o | | | いもす法 | o | | | x | O(n) | O(1) 0-indexのみ | O(1) | o | | | いもす法 | o | | o | x | O(n) | O(1) i-indexも可能 | O(1) | o | | | ナイーブ構築あり | o | | | o | O(n^2) | O(1) | - | - | | | ナイーブ構築なし | o | | | x | O(1) | O(n) | O(1) | x | |
BIT †
- Fenwickは、「点更新」「範囲参照（0-indexにしかならない！）」
- Fenwick Tree=BIT=Binary Indexed Tree
Segment Tree †
- Segment Treeは、「範囲更新」「範囲参照」（範囲更新はlazyによって実現）
- セグメント木
- モノイドでいいので応用力が高く、自分で考える部分が大きい。
- コツ
- 非遅延セグメントツリーは、結合二項演算と単位元だけあればできる。
- 練習問題
Lazy Segment Tree †
- 範囲に対する更新を可能にする
- 遅延セグ木のコツ
- あるノードより上のノードとその子のlazyを、上から全部解消すると、そのノードの本当の値が出てくる。
- 遅延更新セグ木のアルゴリズム
- 更新すべき被覆X={X_i}を列挙する。以下i固定
- X_i以上に未解消のlazyがあれば、そのlazyを全て解消
- X_iの真下があれば、真下にlazyを追加
- X_iをdataに追加し、上方向に一貫するように更新
- 更新すべき被覆X={X_i}を列挙する。以下i固定
- X_i以上に未解消のlazyがあれば、そのlazyを全て解消
- 解消後のX_iをメモ
- op(X)を計算
- 実装
- コツ：1-indexで実装し、data[0], lazy[0]は使わない
- lazy segtreeに必要な条件、集合A上の+っていう演算結果が欲しくて、更新クエリが写像A -> Aの部分集合Fの元になっているとき、(A,+)がモノイドで、Fが合成で閉じていればokな気がした。あとはFの元f,gについて合成f*gとf(x_i)の区間和が高速に計算できれば
永続Segment Tree †
動的Segment Tree †
部分列の最大値を計算するSegment Tree †
- AOJ Do use segment tree解説資料参考
- Segment Treeの各ノードに必要そうな値を考える
- その区間の最大値ansは絶対必要
- その区間の合計allも必要そう
- 左端を含んだ最大値left、右端を含んだ最大値rightがあれば便利
- マージ則
- m.ans = max(l.ans, r.ans, l.right + r.left)
- m.all = l.all + r.all
- m.left = max(l.left, l.all + r.left)
- m.right = max(r.right, r.all +l.right)
範囲クエリ上での二分探索 †
- つまり、範囲で見ると単調性が現れるものが、範囲クエリでの二分探索に相当する。
- 数列のminとmaxは範囲に対して単調になる。
- ''全要素が正ならば、積分すると単調になる
- segment tree上の二分探索が可能''
- Segment tree上の二分探索、要するに積分すると単調=全要素が正ってことなんだよね。
imos法 †
- コツ
- n要素配列の累積和なら、n+1個用意して0番目を単位元にする。
- 二次元でも累積和できる。
- imos法
二次元Fenwick †
http://codingmelon.com/2015/12/17/range-sum-query-2d-mutable-leetcode-308/
二次元セグ木 †
http://algoogle.hadrori.jp/algorithm/2d-segment-tree.html
http://d.hatena.ne.jp/ishikado/20111130/1322657085
logicmachineさんの実装
https://github.com/logicmachine/LibCompetitive/blob/master/structure/segment_tree_2d.h
遅延二次元セグ木は？
ソート †
クイックソート †
バケツソート †
- バケツソート
- 静的配列にひたすら突っ込むだけのソート。O(n)でソート可能。1000万はいける。
- SRM D2E 671？
自分でソート †
- 優先度付きキューで自分でソートする
- SRM D1E スターウォーズのやつ
バケット法 †
- バケット法=平方分割=sqruare root decomposition=sqrt(n)分木
- 範囲を扱う時に、平方に分割して記憶することで前処理O(n)、各クエリO(sqrt(n))を実現
- 応用力が高く、自分で考える部分が大きい。各バケットが2分探索木やBITを持ってたりする。
- 応用範囲は、バケット法>セグメント木。
- 速度はバケットO(sqrt(n))<セグメント木O(log n)
- 例題
クエリ平方分割 †
- Codeforces Educational contestのどこかのF
木平方分割 †
グラフ †
グラフに関する基本的名称 †
- 頂点
- 辺
- 入次数・出次数
- DAG
- 平面グラフ
- Functional Graph
- 頂点が入次数、出次数がともに1
- Topcoder Sunny Graph, Codeforces Educational 16くらいのやつ（Functional Graphはサイクル分解しなくてもダブリング出来るよ、という問題）
- 二部グラフ
有名問題とそのクラス †
- 概観
- いろいろ長い問題名が出てくる。同じ名前で違う呼ばれ方がするので、以下に統一
- 問題＝最小独立パス被覆問題、最小頂点被覆問題、最大独立集合問題、最小パス被覆問題、最小辺被覆、最大マッチング
- 性質＝DAG、推移性、二部グラフ
- 最小独立パス被覆問題
- グラフの頂点を、非連結な何個のパスで全て覆い尽くすことが出来るか？
- 非連結なの部分が「独立」に相当している。重要。これがないと、多項式時間にするのに推移性が更に必要になる。
- DAGだと多項式時間で解ける
- 最小頂点被覆問題
- 頂点被覆＝全ての辺が、選んだ点に接続するようにする頂点集合
- グラフの頂点に色を塗る。色を塗られていないところの隣に必ず色が塗られているようにしたい。色を塗る最小回数を求めよ（NP完全）
- |V|=最小点被覆+最大独立集合
- 一般にはNP完全
- 最大独立集合問題=最大安定集合問題
- 独立集合=辺で隣り合っていないような頂点集合
- 一般にはNP完全
- 最小パス被覆問題
- グラフの頂点を、何個のパスで全て覆い尽くすことが出来るか？二回同じ頂点を使っても良い。
- 推移性があるDAGだと、最小独立パス被覆問題に一致し、多項式時間で解ける。
- 最小辺被覆
- 全ての点が、選んだ辺に接続するようにする頂点集合
- 詳しくは
- 推移性
- 「a->bとb->cに辺があるならば、a->cにも辺がある」を満たすDAGに関する性質
- 推移性のあるDAGなら、最小独立集合問題と最小パス被覆問題と最小独立パス被覆問題は一致し、多項式時間で解ける [Dilworth 1950]
- 二部グラフ
- 二色彩色可能なグラフ
- 二部グラフでは、最大マッチングが多項式時間で求まる
- 二部グラフならば、最小頂点被覆＝最大マッチング
複雑なグラフ構築のコツ †
- グラフ構築ゲーはname server作ったほうがいい（name server = 文字列からノードの番号を得るmap）
最短経路問題 †
- ベルマンフォードって何のために使うの？(LatteさんのSelf-constructing witchが1つの解答になるかも)
| 名前 | 計算量 | アルゴリズム | 特徴 | | ベルマンフォード法 | O(VE) | 前提：負の閉路がない連結グラフ。全辺を見て、現状より辺を通じたほうが良ければ更新。更新するものがなくなるまで行う | 負のコストを許容。負の閉路がなければOK。また、すべての負の閉路の検出も可能（更新が規定回数で止まらなかったら） | | ワーシャルフロイド | O(V^3) | | 全始点全終点。実装楽。 | | ダイクストラ法 | O(ElogV) | 前提：負のコストがない連結グラフ。コスト最小の未確定頂点を選び、そこから行ける頂点を更新して未確定頂点とする。これを未確定頂点がなくなるまで続ける。priority queueを使って実装する場合は「確定」の概念が明示的には入らず、コストが同じなら一番初めに処理した頂点が強いことで弾く | 負のコストを許容しない。 | | 経路復元 | O(E)かO(V) | O(V)は以前の道を記憶する。O(E)は以前の道をあとから探す | E: d[j]=d[k]+cost[k][j]なるkを探す。V: 更新時prev[j]を記録する。 |
- ダイクストラ
- 要するに集合拡大
- 拡大ルールは「集合から到達できる頂点のうち、最も小さいコストの頂点を拡大する」
- 実装にはフィボナッチヒープでBFSが高速
閉路検出 †
- 有向閉路検出→SCC
- 無向閉路検出→BFSで二度来たら閉路あり。
グラフのDAG化 †
- 強連結成分を縮約すると、任意のグラフはDAGになり、トポロジカルソートができるようになる
トポロジカルソート †
全域森 †
- 重要なのは「ループがない」こと
- 全域森のモチベーション
- なるべく少ないコストで全部繋ぎたい
- なるべく少ないコストでグラフのループを消したい
| プリム法 | O(ElogV) | 統合頂点群から未統合頂点への最小距離をメモする。未統合頂点のうち統合頂点群に最も近い頂点を探す。統合頂点群に追加する。頂点追加によって、最小距離が変わるので更新する。 | 最も近い頂点を貪欲的に追加する方法 | | クラスカル法 | O(ElogV) | 辺をコストの小さい順に並べる。コストの低い順に見て、閉路ができないならば連結していく。閉路ができることは連結先と連結元がUnion-Findで同一かによって検知可能 | 最もコストの小さい辺を貪欲的に選び続ける方法 |
Functional Graph †
- 全ての頂点が唯一の有向辺を持つようなグラフ。
- 木の頂点がサイクルでつながっている形をしている。
- 実は、サイクルを分解しないでダブリングできる（Educational codeforces 15のE問題)
最小パス被覆 †
- DAG上だと多項式時間で解ける
- 「DAGを無理やり二部グラフにしたもの」を「2V個の頂点V, V’を用意して、元のグラフx->yに辺があるならばx->y’に辺を張る、としたときの二部グラフ」と定義する
- DAG上での最小パス被覆（全頂点を通るような）は、|V| -無理やり二部グラフにしたものの最大マッチングである
最小費用流 †
- 最小費用流は割り当て問題を解ける。
- 「全体で限られた資源で、個々人が資源を使うことにより個々人の不満度が定義され、その不満の総和を最小化する」ということができる
- 「全体で限られた資源で、個々人が資源を使うことにより個々人の満足度が得られ、その価値の総和を最小化する」ということができる
- 最小費用流の非常に良いテキスト
- 輸送問題
- 割り当て問題
- 複数シンク
- 特定の枝に少なくともこれだけのフローを流す、といった制約も解説
- 特にオアシスの例は非常にわかりやすい
- 輸送問題
- AOJ Dangerous Tower
二部グラフ †
- グラフから二部グラフ構築はたったのO(n)
- 二色彩色可能ならば、塗った白黒を左右に振り分けて、必ず二部グラフを構築可能
- 二食彩色不可能ならば、二部グラフは構築できない
- AOJ RabbitWalking?
最大流 †
- マッチング問題が解ける(AOJ Luigi's Tarvan)
- Ford Fulcarsonを動的にする問題が大量にある
- 残余グラフ
- Ford Fulkersonでは、「流せる余力」を表したグラフを作る
- 元のグラフと何が違うかというと、「さっき順方向に2だけ流したから、逆方向に2だけ流す余力がある」というのを許可する点。
- これを前提すると、大概の操作が貪欲に行うことが出来る！
- また、流れているフローを、順方向の辺に対応する逆辺の容量を見ればよい。
- 動的Ford Fulcarson
- 辺Add:
- 残余グラフの余力が増える→フローが流せるか試すだけ。簡単
- 辺Erase:
- フローが流れていないなら、消すだけ。flowは変わらない。
- フローが流れていれば、まずその辺のフローを他のルートに押し付ける！これは、辺を含む閉路が存在したら押し付けることが出来る。
- その結果フローが流れなくなったら、消すだけ。flowは変わらない
- もしフローが足りないなら、終点から始点への消すフローFの増加路を押し戻す。そうすると、上記閉路が必ず存在するようになるので、他のルートに押し付けて、自分は消える。
最小カット †
雑多 †
- 葉を指定した最小全域木→Kruskalの変形
- 分散最小全域木、比最小全域木などは、パラメータ化して何かを止めると凸にする
- k-th最小全域木
静的木 †
- 木の構造そのものが切られたり追加したりしないものでの、様々な木の上でのクエリの処理方法
- 木いろいろ
基本的な性質 †
- 頂点n辺n-1かつ連結なら必ず木構造
- 木構造はどこを根にしても木構造
まとめ †
| 名称 | 計算量 | 説明 | | 頂点から根へ向かうパスの二分探索 | O(log n) | ダブリングで可能 |
| 名称 | 結合 | 可換 | 可逆 | 構築後のデータ変更 | 木の構造変更 | 構築 | 参照クエリ | 更新クエリ | 備考 | | オイラーツアー+Segment Tree | o | o | | o | x | O(n) | O(log n) | O(log n) | min, maxもできる |
| 名称 | 結合 | 可換 | 可逆 | 構築後のデータ変更 | 木の構造変更 | 構築 | 参照クエリ | 更新クエリ | 備考 | | オイラーツアー+Segment Tree | o | | o | o | x | O(n) | O(log n) | O(log n) | min, maxはできない | | Heavy-Light Decomposition+Segment Tree | o | | | o | x | O(n) | O(log^2 n) | O(log n) | min, maxもできる |
オイラーツアー †
- オイラーツアーは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
直属の親子のパスの頂点に乗ったデータの積分 †
- 頂点に群のデータを載せるタイプのオイラーツアーで実現できる。
- 木Gが与えられる。
- 木Gの根からの、オイラーツアーEを考える。
- |E| = 2*|G|
- 頂点iがオイラーツアー上で出てくる1回目を、f_i, 2回目をs_iとする。(fはfirst, sはsecond)
例)
0
1 2
3 4 5
のオイラーツアーは
0 1 3 3 1 2 4 4 5 5 2 0
f = [0, 1, 5, 2, 6, 8]
s = [11, 4, 10, 3, 7, 9]
である。
- 前提
- 木Gの頂点には、結合二項演算opと合わせて群をなす型のデータAを持っている。
- 頂点x, yについて、xがyの直接子孫とする
- [x, y]を頂点xから頂点yへの最短パスの経路上にある頂点（端を含む）とする
- やりたいこと: [x, y]のデータ型の積分をしたい。
- 具体的には、例でx=0, y=6とすると、#0 op #4 op #6を高速に計算したい。
- 実は、これはデータ型の群的性質を用いると、簡単に計算できる。
- データの保持をオイラーツアーと同じ長さの配列Dで持つ。
- 頂点iのデータをA_iとすると、を、D[f_i] = A_i, D[s_i] = A_i^{-1}と、初めの出現に普通に格納し、二回目の出現には逆元を格納する。
- ここで、[x, y]でのデータのopによるパスの積分を考えると、これは数列上で、D[s_x:s_y]の積分に一致する！
- 今データ型は逆元を持つことを前提としたので、D[s_x:s_y] = D[0, s_y] - D[0, s_x-1]であり、BITによってO(log n)で計算可能である。
- 今までの議論では、「xはyの直接祖先」を前提していたが、LCA(x, y)を求めることができれば、最短パスの積分もO(log n)で計算できる。
頂点から根までの列の二分探索 †
重軽分解 †
- 用語定義
- Centroid Path Decomposition
- Heavy-Light Decomposition
- 親の子数が、「最大子数をもつ子」の子数の倍より以下ならばHeavy（つまり、1つのノードからHeavyな辺が二つ以上は出ない）
- 本当は、Centroid Path DecompositionはHeavy-Light Decompositionの一種、という言い方が正しい。
- プロコンではCentroid Path Decompositionのことを、Heavy-Light Decompositionと言及することが多い
- pekempeyさんのHL分解を使って木の上のクエリに高速に答える方法を紹介してくれている
再帰 †
返り値をメモするタイプの再帰 †
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はとにかく、ある状態にいる人の気持ちになって考える=状態を固定した時に、次にどこに行くか、を考えることが非常に大事
- 難しさ
- 分かったつもりで実際に問題をといても、アクセプトされない。
- デバッグしにくいので、しかも何でアクセプトされないかわからない。
- 解説を見ても、DPは図を書かないと絶対理解不能。漸化式を文章で書かれても困る。
- DPの類型化
- 本当はやりたい。
- 無理矢理でもとにかく大量の（200問以上の単位で）ものを分類したい
参考 †
DPの漸化式 †
- コツ
- 「i未満の添字を使って」という表現をする
- 「〜が確定している時」という表現をする
DPの種類 †
| 名前 | 特徴 | できること | | 戻るDP | 漸化式の方向が逆のもの | 特になし | | 配るDP | 漸化式の関数が可換、かつ漸化式の関数に単位元が存在し、かつ更新前の添字から更新後の添字を計算可能 | 実装が楽。配れないならcontinueできる | | 集めるDP | 更新後の添字から更新前の添字を計算可能 | 汎用的 |
| 前回のみに依存するDP | 空間計算量が抑えられる。DP配列を2だけ用意して偶数奇数で分ければいい。配る前回のみに依存するDPは初期化に注意 | | 一方向に依存するDP | 前回のみに依存し、かつ更新式が後ろにのみ依存する場合、添字を前から後ろに回して、空間計算量を更に抑えられる。DP配列を使いまわせるので。 |
DPのデバッグ †
- コツ
- 変更後の状態を
- 別のループで
- 自明でないものだけ出力！
DPはメモ化再帰のループ版 †
- メモ化からの漸化式構築＝動的計画法
- 「これまでに得られる〜」をメモ化する
- 幅・深さ優先探索のメモ化のときに保存した状態と、ここで計算するテーブルの状態変数は一致する
- 「ありえない組み合わせ」というものが存在する
- DPは指数計算量探索の合流である
- 探索の「状態」と「合流法則」を抽出したものがDPとなる
- まず指数計算量探索を図示してみる
- 丸の中に状態（＝添字や重さや価値）を書いたグラフを書いてみる
- すると、合流を見つけることができる。合流のルール（＝その上流すべての情報の集め方）を抽出する
- 状態と合流から自動的にDPが計算できる
- 初期条件は初めが決まっていることも、深いところの拘束条件があることもある
- DPでは深いところしか決まっていないとやりづらい
- 場合の数も、初めに自明に決まる場合の数から始めるとDPが楽になる
何を考えるべきか †
- 自明な条件（＝初期条件）はないか
- 「1個も取らないと答えは自明に0」
- 「最後の1つだけを取ると自明に1」
- 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;
CTRL: Left Allegro Hand controller initialized.
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
区間DP †
- 数列や盤面に対して、非常に典型的なDP
- 数列の典型区間DP dp[i][j] := [i, j]の区間での最大値（閉区間）
- 盤面の典型区間DP dp[i][j][k][l] := (j, i)(左上)から(l, k)（右下）の盤面での最大値（閉区間）
- 例えば50*50の盤面で、左上から右上に移動するパターンは2^100くらいあって無理ゲーだが、区間DPを使うと50^4となり現実的に
- 例題
- 数列: SRM 693 D1E
- 盤面: AOJ Stack Maze
- 盤面: ABC 8D
bitDP †
挿入DP †
確率DP †
- 確率のDPは条件付き期待値を計算すると良い（つまり今までのことを考えてはならない！！！）
- これは、DPの遷移で、その和が必ず1になるように注意できるから。assertとかも最悪掛けられる。
- 656 D1E
未確定のDP †
Monge †
- DPのMonge性
- O(n^3)->O(n^2)（Knuth-Yao Speedup）
- Totally monotone性
- ちゃんとまとめたい
問題特有の構造による状態削減 †
- yukicoder ドーナツ
- Rabbit Walking
包除原理のDP †
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;
最小辺カバー †
FFT †
FFT †
- 結構自然な問題
- 添字の順序の総和が一定となるような掛け算の総和は、O(n log n)で計算できる！
- 用途
線形漸化式と畳み込み †
NNT=高速余剰環畳み込み †
- コード
- mod pでの畳込みはO(n log n loglog n)で計算できる。
- 実は任意の余剰でもO(n log n)でいける。
- p=2の場合、特に高速XOR変換と呼ばれる。bitsetが使えるなど、定数倍を早くできる。
- NTTの別名
- 高速剰余変換 O(n log n)
- 高速xor変換 O(n log n)←法が2の時はこうも呼ばれる。適切な演算子が使えるので定数倍が高速
拡張ダイクストラ法 †
誤差 †
浮動小数点 †
- 例えば、(ll)pow(3, 3) = 26
- とにかく浮動小数点は誤差が出る。
誤差の減らし方 †
- 誤差が厳しい場合
- long doubleを使う
- ハフマン符号のように小さい数値から足していくだけでも誤差減る
「long longのcastで大きくなる」誤差 †
- 前提として丸め誤差は大きくなる
- doubleの精度が15桁であるが、17桁を扱おうとするなどしたら起きる誤差
- 本当の答えが0.999999999999とかである時、丸め誤差が発生すると1.00000000000001とかになる。
- long longのキャストせよという問題なら、本当は0であるべきところが1になる。
- yukicoder 413
XOR †
GF(2)の加算としてのXOR †
XORは、余剰体Z/2Zの加算演算である。
加算かつ減算 †
最大化 †
最大化クエリ †
- Trieを使うことでXORをO(log n)で最大化することができる。
累積和するといいことがある †
- XOR範囲和が0となるような範囲の数え上げ SRM 565
ウェーブレット木 †
Subset Convolution †
高速ゼータ変換 †
高速メビウス変換 †
文字列操作 †
文字列でやりたいこと †
- sが大きな文字列、t_iがマッチングする文字列, |s|=n, |t|=m
- 0-index LCP
- sとt_0の最長共通文字列長を求める
- 重要なのは、マッチング文字列は1つに限定されているということ
- i-index LCP
- sとt_0, t_1, ..., t_nの最長共通文字列長を求める
- マッチング文字列は複数指定可能
| 名前 | 構築 | 0-index LCP | i-index LCP | contain | | SA-IS | O(n) | O(1) | O(1), RMQにメモリ削減のためSegment TreeならO(log n), 複数個の文字列のマッチングが可能 | O(log n) | | Rolling Hash | O(n) | O(log n) | O(log n), 複数個の文字列のマッチングが可能 | 不可能 | | Z-Algorithm | O(n) | O(1), 1個だけの文字列のマッチングが可能 | 不可能 | 不可能 | | boyer moore | なし | 不可能 | 不可能 | 最悪O(n), 平均O(n/m) |
int getLCP(int i, int j)の使い方 †
- SA-ISとかZ-Algorithmを見て、「sa.getLCP(i, j)とか言われても、これでどうやって文字列sと文字列tのLCPを求めるんだ…」と思うこと必至
- int getLCP(int i, int j)の挙動
- saの構築にsを用いたとすると、s[i:end]とs[j:end]の最長共通接頭尾長を求める。
- え、tどこいったの？と思う
- で、どうやってマッチングするの？→t+sに対して構築する！
- saの構築をsa(s)ではなく、マッチング対象t1, t2があったとしたら、sa(t1+t2+s)として構築する。
- こうすると、sa.getLCP(0, |t1|+|t2|)とすることで、t1とsのLCPを求めることが出来る！
boyer moore search †
MP †
- 0からの回文をO(n^2)ではなくO(n)で全列挙できる！
- MP
- O(n)で、文字列 S が与えられたときに、各 i について「文字列S[0,i-1]の接頭辞と接尾辞が最大何文字一致しているか。ただし|S[0,i-1]|未満の一致とする。」を記録した配列を計算。
Manacher †
- Manacher
- 各 i について「文字 i を中心とする最長の回文の半径」を記録した配列 R を O(|S|) で構築するアルゴリズム
ローリングハッシュ †
- ローリングハッシュ
- h(0, i)=h(0, i-1)*b+s[i] で定義される文字列のハッシュ。
- 何が嬉しいかというと、このハッシュは群的なので、h(j, i)がh(0, i)からO(1)で計算可能
- ローリングハッシュのLCP
- 「iから長さkと、jから長さkのLCP」が構築O(n)クエリ(log n)で計算できる。
- ローリングハッシュ、Suffix Arrayの純粋な解説寄り
Zアルゴリズム †
- Zアルゴリズム
- 「0から長さn-jと、jから長さn-jのLCP」が構築O(n)クエリ(1)で計算できる。
- 解説付き
- ちょっと雑
- 重要なのは、これを使うと「TとSのLCP（Tは唯一）は、Zアルゴリズムで構築O(n) 参照O(1)で可能。」ということ
- AOJ Almost Same Substring
Suffix Array †
- Suffix Array
- iとjから始まる文字列からのLCSクエリO(log log n) （ただしクエリはMLEが怖いのでSparse Tableではなく、Segment Treeで実装することが多い。それだとクエリO(log n)）
- ある文字列が含まれているか？containクエリO(log n)
- 構築方法
- Suffix Array 構築O(n^2 log n)＝比較O(n)*ソートO(n log n)
- SA-IS 構築O(n) (Two Efficient Algorithms for Linear Time Suffix Array Construction [G Nong, et.al.])
- Manber&Myers : 構築O(n (log n)^2)
- Suffix Arrayの構築方法
- 愚直 O(n^2 log n) ←multikey-quicksortなるものを使うと早くなるらしい
- SA-IS法 O(n)← 2012年現在，最速
- Manber&Myers O(n (log n)^2)) ←プロコン的にはよく使われる、上の記事はこれ、コメントいっぱいついてる
- Larsson-Sadakane O(n (log n)^2)) ← spaghettiのやつ
問題集 †
Trie †
k-mismatch-matching †
- k個未知の文字列"he?lo wor??"が、もう片方の文字列に含まれているか
- SA-ISでO(k n)で解けるはず。AOJ Almost Same Substring講評参照
二分木 †
- やりたいことは「ソートしながらデータを持つ」データ構造
- 追加も削除もある場合の頻出テク
- クエリの(平方)分割
- がんばって動的になんとかする
愚直な方法 †
- 頂点の左は必ず小、頂点の右は必ず大
- クエリ
- 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木間の辺として表記する）
Euler-Tour Tree †
- Euler-tour treeとLink-cut treeは同様に神がかり的木
ゲーム †
解き方の大まかな分類 †
- 深さ探索するもの
- 状態列挙してGrundy数を使うもの
- ゲーム特有の性質を使うもの
WL-Algorithm †
boolean isWinning(State pos){
State[] nextStates = { posから到達できる全ての次の状態 };
for(State s : nextStates){
if(!isWinning(s)) return true;
}
return false;
}
- このタイプの理解の方法
- 二つの状態の定義があり、この曖昧さによって混乱が生じる！どちらの立場なのかをきちんと明確にすること。
- 勝ち状態wを「この状態から始めた人は必ず勝つ」、負け状態lを「勝ち状態ではない」と定義する。（こっちのほうが一般的！）
- 遷移は、「次に負け状態を相手に押し付けられる遷移が選べるならば勝ち」＝「遷移先にlがあればw, なければl」
- 勝ち状態wを「この状態で終わっ人は必ず勝つ」、負け状態lを「勝ち状態ではない」と定義する。
- 遷移は、「終わったあと、勝ち状態を相手が選べてしまうなら負け」＝「遷移先にwがあればl, なければw」
- 基本的には、「始め」の勝ち状態のほうを、一般的に勝ち状態と言う。
- 勝ち負けゲームの定番解法「勝ち状態にwを置いて、負け状態にいけないなら負け、負け状態にいけるなら勝ち」
- rngさんのAGC02 E問題の解説(youtubeに上がっている)を見るとわかりやすい
ゲームの分類 †
- 二人
- 四人（麻雀）
- 二人（将棋・囲碁・オセロ）
- 一人（ソリティア）
- 有限
- 有限回で終わるゲーム
- ゲーム木（＝局面全体を頂点集合とし、局面Pから局面Qに移動できるとき、PからQに矢を作って得られるグラフ）において、どの頂点から始まる有向パスの総数も有限
Grundy数 †
- pekempeyさんの良い解説
- 定義
- mex(S) = 集合Sに含まれない最小の非負整数(空集合に対しては0)
- Grundy数が負けの状態なら0とする
- 負けの状態ではないGrundy数は、mex(遷移先)とする
- 現在の状態の Grundy 数が 0 なら後手必勝、そうでなければ先手必勝。
- 何がすごいの？
- 複数の山がある場合のGrundy数は、g(a,b,c)=g(a)⊕g(b)⊕g(c)。
- 山ががある場合のGrundy数は、g(a,b,c)=g(a)⊕g(b)⊕g(c)。
- 山が分裂する場合のGrundy数は、g(n)=mex(g(n−1),g(n−2),g(n−3),g(x1,x2,…,xn))=mex(g(n−1),g(n−2),g(n−3),g(x1)⊕g(x2)⊕⋯⊕g(xn))
- g(n-1)からg(n-3)は、Nいっちゃダメゲームで1から3だけ減らせる時のGrundy数を表す。g(x1,x2,…,xn)は分裂後のGrundy数を表す。
- 性質
- Grundy数は「遷移可能な状態の個数」で上から抑えられる
- そのゲーム特有の Grundy 数の性質を見つかる場合あり。N言っちゃダメゲームの場合、単にmodを取ればGrundy数が求まる
- 拡張性
- もちろん、Nいっちゃダメゲーム以外にも使える。
- 具体的には、状態遷移図がDAGなら使える
幾何 †
基本的な発想 †
- なんとなく連続っぽいので難しそうだが、実際にはイベントが発生するような点は有限
- このようなイベント点と、イベント点で何が起きているのかを把握する力が重要
計算のロバストネス †
- 誤差が非常に効いてくるケースが少ないので、なるべく計算誤差が少ないような演算方法が重要
点の進行方向 †
- ccwはロバストな進行方向の計算方法
- angle は三角関数の計算という不動小数の計算を必要とするが，ccw は係数環の演算だけで構成されているので，極めてロバスト
凸包構築 †
- 凸包は基本的にはO(n log n)
- 基本的にはAndrew's Monotone Chainを使うのがいい
Connectivity †
Incremental Connectivity = Union-Find Tree †
- 「同じ集合は同じ根を持つ木である。根は-要素数を持つことでsizeを持つ」である
- 工夫も実は簡単で、(1) uniteの時に木の浅い方にくっつける。 (2) Findの時に、通ってきた経路を全部根からの多分木にするである。
- 盤面問題をUnionFindで
永続Union-Find †
- 永続union find
- 2007年、ACM SIGPLAN の Workshop on ML において、Sylvain Conchon と Jean-Christophe Filliâtre
- 計算機支援証明システムCoqを使って形式的に正しさが証明されている
- 永続Union-Findは、永続配列・永続平衡二分木の両方で実装可能
Decremental Connectivity †
Dynamic Connectivity †
- 切れるUF
- 追加クエリO(log n), 削除クエリO(log^2 n), 連結性判定O(log n / log log n)
- antaさんのライブラリがめっちゃ速い。
- 雑多情報
乱択 †
ヒープ †
- 二分ヒープがpriority_queue
- フィボナッチヒープが最速
Convex Hull Trick †
概要 †
- さばけるクエリ
- 直線f_i(x)=a_i*x+bをリストに追加する O(log n)
- max f_i(x) を計算する O(log n)
Increasing Convex Hull Trick †
- 直線の削除ができない！
- a_iが単調増加、xが単調減少の場合
Dynamic Convex Hull Trick †
Mo's Algorithm †
貪欲 †
証明方法 †
ビームサーチ †
証明の練習問題 †
- Topcoder SRM 697 D1E
- ARC 53C
- 上がって下がってする奴
- あの貪欲の構成は面白かった気がする
- AGC 03B
行列 †
行列の種類 †
0 1 0 0
0 0 1 0
0 0 0 1
a0 a1 a2 a3
- Toeplitz行列
- ある関数fが存在して(A[i][j] = f(i-j))と表せることを言う。
- Toeplitzであるだけでは乗算の元で閉じていない
- Blackbox linear algebraでは一般Toeplitzで動く。
- 上三角Toeplitz行列
- Toeplitx行列でかつ上三角行列のもの。
- 加算・乗算の元で閉じている。
- この行列はサイズnのベクトルによって表すことが出来る。
- 行列とベクトルの乗算は畳込みになっているのでO(n log n)
- Toeplitzであるだけでは乗算の元で閉じていない
- Blackbox linear algebraでは一般Toeplitzで動く。
- 巡回行列
- Toeplitz行列の特殊系
- 加算・乗算の元で閉じている。
- 加算はO(n)
- テプリッツ行列とベクトルの乗算はO(n log n)
- 2つのテプリッツ行列の乗算はO(n^2)
- テプリッツ系 Ax=b は、レビンソン＝ダービン・アルゴリズムでΘ(n^2)の時間で解ける。
a0 a1 a2
a1 a2 a0
a2 a0 a1
行列のクラスと計算量 †
| 名称 | 行列と行列の積 | 普通のk乗行列累乗 | k乗行列累乗(BLA) | | | 一般 | O(n^3) | O(n^3 log k) | O(n^3+M(n)log k) | | | 理論最速 | O(n^2.3) | | | 全く実用的ではないので、O(n^3)未満のものに期待してはいけない。理論最速に至っては、確率モデルに依存して実装不能 | | 巡回行列 | O(n^2) | O(n^2 log k) | O(n M(n) + M(n) log k) | | | (三角とは限らない)テプリッツ行列 | O(n^2) | O(n^2 log k) | O(n M(n) + M(n) log k) | | | K重対角行列 | O(n k^2) | O(n k^2 log k) | | | | S要素疎行列 | | | O(n^2 + n S + M(n) log k) | | | コンパニオン行列の累乗 | | | | |
- Blackbox linear algebraによる行列累乗
- O(n^2+n T(n)+M(n)log k)
- T(n): 行列とベクトルの掛け算
- M(n): 多項式乗算の時間計算量
- 単純なアルゴリズムではM(n)=O(n^2)だが、R=Z/mZの場合は余剰環上のFFTを用いることでM(n)=O(n (log n) log(log n))にできる。
- Blackbox linear algebraによる行列式
行列累乗 †
- 普通の行列累乗について、
- 行列累乗は行列を先に計算するとめっちゃ遅くなるので、行列xベクトルを計算しましょう。
- 構築ありの行列累乗だとメモ化できるので早い
- 参考 AOJ Three-way branch
行列式 †
- 普通には全体でO(n^3)
- 行列木定理と呼ばれる定理は、 グラフが与えられたとき、全域木の個数を行列式を用いて求められる
Blackbox linear algebra †
- 資料
- 行列累乗
- 普通O(n^3 log k)で、テプリッツ行列・巡回行列・コンパニオン行列などでO(n^2 log k)だった。
- めちゃくちゃ大雑把にいうと、これのlog kを分離してO(n^3 + log k)やO(n^2 + log k)にする手法
- 以下の時、「線形漸化的」であるという。（antaさんの造語？N階線形漸化式を満たすという表現）
- これはまさに、無限列が実は初期値＋線形多項式で生成できる、という意味！
Vを体F上ベクトル空間として、V上無限列{a_i}がある。
ある多項式cが存在して、
c(x) = c_0 * x^0 + c_1 * x^1 + ... + c_n * x^n
全てのiについて、
c_0 * a_i +
c_1 * a_i+1 +
c_2 * a_i+2 +
...
c_n * a_i+n = 0
- 線形漸化的な無限列は、多項式cの空でない集合を持つ。
- cをうまく取ることで、最小次数を有しかつ最大次係数が1となるような多項式を唯一に選べる。これを最小多項式と名付ける。
- 行列Aに対して、無限列{A^i}は線形漸化的である。
証明: ケイリーハミルトンの定理により、c(A)=0。
任意のiについて、
c_0 * A^i +
c_1 * A^i+1 +
c_2 * A^i+2 +
...
c_n * A^i+n =
A^i * (
c_0 * A^0 +
c_1 * A^1 +
c_2 * A^2 +
...
c_n * A^n) =
A^i * c(A) =
0
- 最小多項式は、「最小多項式の次数の上限n」「列の先頭2n要素」の2つだけで構成可能
- 体上の最小多項式は、Berlekamp–Massey algorithmで計算できる。資料
- 体上のベクトル{b_i}の最小多項式は、ランダムベクトルuを取ってきて、{u^t b_i}の最小多項式と高確率で一致する。
- 体上の行列{A_i}の最小多項式は、ランダムベクトルuを取ってきて、{A^i u}の最小多項式と高確率で一致する。
- 最小多項式が既知ならば、線形漸化式の第j項はO(k^2 log j)で計算可能。
b_i = a_i
b_i+k =
c_0*+b_i+0 +
c_1*b_i+1 +
...
c_k-1*b_i+k-1
f = x^k - c_0 x^0 - c_1 x^1 - ... - c_k-1 x^k-1
x^j mod f = d_0 * x^0 + d_1 * x^1 ... d_k-1 * x^k-1
x^2n mod f = [xの2k-2次多項式] mod f = [xのk-1次多項式]
O(k^2) ①
①はx^i (i <= 2k-2)を前計算O(k^2)することで、O(k^2)で計算可能。
最後の合成ではlog j個の掛け算を行うので、全体でO(k^2 log j)
コンパニオン行列の累乗 †
- 二つの実装方法があり、後者のほうがメモリ効率が良いためかなり速い
- 行列の形に注目するもの
- 線形漸化式の線形性と、本質的に多項式の乗算除算であることを使う（つまりはこういうこと）
- その他説明
- コンパニオン行列の累乗（これが前者の方法で、これを実装すると遅いので注意）
- 古くは Krishnamurty [2] に発見され，その後 [1, 3, 4] によって再発見されている．
- ヘッセンベルク行列のべき乗への拡張は Datta and Datta [5]によって提案されている
- O(n^2 log k)
加群の行列演算 †
- 環R上の左加群なら、(+, *)じゃなくても行列演算が可能
- 零元と単位元が何かをものすごく気をつける必要あり。意識しないと死ぬ。
- 零元「足し算すると変わらない、かつ掛け算すると0になる」
- 単位元「掛け算すると変わらない」
- 普通の行列演算でいう0を零元、1を単位に書き換えないといけない。
非自明数え上げ †
無向グラフの頂点iから頂点jにちょうどk歩で行く場合の数 †
- 参考
- 「無向グラフの頂点iから頂点jにちょうどk歩で行く場合の数」＝「隣接行列Aとする。A^kのi, j成分」である。
- 閉路を考えるなら、i==jとすればよい
- 注意点
- 交差しているものも数え上げる！
- i=A, j=B, k=4としたとき、A->B->A->B->A->Bとかも数える。
無向グラフのk歩で戻ってくる閉路の個数 †
- 無向グラフのk歩で戻ってくる閉路の個数
- 開始頂点は指定できないので注意！
- k=3からk=12くらいまでは公式がある。
- 公式は非常に複雑なので、ここを見るか、ライブラリをそのまま使う。
無向グラフの全域木の数え上げ †
- 「無向グラフの全域木の数」＝「ラプラシアン行列のn-1次部分行列の行列式」
- ラプラシアン行列とは、n行n列行列で、その (i,j) 成分が
- i=jのとき、頂点iの次数（＝頂点iから出ている辺の数）
- i≠jのとき、隣接行列の(i,j) 成分の−1倍
- 行列木定理 (Matrix-Tree Theorem)と呼ばれているもの。
二部マッチングの数え上げの偶奇 †
- 隣接行列の行列式で計算できる。
- 二部マッチングの数え上げそのものはNP完全
元の隣接行列
011
110
011
数え上げるべき組み合わせ
001
100
010
010
100
001
転倒数の数え上げ †
- 問題そのものは「クロッシング問題」と呼ばれる。
- 要するにバブルソートの交換回数。転倒数は反転数とも呼ばれる。
- 愚直にはO(n^2), 普通にはO(n log n), 世界最速はO(n sqrt(log n))
- 解法
オイラー閉路の数え上げ †
- BEST theorem
- オイラー路はグラフの全辺を使うパス
- オイラー閉路は、閉路であるオイラー路。
多項式 †
畳み込み †
- FFTとかNTTを使うとO(n log n)で計算できる
公式 †
- 総和の分解
- &ref(): File not found: "IMG_0570.JPG" at page "プロコン";
- ARC 59C
- くくりだしの漸化式
- &ref(): File not found: "IMG_0569.JPG" at page "プロコン";
- ARC 59C
ラグランジュ補完 †
- N次式で(N+1)個の値がわかっているので、ラグランジュ補間で完全に式を求めることができる。
母関数 †
- 漸化式と母関数 [#ya65cdad]
- 講義資料
- 漸化式→母関数
- 母関数→一般項は非常に簡単
- 母関数fが有利関数ならば、漸化式は線形漸化的
- f=g/hとすると、1+deg h次の線形漸化式となる。
- 母関数を直接求める [#pa2f69f3]
- 母関数が先に簡単に求まるケース
- 「正整数の列aが与えられるとき、aの重複なし部分和でちょうどbになるものは何通りあるか？」＝「f=∏(1+X^{a_i})f=∏(1+X^{a_i})とするとき、fのb次の係数を求めよ」
- 「正整数の列aが与えられるとき、aの重複あり部分和でちょうどbになるものは何通りあるか？」＝「f=∏Σ(1+X^{j*a_i})f=∏(1-X^{a_i})^{-1}とするとき、fのb次の係数を求めよ」
結合性 †
expand(subst(subst(a3*x+b3, x, a2*x+b2), x, a1*x+b1));
expand(subst(a3*x+b3, x, subst(a2*x+b2, x, a1*x+b1)));
- 3次
expand(subst(subst(a3*x^2+b3*x+c3, x, a2*x^2+b2*x+c2), x, a1*x^2+b1*x+c1));
expand(subst(a3*x^2+b3*x+c3, x, subst(a2*x^2+b2*x+c2, x, a1*x^2+b1*x+c1)));
高次連立漸化式の係数変更クエリ †
- まず、漸化式を愚直に代入すると、各漸化式毎に出てくる項は有限であることがわかる。
- 従って、各漸化式ごとに、1つ前の係数から次の係数を計算する行列を計算することができる。
- これを対角に連結（してもしなくてもいい）すると、行列連鎖積*初期値になるので、Segment Treeで計算できる
&ref(): File not found: "IMG_0665.JPG" at page "プロコン";
場合の数 †
カタラン数 †
点群処理 †
2つのsetを同時更新 †
- 範囲のどれかが0であれば、2つのsetを同時更新するだけでkd-tree相当の処理がO(log n)、しかもnot amotizedで処理可能
- set<int, int> fs, sf; // first-second, second-first
- CF 366 D2C
kd-tree †
- 平衡Dynamic kd-tree
- spaghetti codeにあるやつ
- 二次元閉区間の点を追加、点を削除がO(log n + k), k=ヒット数、amortizedで処理可能。
- 点に情報を乗せることもできるはず
- スケープゴート的に平衡処理する
- CF 366 D2C
応用：2D Euler Tour †
- iwiwi先生の木のクエリ完全制覇
- 1D Euler Tourだと群的データしか載せられなかったのが、これだとモノイドも載せられるっぽい
盤面 †
上書き †
DP †
マトロイド †
- よくわかってないし必要かもよくわからない。
- http://d.hatena.ne.jp/drken1215/20121212/1355280288
- ある集合がマトロイド＝ザイズが同じ一番大きな集合を何個か持ってきたものをマトロイドとする
- マトロイドの基＝極大独立集合
- マトロイドの集合から任意個数の要素を削ったものをマトロイドに加える
- このように出来たものがマトロイド
- マトロイドの要素は「独立な」集合と呼ばれる。
- 単位時間ジョブスケジューリング問題（http://topcoder.g.hatena.ne.jp/spaghetti_source/20121103/1351911603参照）
- ベクトルマトロイドに用いる問題（SRM 526.5 DIV1 Hard）
- 行列Aが与えられたとき、Aの列ベクトルをa_1, a_2, …, a_nとすると、M = {a_1, a_2, …, a_n}、I = (Mの部分集合のうち、一次独立なモノの集合)とすると、(M, I)はマトロイドとなります。これはベクトルマトロイドと呼ばれます。
- グラフの枝集合に対して森はマトロイド。最大独立集合は全域森
- 2つの基に対して、かぶっていないものを交換しても両方ともマトロイド。これをマトロイドの交換公理と呼ぶ。基と基でこれをやると、同じように交換後も基である。これは凄くて、凸っぽい。
- マトロイド(M, B)に対し、ある基Sが与えられたとすると、以下の2つは同値である。「Sが最大重みの基」「Sの近傍となる基S^’で、Sよりも重みが大きい基は存在しない」これはまさにGreedy!
Gray Code †
- ハミング距離が常に1の表現
- 使い道
- アブソルートロータリーエンコーダで隣り合った角度のハミング距離がでかいとこまる
- 遺伝アルゴリズムで使うと性能が上がる
細々した定数倍高速化 †
vectorのreserve †
ループアンローリング †
- ループアンローリングで20%くらいの高速化できることがある。
- キャッシュが乗るらしい。よくわからない。
emplace_back †
- moveが呼ばれるので少し早い
- たとえば以下の2つはほぼ同じだが、メモリ確保回数が減る
vector<vector<int>> vvi;
vvi.push_back(vector<int>(10));
vvi.emplace_back(10);
bit並列 †
- これは「細々として」ないかも
- bitの状態をまとめて持つことによるDPの高速化。64bitだと64倍高速化になることも！
- intが32bitなのに対して欲しいものが8bitとかの時にまとめて計算する並列化手法。文字列でよく使われてる
SSE †
- SSE?
- SSE具体的には、mask使うとifを簡単に表現できたりするけど、コンパイラもそこまではやってくれないとか
Dancing Links †
埋め込み †
- 漸化式の途中計算を0, 10000, 100000などと埋め込むことで、高速化する方法。
- 式そのものを埋め込むことも
Range Tree †
- 特に、指定された区間や点にオーバーラップする全ての区間を探すという問題を効率的に解くことができる。
- 例えば、表示されている地図内に見えている全ての道路を求めるとか、3次元のシーンで見えている全てのオブジェクトを求めるといった用途に使われる。
「データ構造をマージする一般的なテク」 †
- 挿入が定義されたデータ構造がn個ある。この時「片方Aのデータを全てもう片方Bに挿入し、Aをclearする」というマージ操作において、必ず|A|<=|B|とする。すると挿入操作をO(T(n))として
- 最悪計算量O(n log n T(n))
- ならし計算量O(n T(n))
- なお、集合サイズの制約がないと、最悪O(n^2 T(n))となる。
- 「挿入が定義されたデータ構造」とは？
- vector
- set
- priority_queue（併合をサポートするLeftist HeapやSkew Heapで併合ならしO(log n)なので、そっちを使うべき）
- Quick-Findはvectorでこれを行ったUnion-Findもどき
整数計画法 †
- 大概のアルゴリズムは整数計画に落ちる
- 綺麗な形なのでなんとなく楽しいが、実際に解くのはNP困難の上、IPソルバは非常に長いので現実的には使えない（と思っている）
- 整数計画に落としたあとに、多項式時間で解くためのコツをまとめる
変数定義 †
証明でよくある手法 †
- S=Σxと置く。
- Sから1つかけているなら、S-x_iときちんと変形
- T>Sなる超大きな定数を前提する（あとでそのようなTが存在することを示す必要あり）
=存在性証明の顔をして一例あげてしまう
存在性証明の顔をして一例あげてしまう †
- 存在性証明は、順逆の証明をするのだが、まるで二回順方向に証明しているように示す
- まず必要条件を示す
- つぎに解を具体的に提示（むつかしい。元の拘束条件から求める）
- その解を拘束条件に代入して、必要条件と同値を示す
- &ref(): File not found: "IMG_0595.JPG" at page "プロコン";
ヤバくて手が付けられてないもの †
ADS †
フロンティア †
- フロンティア法の長い解説
- 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)
|
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
