TODO

概要

  • プロコンで考えるべきこと
  • 解いた問題数を増やすのは良い事なんだけど、解いた問題数を増やすためだけに、簡単な問題を解きまくるのってすげえ時間の無駄

記録

参考

下位ページ

目次

参考

勉強すべきこと

  • 2-SAT
  • Treap, RBST(k-th tree), 平衡二分木
  • デク・優先度付キュー
  • Link-Cut Tree(木で最強)
  • インタバル木
  • k-d木
  • 分割統治法,逐次構成法,
  • 平面走査法
  • ボロノイ図とデローネイ三角形分割
  • 美術館問題
  • 最短路問題
  • Gray Code
  • 埋め込み
  • コンパニオン行列の累乗(きたまさ法)
    • 切れるUF, 辺がshared_ptrみたいになっている。
  • ADS
  • 乱択
  • NTT
  • Blackbox Algebra
  • 高速剰余変換 O(n log n)
  • 高速xor変換 O(n log n)
  • Stern-Brocot木
  • ベルヌーイ数列挙 O(n^2)
  • 分割数 O(n√n)
  • スターリング数 O(n^2)
  • Chordal graph
  • Cograph
  • Stoer-Wagner
  • 永持-茨木法 (全点対最小カット)
  • 木の重心
  • 木のcenter
  • 有向木の部分木のハッシュ
  • functional graphをサイクルと有向木にうまく分解する
  • Knuth-Morris-Pratt
  • Aho-Corasick
  • CIPR (最長共通部分列)
  • 編集距離 O(nm)
  • SA-IS (Suffix Array) O(n)
  • 部分回文列挙
  • 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
  • Dancing Links
  • ウェーブレット行列
  • ウェーブレット木
  • Shunting-yard algorithm
  • 平面グラフ 双対なものが構成できる。
  • 永続UF
    • 2007年、ACM SIGPLAN の Workshop on ML において、Sylvain Conchon と Jean-Christophe Filliâtre が素集合森データ構造-の永続版を発表した。これは構造の以前のバージョンを効率的に保持するもので、計算機支援証明システムCoqを使って形式的に正しさが証明されている[5]。
  • 木について
(1) 頂点uの値をxに変える
(2) 頂点u, vを結ぶ最短パスの頂点のうち、最小値を答える
というクエリを、O(log n)で処理できないという結論に至った。(今の僕には)

ライブラリ

  • TODO
    • エラトステネスのかわりに区間篩を使って実装。
    • 区間篩じゃないとかなり大きい範囲の素数全列挙はできないという噂
アルゴリズムとリンク概要計算量
二分探索単調関数の境界面をlog(N)で計算。Nは探索空間。
Union Find「xとyの集合をまとめる」「xとyの集合が同じか判定」分割はできないのが重要な制約構築O(n), union, findは両方O(A(n))
BFS on tree幅優先探索で頂点rを始点とする最短距離を求める。O(V)
Bellman Ford1点から全点への最小コスト。負の閉路がない連結グラフを入力。あった場合は検出できる。O(V E)
Johnson前処理 O(V E). 中間処理 O(V E log V). 後処理 O(V^2).
Warshall Floyd全点から全点への最小コスト。O(V^3)、だが漸化式が単純なので速い。
Dijkstra1点から全点への最小コスト。コストは正でなければならない。O(E log V)
K ShortestO(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 ConminationnCrのループを回す前処理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)

アルゴリズム各論

全探索

n^k

  • rep(i, ni) rep(j, nj) rep(h, nh) rep(k, nk) cout << i + j + h + k << endl;

深さ・幅優先探索

名前データ構造デメリットメリット
DFSstack最適性は保証されない省メモリで全探索可能
BFSqueueメモリをいっぱい使うHITしたものが最短経路経路であることが保証される

n!

  • next_permutation

nCr

  • next_combination
  • めんどい場合はnext_permutationを使っても良い

基本

二分探索

  • デバッグ
    • 特性関数だけまず確認したほうがいい
   while (1) {
       ll t; cin >> t;
       cout << check(t) << endl;
   }

しゃくとり法

データ構造の数学的構造

モノイド

opTT0
maxint0
minintinf
(+)int0
(*)int0
sort.(++)[int][]
^(累乗)int1
andbool1
orbool0
xorbool0
(++)string""
集合和[int][]
集合積[int]全体集合
gcdint0
lcdint1

範囲クエリ

まとめ

名称数学的構造構築後のデータ変更構築参照クエリ更新クエリ更新タイプ
Fenwick Tree = BITモノイド可能O(n)O(log n) 0-indexのみO(log n)点更新のみ
Fenwick Tree = BIT可能O(n)O(log n) i-indexも可能O(log n)点更新のみ
Sparse Tableモノイド可能O(n)O(log log n)不可能不可能
Segment Tree (点更新)モノイド可能O(n)O(log n)O(log n)
Lazy Segment Tree (範囲更新)モノイド、opの縮約可能可能O(n)O(log n)O(log n)点更新・範囲更新
いもす法(範囲更新、点参照)モノイド不可能O(n)O(1) 0-indexのみO(1)範囲更新
いもす法(範囲更新、点参照)不可能O(n)O(1) i-indexも可能O(1)範囲更新
ナイーブ構築ありモノイド可能O(n^2)O(1)不可能不可能
ナイーブ構築なしモノイド可能O(1)O(n)O(1)点更新のみ

BIT

  • Fenwickは、「点更新」「範囲参照(0-indexにしかならない!)」
    • もしデータと演算が群ならi-indexになる
  • Fenwick Tree=BIT=Binary Indexed Tree
    • 実装が簡単で高速。

Segment Tree

  • Segment Treeは、「範囲更新」「範囲参照」(範囲更新はlazyによって実現)
  • セグメント木
    • モノイドでいいので応用力が高く、自分で考える部分が大きい。

Lazy Segment Tree

  • 範囲に対する更新を可能にする
  • 遅延セグ木のコツ
    • あるノードより上のノードとその子のlazyを、上から全部解消すると、そのノードの本当の値が出てくる。
  • 遅延更新セグ木のアルゴリズム
    • 範囲更新の手順
    1. 更新すべき被覆X={X_i}を列挙する。以下i固定
      1. X_i以上に未解消のlazyがあれば、そのlazyを全て解消
      2. X_iの真下があれば、真下にlazyを追加
      3. X_iをdataに追加し、上方向に一貫するように更新
    • 範囲クエリの手順
    1. 更新すべき被覆X={X_i}を列挙する。以下i固定
      1. X_i以上に未解消のlazyがあれば、そのlazyを全て解消
      2. 解消後のX_iをメモ
    2. op(X)を計算
  • 実装
    • コツ:1-indexで実装し、data[0], lazy[0]は使わない

永続Segment Tree

動的Segment Tree

範囲クエリ上での二分探索

  • segment tree上の二分探索はそれだけで面白い話題っぽい

imos法

ソート

クイックソート

  • std::sort

バケツソート

  • バケツソート
    • 静的配列にひたすら突っ込むだけのソート。O(n)でソート可能。1000万はいける。
    • SRM D2E 671?

自分でソート

  • 優先度付きキューで自分でソートする
  • SRM D1E スターウォーズのやつ

バケット法

グラフ

  • 頂点は難しい、枝は簡単
  • 葉を指定した最小全域木→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で同一かによって検知可能最もコストの小さい辺を貪欲的に選び続ける方法

閉路検出

  • 有向閉路検出→SCC
  • 無向閉路検出→BFSで二度来たら閉路あり。

ダイクストラ

  • 要するに集合拡大
    • 拡大ルールは「集合から到達できる頂点のうち、最も小さいコストの頂点を拡大する」
    • 実装にはフィボナッチヒープでBFSが高速

グラフのDAG化

  • 強連結成分を縮約すると、任意のグラフはDAGになり、トポロジカルソートができるようになる

静的木

  • 木の構造そのものが切られたり追加したりしないものでの、様々な木の上でのクエリの処理方法
  • 木いろいろ

基本的な性質

  • 頂点n辺n-1かつ連結なら必ず木構造
  • 木構造はどこを根にしても木構造

できること

名称計算量説明
最短パスの頂点に乗ったデータの積分(群限定)O(log n)オイラーツアー+範囲参照データ構造
頂点から根へ向かうパスの二分探索O(log n)ダブリングで可能
  • 木に対する積分
木の構造データ対象データの変更できることできないこと備考
静的部分木可能群積分・部分木更新特になし
静的最短パス可能群積分min, max範囲更新もできる気がする(正に加算、負に減算するような操作はlazyできそう)
静的最短パス不可能モノイド積分データをあとから書き換える
動的最短パス可能モノイド積分特になし2D Euler-Tour+領域木で行けそう
  • 辺に関するクエリは、頂点に持たせることで同様に積分できそう

オイラーツアー

  • オイラーツアーはDFS順序とも呼ばれる。
    • bfsの経路を添え時に直したもの
    • 木を列で扱える!
      • しかも、各頂点番号が最初に登場するインデックスと最後に登場するインデックスの間が部分木に。
      • 上から下への辺の重みも、上から下への経路で無向グラフ辺を足したものとして表現できる。
    • セグメント木などのデータ構造を扱えるようになる!
      1. 部分木のコストを変える・部分木のコストのsum, min, maxを求める。(無向辺のコストを両方向正にして実現)
      2. 辺(上から下へに限定)のコストを変える・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|
      • Eには頂点が二回ずつ必ず出てくる
    • 頂点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)で計算できる。

頂点から根までの列の二分探索

  • 先祖のダブリングによって実現

再帰

返り値をメモするタイプの再帰

  • 異常条件→メモ条件→遷移→メモ→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漸化式の方向が逆のもの特になし
配る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];
    1. i: 0 1 2 3 4 5
    2. 0: 0 2 7 5 3 2
    3. 1: 2 9 12 17 20 22
    • ↑を0の配列のみを使って更新してみよ

区間DP

  • とはなにか
  • SRM 693 D1E

bitDP

  • bitDPのコツ
    • 「部分集合と初めと終わりさえ決まっていれば、余集合の最適解は変わらない」
      • 初めを持つ必要がないことが多々
    • n!はダメだけど2^nがOK系は、とにかくbitで状態を持つことを考える。
    • http://www.slideshare.net/iwiwi/ss-3578511 (50ページ目がわかりやすい)

挿入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;

Link Cut Tree

最小辺カバー

高速フーリエ変換

Subset Convolution

高速ゼータ変換

高速メビウス変換

文字列操作

boyer moore search

  • 早い文字列検索
  • m文字を探す時、BM法の計算量は、最悪O(n)、平均的な場合O(n/m)

MP

  • MP
    • O(n)で、文字列 S が与えられたときに、各 i について「文字列S[0,i-1]の接頭辞と接尾辞が最大何文字一致しているか。ただし|S[0,i-1]|未満の一致とする。」を記録した配列を計算。

Manacher

  • Manacher
    • 各 i について「文字 i を中心とする最長の回文の半径」を記録した配列 R を O(|S|) で構築するアルゴリズム

ローリングハッシュ

Zアルゴリズム

  • Zアルゴリズム
    • 「0から長さn-jと、jから長さn-jのLCP」が構築O(n)クエリ(1)で計算できる。
  • 解説付き
  • ちょっと雑

Suffix Array

  • Suffix Array
    • iとjから始まる文字列からのLCSクエリO(log n)
    • ある文字列が含まれているか?containクエリO(log n)
    • 構築方法
      1. Suffix Array 構築O(n^2 log n)=比較O(n)*ソートO(n log n)
      2. SA-IS 構築O(n) (Two Efficient Algorithms for Linear Time Suffix Array Construction [G Nong, et.al.])
      3. 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のやつ

問題集

三角数乗

  • 2^(n*n)は、三角数乗を順に求めるとO(n), 二分累乗だとO(n log n)?

座標圧縮

http://algoogle.hadrori.jp/algorithm/compress.html

Range Tree

  • 特に、指定された区間や点にオーバーラップする全ての区間を探すという問題を効率的に解くことができる。
  • 例えば、表示されている地図内に見えている全ての道路を求めるとか、3次元のシーンで見えている全てのオブジェクトを求めるといった用途に使われる。

二分木

  • やりたいことは「ソートしながらデータを持つ」データ構造
    • std::mapみたいな感じ
  • 追加も削除もある場合の頻出テク
    • クエリの(平方)分割
    • がんばって動的になんとかする

愚直な方法

  • 頂点の左は必ず小、頂点の右は必ず大
  • クエリ
    1. insert(x): 頂点がxより小さければ左遷移、大きければ右遷移、を繰り返してNULLポインタにあたったらそこにnew
    2. 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が右を下げること。
  • クエリ
    1. insert, erase
    2. split, merge: [0, k)と[k, n)の2つの列に分割、マージ
    3. 値に関する質問・更新: sum, addなど
  • 各論
    • Treap: キーと一緒に「優先度」を持つ。キーを見ると二分探索木、優先度を見ると二分ヒープ(常に親が子より大きい)になるように木を構成
    • Splay: 2つ親までを見れば、回転によって平衡化が可能なことを利用した平衡木。頂点xを根の場所まで移動させてできる木を返す

重軽分解

Link Cut Tree

  • Link-cut Treeのなりたち(下に行くほど実装が重い)
    1. 頂点vから根へのパスをつなげる(expose, 必須で平衡二分探索木のsplit, mergeを使う)
    2. 頂点の親を変更(link)、削除(cut)
    3. 木の根を求める(root), 木の根を変更(evert)
    4. パスに対する頂点・枝の値のクエリ(sum, max, 更新)
  • コンセプト
    • ツリーを分解してパスにします。
    • パスをsplay木で管理します(パスの順序さえあってればいいので、根は自由に選べる。よく実線をsplay木内部の辺、点線をsplay木間の辺として表記する)

Euler-Tour Tree

  • Euler-tour treeとLink-cut treeは同様に神がかり的木

永続

  • 永続(persistent)=バージョン管理して、undoできる!

ゲーム

ゲームの分類

  • 二人
    • 四人(麻雀)
    • 二人(将棋・囲碁・オセロ)
    • 一人(ソリティア)
  • 有限
    • 有限回で終わるゲーム
    • ゲーム木(=局面全体を頂点集合とし、局面Pから局面Qに移動できるとき、PからQに矢を作って得られるグラフ)において、どの頂点から始まる有向パスの総数も有限

Gray Code

  • 面白い特徴のバイナリ表示らしい。

ビット並列アルゴリズム

埋め込み

乱択

幾何

計算のロバストネス

  • 誤差が非常に効いてくるケースが少ないので、なるべく計算誤差が少ないような演算方法が重要

点の進行方向

  • ccwはロバストな進行方向の計算方法
  • angle は三角関数の計算という不動小数の計算を必要とするが,ccw は係数環の演算だけで構成されているので,極めてロバスト

凸包構築

  • 凸包は基本的にはO(n log n)
  • 基本的にはAndrew's Monotone Chainを使うのがいい
    • 上凸と下凸包を計算して、あとでマージする。

Connectivity

Incremental Connectivity = Union-Find Tree

  • 「同じ集合は同じ根を持つ木である。根は-要素数を持つことでsizeを持つ」である
  • 工夫も実は簡単で、(1) uniteの時に木の浅い方にくっつける。 (2) Findの時に、通ってきた経路を全部根からの多分木にするである。
    • 片方でO(log n)両方でO(A(n))
  • 盤面問題をUnionFindで

永続Union-Find

Decremental Connectivity

  • えー
  • 問題によっては逆から見ればUFに落ちるらしい

Dynamic Connectivity

細々した定数倍高速化

vectorのreserve

ループアンローリング

emplace_back

  • moveが呼ばれるので少し早い
  • たとえば以下の2つはほぼ同じだが、メモリ確保回数が減る
vector<vector<int>> vvi;
vvi.push_back(vector<int>(10));
vvi.emplace_back(10);

bit並列

  • これは「細々として」ないかも
  • bitの状態をまとめて持つことによるDPの高速化。64bitだと64倍高速化になることも!

SSE

ヒープ

  • 二分ヒープがpriority_queue
  • フィボナッチヒープが最速

Convex Hull Trick

Mo's Algorithm

貪欲

証明方法

  • えー

ビームサーチ

  • n個残す貪欲法

行列

行列のクラス

名称行列と行列の積普通のk乗行列累乗k乗行列累乗(BLA)
一般O(n^3)O(n^3 log k)O(n^3+M(n)log k)
巡回行列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(n2)だが、R=Z/mZR=Z/mZの場合はFFTを用いることでM(n)∈O(nlognloglogn)M(n)∈O(nlog⁡nlog⁡log⁡n)にできる。
  • Blackbox linear algebraによる行列式
    • O(n^2+n T(n))

行列式

  • 普通には全体でO(n^3)
  • 行列木定理と呼ばれる定理は、 グラフが与えられたとき、全域木の個数を行列式を用いて求められる
    • 非自明数え上げが多項式時間でできるすごい。

Blackbox linear algebra

コンパニオン行列の累乗

加群の行列演算

  • 加群なら、(+, *)じゃなくても行列演算が可能
  • 零元と単位元が何かをものすごく気をつける必要あり。意識しないと死ぬ。
    • 零元「足し算すると変わらない、かつ掛け算すると0になる」
    • 単位元「掛け算すると変わらない」
  • 普通の行列演算でいう0を零元、1を単位に書き換えないといけない。

Dancing Links

  • 幼稚園児高橋君のやつ

「データ構造をマージする一般的なテク」

  • 挿入が定義されたデータ構造が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もどき
    • Union O(log n)
    • Find O(1)

ヤバくて手が付けられてないもの

ADS

NTT

フロンティア

  • フロンティア法の長い解説
  • 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)

浮動小数点

  • (ll)pow(3, 3) = 26なので、roundを使うこと

トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS