- 追加された行はこの色です。
- 削除された行はこの色です。
[[TODO]]
*概要 [#p5677d79]
-プロコンで考えるべきこと
-解いた問題数を増やすのは良い事なんだけど、解いた問題数を増やすためだけに、簡単な問題を解きまくるのってすげえ時間の無駄
*記録 [#g025ad7f]
-[[Topcoderのはむこと分布>https://www.topcoder.com/members/hamko]]
-[[Codeforcesのはむこと分布>http://codeforces.com/profile/hamko]]
-[[はむこ主催の勉強会>https://docs.google.com/document/d/1CUFgykFSFBg2EdKseUAuQCsDrJgI92Ip_1BJD3J_roI/edit]]
-[[プロコン記録>https://docs.google.com/spreadsheets/d/1zYQDdJYxtZRr9s7U_dCtZEHfehu5_Qq7wtGemNM3tT4/edit#gid=0]]
*参考 [#f5c97c65]
-問題集
--[[ICPC非公式難易度>https://docs.google.com/spreadsheets/d/1_UCibOHFR2tQDwNBsg7uORuGJoP7jy_ckWpQhzhdYUM/edit#gid=0]]
--[[rng問題>https://docs.google.com/spreadsheets/d/1-dwOvCUGF7ITCYXg2LUFo0YqvZc7PTNX3jz1USuXuBE/edit#gid=408778518]]
--[[snuke問題>https://docs.google.com/spreadsheets/d/1jQ7nCYwCM_fKY3H5aqrjJ1sZLE02m9VXh7kpWuE-WYc/edit#gid=13]]
--[[sugim問題>https://docs.google.com/spreadsheets/d/1ohGEbAMNI5Gl2WlPqw-LOtkQB5GlXFhwPgK_0svKnQM/edit#gid=0]]
-[[岩田さんの指数時間アルゴリズム>http://www.slideshare.net/wata_orz/ss-12131479]]
*下位ページ [#qc53e894]
-[[初心者向けプロコン]]
#ls
*目次 [#n328e6e1]
#contents
*参考 [#y81fa88b]
-[[Div2 Hard 講評>http://nagoyacoder.web.fc2.com/topcoder/topcoder_div2hard.html]]
-[[診断人さんのDP>http://shindannin.hatenadiary.com/entry/20131208/1386512864]]
-[[非公式難易度表>https://docs.google.com/spreadsheets/d/1_UCibOHFR2tQDwNBsg7uORuGJoP7jy_ckWpQhzhdYUM/edit#gid=7]]
-[[Spaghetti>http://www.prefield.com/algorithm/]]
-[[tubo28>http://tubo28.me/algorithm/]]
--現代的な書き方
-Antaさんのライブラリ
--https://www.dropbox.com/sh/9lknvq4xay709cn/Ly2afJ-87e/%E3%83%A9%E3%82%A4%E3%83%96%E3%83%A9%E3%83%AA%E3%81%BE%E3%81%A8%E3%82%81.txt
--http://d.hatena.ne.jp/anta1/
--https://www.dropbox.com/sh/9lknvq4xay709cn/J96DtYOP8V
*勉強すべきこと [#x5163fe2]
-2-SAT
-[[Treap, RBST(k-th tree), 平衡二分木>https://docs.google.com/document/d/1QuPsq6an9MKjTOGxKnNi2TwAqgS7o5Aissnipzl6OOI/edit]]
-デク・優先度付キュー
-[[Link-Cut Tree>http://www.slideshare.net/iwiwi/2-12188845]]（木で最強）
-インタバル木
-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]。
*ライブラリ [#ff8ddfbd]
-TODO
--エラトステネスのかわりに区間篩を使って実装。
--区間篩じゃないとかなり大きい範囲の素数全列挙はできないという噂
|アルゴリズムとリンク|概要|計算量|h
|二分探索|単調関数の境界面をlog(N)で計算。Nは探索空間。||
|Union Find|「xとyの集合をまとめる」「xとyの集合が同じか判定」分割はできないのが重要な制約|構築O(n), union, findは両方O(A(n))|
|BFS on tree|[[幅優先探索>http://tubo28.me/algorithm/shortest-path-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)|
*アルゴリズム各論 [#gc237b0d]
**Blackbox linear algebra [#n71642f1]
-[[antaさんの記事>http://yukicoder.me/wiki/black_box_linear_algebra]]
**RMQ [#l87d5a5b]
-3種類処理の方法があったはず
**ソート [#m7790d04]
***クイックソート [#x6e6f773]
-std::sort
***バケツソート [#z1540299]
-バケツソート
--静的配列にひたすら突っ込むだけのソート。O(n)でソート可能。1000万はいける。
--SRM D2E 671？
***自分でソート [#fa7299aa]
-優先度付きキューで自分でソートする
-SRM D1E スターウォーズのやつ
**バケット法 [#kf0e46dd]
-バケット法=平方分割＝sqrt(n)分木
--範囲を扱う時に、平方に分割して記憶することで前処理O(n)、各クエリO(sqrt(n))を実現
--応用力が高く、自分で考える部分が大きい。各バケットが2分探索木やBITを持ってたりする。
--応用範囲は、バケット法>セグメント木。
--速度はバケットO(sqrt(n))<セグメント木O(log n)
-例題
--http://pekempey.hatenablog.com/archive/category/%E5%B9%B3%E6%96%B9%E5%88%86%E5%89%B2
--http://tubo028.hatenablog.jp/entry/2014/06/30/174028
--http://sssslide.com/www.slideshare.net/hcpc_hokudai/rmq-47663507
--[[文章の解説>http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%80%8A%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E6%B3%95%E3%80%8B]]
--[[tuboさん>http://tubo28.me/algorithm/sqrt-decomp/]]
--[[1>https://www.google.de/url?sa=t&rct=j&q=&esrc=s&source=web&cd=21&ved=0ahUKEwjPmaX8nO3MAhUBFxQKHSTVD9A4FBAWCBwwAA&url=http%3A%2F%2Fresearchmap.jp%2F%3Faction%3Dmultidatabase_action_main_filedownload%26download_flag%3D1%26upload_id%3D30931%26metadata_id%3D993&usg=AFQjCNHqislUacfLHPFiJuxREOiXkH-ntA&sig2=HCrPdUmyjbpwlr4NwLS_uQ]]
--[[分割統治法との関係>https://www.google.de/url?sa=t&rct=j&q=&esrc=s&source=web&cd=26&cad=rja&uact=8&ved=0ahUKEwjPmaX8nO3MAhUBFxQKHSTVD9A4FBAWCEAwBQ&url=http%3A%2F%2Fwww.akashi.ac.jp%2Fcontents%2FGakusei%2Fshirabasu%2F20nendo%2FPdffiles%2F20050403400.pdf&usg=AFQjCNFQLqFVqjaHTFgfvOhnPfVpAF18-g&sig2=sXecOTThM-9oiefR9O-rtA]]
**BIT・セグメント木 [#ib2b69ef]
-「データ型T, 二項結合演算op、単位元T0」が定義できると、構築O(n), 更新O(log n), 範囲参照O(log n)のデータ型が定義可能
--Fenwickは、「点更新」「範囲参照」
--Segment Treeは、「範囲更新」「範囲参照」（範囲更新はlazyによって実現）
-[[単位元を持つ二項結合演算とは？>http://akiradeveloper.hatenadiary.com/entry/2015/04/29/165135]]
|op|T|T0|h
|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|使い道|h
|max, min|RMQ、DP加速|
|(+)|DP加速、オイラーツアー|
***Segment Tree上の二分探索 [#cee036ad]
-segment tree上の二分探索はそれだけで面白い話題っぽい
**Dancing Links [#j3a89071]
-幼稚園児高橋君のやつ
**グラフ理論 [#e41853df]
-頂点n辺n-1かつ連結なら必ず木構造
-木構造はどこから見ても木構造、おぼえましたし
-このスライドめっちゃいい
-本「離散凸解析の考え方」
-http://www.slideshare.net/tmaehara/ss-17402143
--なんか関数定義をして、それが凸かどうかを判断して、云々している。とてもよい。
-頂点は難しい、枝は簡単
-葉を指定した最小全域木→Kruskalの変形
-分散最小全域木、比最小全域木などは、パラメータ化して何かを止めると凸にする
-k-th最小全域木
|名前|計算量|アルゴリズム|特徴|h
|ベルマンフォード法|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で同一かによって検知可能|最もコストの小さい辺を貪欲的に選び続ける方法|
***閉路検出 [#ia83b6ad]
-有向閉路検出→SCC
-無向閉路検出→BFSで二度来たら閉路あり。
***ダイクストラ [#j53a40c7]
-要するに集合拡大
--拡大ルールは「集合から到達できる頂点のうち、最も小さいコストの頂点を拡大する」
--実装にはフィボナッチヒープでBFSが高速
**静的な木 [#y4c5ec51]
-木の構造そのものが切られたり追加したりしないものでの、様々な木の上でのクエリの処理方法
-[[木いろいろ>https://topcoder.g.hatena.ne.jp/iwiwi/20111205/1323099376]]
***オイラーツアー [#l7ff8485]
-オイラーツアーはDFS順序とも呼ばれる。
--bfsの経路を添え時に直したもの
--''木を列で扱える！''
---しかも、各頂点番号が最初に登場するインデックスと最後に登場するインデックスの間が部分木に。
---上から下への辺の重みも、上から下への経路で無向グラフ辺を足したものとして表現できる。
--セグメント木などのデータ構造を扱えるようになる！
+++部分木のコストを変える・部分木のコストのsum, min, maxを求める。（無向辺のコストを両方向正にして実現）
+++辺（上から下へに限定）のコストを変える・u から v へのパスのコストのsum, min, maxを求める（無向辺のコストを片方1片方-1にして実現）
-[[オイラーツアーによるLCA(47ページ)>http://www.ioi-jp.org/camp/2013/2013-sp-tasks/2013-sp-day4-spaceships-review.pdf]]
--構築O(n), RMQによる最小値判定O(log n)
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
***最短パスの頂点に乗ったデータの積分 [#de70c9c6]
-頂点に群のデータを載せるタイプのオイラーツアーで実現できる。
--木Gが与えられる。
--木Gの根からの、オイラーツアーEを考える。|E| = 2*|G|である。Eには頂点が二回ずつ必ず出てくる。頂点iがオイラーツアー上で出てくる1回目を、f_i, 2回目をs_iとする。(fはfirst, sはsecond)
例)
0
1 4
3 5 6
のオイラーツアーは
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)で計算できる。
***頂点から根までの列の二分探索 [#y5026aa7]
-先祖のダブリングによって実現
**DAGからフロンティア [#w72b5342]
-フロンティア法の長い解説
--[[C++プログラムも>http://www-lsm.naist.jp/~jkawahara/frontier/]]
--[[資料>http://www-lsm.naist.jp/~jkawahara/frontier/frontier_lec.pdf]]
-DAG
--Directed acyclic graphとは、閉路のない有向グラフ。
-トポロジカルソート
--DAGを列に変換すること。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B&lang=jp
-BDD
--[[何に使えるか？http://www.ai-gakkai.or.jp/my-bookmark_vol27-no5/]]
--n変数0/1論理関数を効率良くグラフとして表現するデータ構造である。
-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の頂点数)
--[[お姉さん本>http://www.amazon.co.jp/gp/product/4627852614/ref=as_li_ss_tl?ie=UTF8&camp=247&creative=7399&creativeASIN=4627852614&linkCode=as2&tag=jmukorg-22]]
--集合族を表現するZDD
--BDDと違うのは、頂点削除のルールのみ
---BDDは「ここが0でも1でも結果が変わらない→頂点削除」
---ZDDは「ここが1だったらどうやっても結果が0になる→頂点削除」
--疎な部分集合族を表現するのに適している
--BDD同様、ZDD 同士の演算がそのままできる（Family Algebra）
-フロンティア法
--ZDDはめちゃめちゃメモリ食う（1頂点当たりO(V)）
--実は、フロンティアの連結と次数だけ覚えれば十分
-その他
--文字列集合を表現する SeqBDD (Sequence BDD)
--置換の集合を表現する πDD (PiDD, Permutation DD)
**メモ化再帰 [#ocefc68a]
-大きく分けて2種類のメモ化再帰がある。
-返り値をメモするタイプの再帰（異常条件→メモ条件→''遷移→メモ''→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 [#mb392f04]
-難しさ
--分かったつもりで実際に問題をといても、アクセプトされない。
--デバッグしにくいので、しかも何でアクセプトされないかわからない。
***参考 [#bebe12ee]
-[[DPはDAQ上の最短経路問題である>http://d.hatena.ne.jp/Tayama/20111210/1323502092]]
***DPの漸化式 [#p1f7a426]
-コツ
--「i''未満''の添字を使って」という表現をする
--「〜が確定している時」という表現をする
***DPの種類 [#cbd1285a]
|名前|特徴|できること|h
|戻るDP|漸化式の方向が逆のもの|特になし|
|配るDP|漸化式の関数が可換、かつ漸化式の関数に単位元が存在し、かつ更新前の添字から更新後の添字を計算可能|実装が楽。配れないならcontinueできる|
|集めるDP|更新後の添字から更新前の添字を計算可能|汎用的|
|前回のみに依存するDP|空間計算量が抑えられる。DP配列を2だけ用意して偶数奇数で分ければいい。''配る前回のみに依存するDPは初期化に注意''|
|一方向に依存するDP|前回のみに依存し、かつ更新式が''後ろにのみ''依存する場合、添字を前から後ろに回して、空間計算量を更に抑えられる。DP配列を使いまわせるので。|
***DPのデバッグ [#k679b527]
-コツ
--変更後の状態を
--別のループで
--自明でないものだけ出す！
***DPはメモ化再帰のループ版 [#g87e3e37]
-メモ化からの漸化式構築＝動的計画法
--「これまでに得られる〜」をメモ化する
--幅・深さ優先探索のメモ化のときに保存した状態と、ここで計算するテーブルの状態変数は一致する
--「ありえない組み合わせ」というものが存在する
-''DPは指数計算量探索の合流である''
--探索の「状態」と「合流法則」を抽出したものがDPとなる
--まず指数計算量探索を図示してみる
--丸の中に状態（＝添字や重さや価値）を書いたグラフを書いてみる
--すると、合流を見つけることができる。合流のルール（＝その上流すべての情報の集め方）を抽出する
--状態と合流から自動的にDPが計算できる
-初期条件は''初めが決まっていることも、深いところの拘束条件があることもある''
--DPでは深いところしか決まっていないとやりづらい
--場合の数も、初めに自明に決まる場合の数から始めるとDPが楽になる
***何を考えるべきか [#re9664cf]
-自明な条件（＝初期条件）はないか
--「1個も取らないと答えは自明に0」
--「最後の1つだけを取ると自明に1」
-1セット
--状態を適当に定めてみる
--今の状態から次の状態がどう決まるかを考えてみる
--次の状態が今の状態から統合されるかを考える
--何の情報が足りないかを考え、情報を状態に追加する
***全探索との対応 [#pac9aa5a]
||グラフ分析|メモ化探索|DP|h
|状態|ノード|引数|DPテーブル添字|
|値|ノードに付属する値|返り値|DPテーブル|
|遷移|上から下への操作|再帰関数（更新）|漸化式（代入演算）|
|結合法則|二つ以上のノードから一つへのリダクション|再帰関数（結合）|漸化式（左辺値）|
|初期条件|初めのノード|関数呼び出し|境界条件|
***例：A未満の非負整数を数える [#ofc3b480]
-[[桁DP>http://pekempey.hatenablog.com/entry/2015/12/09/000603]]が入門に非常によいと思う。
-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;
}
***実装の構造 [#hef767a0]
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番目を選ぶ
***初期値 [#j203fda6]
-''[[探索がベースの DP はどこから始めれば全列挙ができるか考えると自然に初期値が定まる>http://pekempey.hatenablog.com/entry/2015/12/09/000603]]''
--初期値を定めることは探索ベースの時の関数呼び出しに相当する！初期値
--初期値はDPの定義外．（そうじゃないと，空集合に対する場合の数みたいなのって扱われるべき？i=0, つまりAが空集合の時の場合の数が自明になる？A未満であることが確定している(j = 1)、「空集合」の元である自然数の場合の数は？→0A未満であることが確定していない(j = 0)、「空集合」の元である自然数の場合の数は？→1？？？本当に？？？みたいな悩み方をすることになる）
-ナップザックのような数え上げの問題では，初期値は0となる．
***一方向に依存するDP [#c90e181a]
-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
--↑を0の配列のみを使って更新してみよ
***区間DP [#lb2d164e]
-とはなにか
-SRM 693 D1E
***bitDP [#odd25c35]
-bitDPのコツ
--「部分集合と初めと終わりさえ決まっていれば、余集合の最適解は変わらない」
---初めを持つ必要がないことが多々
--n!はダメだけど2^nがOK系は、とにかくbitで状態を持つことを考える。
--http://www.slideshare.net/iwiwi/ss-3578511 (50ページ目がわかりやすい)
***挿入DP [#jae26958]
-http://mayokoex.hatenablog.com/entry/2016/06/25/114813
**基本的な探索 [#s90a9a4b]
|名前|データ構造|デメリット|メリット|h
|DFS|stack|最適性は保証されない|省メモリで全探索可能|
|BFS|queue|メモリをいっぱい使う|HITしたものが最短経路経路であることが保証される|
**累積和 [#jbb00e6f]
-コツ
--n要素配列の累積和なら、n+1個用意して0番目を単位元にする。
-二次元でも累積和できる。
-imos法
--範囲和が実現可能
--[[多次元・多字数・特殊座標への拡張が容易>http://imoz.jp/algorithms/imos_method.html]]
**Priority Queue [#x8059702]
-クエリ突っ込みながらソートしたい！という時のため。
--これだけだと、二分探索木(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;
**二分探索 [#w120e7b6]
***デバッグ [#ie98a520]
--特性関数だけまず確認したほうがいい
while (1) {
ll t; cin >> t;
cout << check(t) << endl;
}
***二分探索内全探索 [#j8e589bc]
-全探索内での二分探索としたほうが枝刈りができて速い
--http://d.hatena.ne.jp/wata_orz/20100910/1284108575
--状態s, 探索空間nとして、O(s log n)からO(s + log n log s)に落ちる
**Link Cut Tree [#x46e61fe]
-Spaceship。これはとんでもない量の解説がある。
--http://www.ioi-jp.org/camp/2013/2013-sp-tasks/2013-sp-day4-spaceships-review.pdf
--http://www.ioi-jp.org/camp/2013/2013-sp-tasks/2013-sp-day4-spaceships-sample2.cpp
--http://joisc2013-day4.contest.atcoder.jp/submissions/605906
-[[木のパスのクエリ>http://yosupo.hatenablog.com/entry/2014/12/27/034809]]
**Segment Tree [#fe1f8233]
-コツ
--非遅延セグメントツリーは、結合二項演算と単位元だけあればできる。
-Do Use Segment Tree
--（セグメントツリー＋重軽分解）
--http://d.hatena.ne.jp/simezi_tan/20140624/1403554584
***遅延評価 [#p557e768]
-範囲に対する更新を可能にする
--[[遅延平衡二分木>http://code-festival-2014-exhibition-open.contest.atcoder.jp/tasks/code_festival_exhibition_b]]
-遅延セグ木のコツ
--あるノードより上のノードとその子の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]は使わない
***永続 [#tfcb70e2]
-[[永続平衡二分木>http://joisc2012.contest.atcoder.jp/tasks/joisc2012_copypaste]]
--[[遅延評価＋永続平衡二分木>http://arc030.contest.atcoder.jp/tasks/arc030_4]]
--[[永続セグメントツリー>http://codeforces.com/contest/455/problem/E]]
--[[永続セグメントツリー>http://codeforces.com/contest/484/problem/E]]
-[[セグメントツリー中級に良さそう>http://d.hatena.ne.jp/DEGwer/20131211/1386757368]]
-実装
--[[pekempeyさんの実装>http://pekempey.hatenablog.com/entry/2016/04/21/235157]]
--[[pekempeyさんの実装2>http://pekempey.hatenablog.com/entry/2016/05/16/235152]]
***セグメントツリーその他 [#jec91c24]
-[[セグメントツリー、遅延セグメントツリー、動的セグメントツリー>http://d.hatena.ne.jp/DEGwer/touch/20131211/1386757368]]
-[[モノイドとSegment Treeを対応付けてるサイト>http://kiripon.net/posts/2015-08-26-Segment-Tree.html]]
-[[難しいセグメントツリー>http://hogloid.hatenablog.com/entry/20121227/1356608982]]
-問題集
--http://kagamiz.hatenablog.com/entry/2012/12/18/220849
--http://algoogle.hadrori.jp/algorithm/segment-tree.html
-単体の解説
--http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2012%2FPractice%2F%E5%A4%8F%E5%90%88%E5%AE%BF%2F%E8%AC%9B%E8%A9%95&openfile=Do%20use%20segment%20tree.pdf
--http://satellitefirst.blog.fc2.com/blog-entry-23.html
--http://qnighy.github.io/informatics-olympiad/joi2011-day4-apples-comment.html
--http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2015%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9C%B0%E5%8C%BA%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=H.pdf
--http://sssslide.com/www.slideshare.net/hcpc_hokudai/2016d-60984811
--http://rokugats-pc.hateblo.jp/entry/2014/06/11/222517
--https://www.ioi-jp.org/joi/2013/2014-ho/2014-ho-t5-review.pdf
--[[永続セグメントツリー>http://sigma425.hatenablog.com/entry/2014/12/30/164148]]
--[[解説>http://sigma425.hatenablog.com/entry/2014/12/30/164148]]
---これすごくよさそう。RMQでの具体的な説明
--[[githubによるプログラム>https://gist.github.com/wafrelka/f531a8ad859b63fee672]]
--[[永続構造スライド>http://www.slideshare.net/qnighy/re-15443018]]
--[[永続セグメントツリーを使う問題>http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2012%2FPractice%2F%E6%98%A5%E3%82%B3%E3%83%B3%E3%83%86%E3%82%B9%E3%83%88%2F%E8%AC%9B%E8%A9%95&openfile=I.pdf]]
--[[Re:永続データ構造が分からない人のためのスライド>http://qnighy.hatenablog.com/entry/2012/12/02/032851]]
--[[木のはなし>https://www.google.co.jp/url?sa=t&rct=j&q=&esrc=s&source=web&cd=10&cad=rja&uact=8&ved=0ahUKEwjY-uOUqPDMAhXpDpoKHdxfDTIQFghnMAk&url=http%3A%2F%2Fwww.npca.jp%2Fworks%2Fmagazine%2F2013_1%2F&usg=AFQjCNF_cG-pDst1VQRsQHfR2RtFRzFX4Q&sig2=VSmnyRL37lyPlBSeC4kyug&bvm=bv.122448493,d.bGs]]
**Connectivity [#f9a81450]
***Union-Find [#g8b79bcb]
-Union Find
--「同じ集合は同じ根を持つ木である。根は-要素数を持つことでsizeを持つ」である
--工夫も実は簡単で、(1) uniteの時に木の浅い方にくっつける。 (2) Findの時に、通ってきた経路を全部根からの多分木にするである。
---片方でO(log n)両方でO(A(n))
**永続Union-Find [#x2d0901d]
***永続Union-Find [#x2d0901d]
-[[永続union find>http://pekempey.hatenablog.com/entry/2016/05/23/041232]]
**最小辺カバー [#l236aace]
-[[最小辺カバー>http://pekempey.hatenablog.com/archive/category/%E6%9C%80%E5%B0%8F%E8%BE%BA%E3%82%AB%E3%83%90%E3%83%BC]]
**しゃくとり法 [#s2f3269a]
-しゃくとり法
--「各lに対してf([l,r))が単調増加二値関数の時、が真になる最小のrを計算」
---[[ARC22B解説 13ページがこれをそのまま実装していて、すごくわかりやすい>http://www.slideshare.net/chokudai/arc022]]
--区間から真偽を返す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])も偽となる、「もうこれ以上削れない区間」を全列挙する-例題
--[[例題>http://arc022.contest.atcoder.jp/tasks/arc022_2]]
--[[非常に基本的な問題>http://d.hatena.ne.jp/inamori/20120519/p1]]
--[[ARC 22B（39ページ目）>http://www.slideshare.net/yuki2006_debel/21-35882983]]
--[[ARC 30C>http://abc030.contest.atcoder.jp/tasks/abc030_c]]
--[[数学的解釈>http://d.hatena.ne.jp/komiyam/20120802/1343894601]]
--[[paiza>http://paiza.hatenablog.com/entry/2015/01/21/%E3%80%90%E7%B4%AF%E7%A9%8D%E5%92%8C%E3%80%81%E3%81%97%E3%82%83%E3%81%8F%E3%81%A8%E3%82%8A%E6%B3%95%E3%80%91%E5%88%9D%E7%B4%9A%E8%80%85%E3%81%A7%E3%82%82%E8%A7%A3%E3%82%8B%E3%82%A2%E3%83%AB%E3%82%B4]]
--[[例題>http://www-ikn.ist.hokudai.ac.jp/~k-kurita/pro_con/other/syakutori_method.html]]
--[[paiza>http://paiza.hatenablog.com/entry/2015/01/21/%E3%80%90%E7%B4%AF%E7%A9%8D%E5%92%8C%E3%80%81%E3%81%97%E3%82%83%E3%81%8F%E3%81%A8%E3%82%8A%E6%B3%95%E3%80%91%E5%88%9D%E7%B4%9A%E8%80%85%E3%81%A7%E3%82%82%E8%A7%A3%E3%82%8B%E3%82%A2%E3%83%AB%E3%82%B4]]
--[[素数の楽しそうな例題>http://hfuji.hatenablog.jp/entry/2016/01/11/180930]]
--[[例題>http://ry0u.github.io/blog/categories/siyakutorifa/]]
**Union Find [#t9152818]
-[[盤面問題をUnionFindで>http://arc031.contest.atcoder.jp/submissions/297951]]
**高速フーリエ変換 [#kc84e8b2]
-[[結構自然な問題>http://atc001.contest.atcoder.jp/tasks/fft_c]]
**高速ゼータ変換 [#qef794e9]
-高速ゼータ変換
--[[コード付きで非常に簡潔>https://topcoder.g.hatena.ne.jp/iwiwi/20120422/1335065228]]
--[[↑の説明>http://d.hatena.ne.jp/todo314/20120614/1339695202]]
--[[岩田さんの指数時間アルゴリズム63ページ>http://www.slideshare.net/wata_orz/ss-12131479]]
--[[kmjpさんブログ>https://www.google.de/url?sa=t&rct=j&q=&esrc=s&source=web&cd=4&cad=rja&uact=8&ved=0ahUKEwiq3PSsi_PMAhXB6xoKHc7xDCkQFgg4MAM&url=http%3A%2F%2Fkmjp.hatenablog.jp%2Fentry%2F2014%2F07%2F28%2F1030&usg=AFQjCNHNsGnLM32hcqnoCDg6AX24snWuiA&sig2=Ctb8WLaizmQonxzTCEnasQ]]
--[[高速メビウス変換>http://d.hatena.ne.jp/simezi_tan/20130522/1369203086]]
**文字列操作 [#m84550f2]
-面白そうな例題
--http://tenka1.klab.jp/2014/explain/final_e.pdf
--http://rsujskf.s602.xrea.com/?atcoder_regular_contest_024_c
--http://www37.atwiki.jp/uwicoder/pages/2842.html
--http://cielavenir.github.io/blog/2016/01/14/takahashikun-password/
--[[1>http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2015%2FPractice%2F%E5%A4%8F%E5%90%88%E5%AE%BF%2F%E8%AC%9B%E8%A9%95&openfile=day2-F.pdf]]
[[ローリングハッシュハック>http://yukicoder.me/problems/652]]
[[ローリングハッシュのメリットは群的であること>http://odan3240.hatenablog.com/entry/2015/02/16/111938]]
「N≦10^6？もしかして噂のSA-IS知らないと解けない？」
キーワード
ローリングハッシュ、suffix array->LCP, Zアルゴリズム
mayoko
IS-SAとスパーステーブルを作ってて面白そう
http://mayokoex.hatenablog.com/entry/2015/08/12/000830
suffix arrayにはランクなる概念があるらしい
suffix array->LCPの簡単な問題
http://kmjp.hatenablog.jp/entry/2016/04/23/1030
// aaabaabaaaaaaaa
// 2 7
// 5 10
ローリングハッシュ、ほとんどARC55Cと同じ問題、解説付き
複数のハッシュ値で同じならだいたい同じとみなす
[a, b]のハッシュ＝H_a - H_b*X^(b-a+1)
http://sssslide.com/www.slideshare.net/hcpc_hokudai/2015day3f
ichyoさんの文字列ライブラリ
https://github.com/ichyo/Procon-Library/tree/master/string
-[[Suffix Arrayの構築方法>http://wtkw.net/tech-blog/?p=230]]
--愚直 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のやつ
人なので
-[[Suffix Array実感>http://shogo82148.github.io/homepage/memo/algorithm/suffix-array/introduction.html]]
--Javascriptの実体験
H問題
「二次元のローリングハッシュ」
http://www.slideshare.net/chokudai/thanks2014-a
-[[ローリングハッシュ、Suffix Arrayの純粋な解説寄り>http://haraduka.hatenadiary.jp/entry/2015/09/02/214940]]
--http://trivial-contents.com/programming/algorithm/search/rabin_karp_search.html
--[[実装寄り>http://techtipshoge.blogspot.de/2011/02/karp-rabin-algorithm.html]]
-例題
--[[1>http://conclave.cs.tsukuba.ac.jp/tpc/wiki/index.php?Solutions%2FLivearchive%2F6133]]
--[[2>http://d.hatena.ne.jp/jetbead/20120513/1336895972]]
--[[Codeforces Div.2 C>http://kmjp.hatenablog.jp/entry/2015/02/15/0900]]
--[[Codeforces Div.1 E>http://d.hatena.ne.jp/DEGwer/20160604]]
***MP [#g53e105b]
-[[MP>http://snuke.hatenablog.com/entry/2014/12/01/235807]]
--O(n)で、文字列 S が与えられたときに、各 i について「文字列S[0,i-1]の接頭辞と接尾辞が最大何文字一致しているか。ただし|S[0,i-1]|未満の一致とする。」を記録した配列を計算。
***Manacher [#i530f1c8]
-[[Manacher>http://snuke.hatenablog.com/entry/2014/12/02/235837]]
--各 i について「文字 i を中心とする最長の回文の半径」を記録した配列 R を O(|S|) で構築するアルゴリズム
***ローリングハッシュ [#oeb0f991]
-ローリングハッシュ
--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)で計算できる。
***Zアルゴリズム [#d56dd5ed]
-Zアルゴリズム
--「0から長さn-jと、jから長さn-jのLCP」が構築O(n)クエリ(1)で計算できる。
-[[解説付き>http://d.hatena.ne.jp/deve68/20120201/1328109890]]
-[[ちょっと雑>http://d.hatena.ne.jp/komiyam/20120118/1326812613]]
***Suffix Array [#ic007404]
-Suffix Array
--iとjから始まる文字列からのLCSクエリ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)
**三角数乗 [#zb185eb7]
-2^(n*n)は、三角数乗を順に求めるとO(n), 二分累乗だとO(n log n)？
**ビームサーチ [#l740ecc1]
-n個残す貪欲法
**座標圧縮 [#t52a4fa3]
http://algoogle.hadrori.jp/algorithm/compress.html
**Range Tree [#ub4e5bea]
-特に、指定された区間や点にオーバーラップする全ての区間を探すという問題を効率的に解くことができる。
-例えば、表示されている地図内に見えている全ての道路を求めるとか、3次元のシーンで見えている全てのオブジェクトを求めるといった用途に使われる。
**加群の行列演算 [#c7caab58]
-零元と単位元が何かをものすごく気をつける必要あり。意識しないと死ぬ。
--零元「足し算すると変わらない、かつ掛け算すると0になる」
--単位元「掛け算すると変わらない」
-普通の行列演算でいう0を零元、1を単位に書き換えないといけない。
**二分木 [#l7e89450]
-やりたいことは「ソートしながらデータを持つ」データ構造
--std::mapみたいな感じ
-追加も削除もある場合の頻出テク
--クエリの(平方)分割
--がんばって動的になんとかする
***愚直な方法 [#jeb3b7e8]
-頂点の左は必ず小、頂点の右は必ず大
-クエリ
++insert(x): 頂点がxより小さければ左遷移、大きければ右遷移、を繰り返してNULLポインタにあたったらそこにnew
++erase(x): まずxを探す(頂点p)。次にxを超えない最大の頂点を左右右…右の要領で探す(頂点q)。pを消して、qをpの場所に張り替える
***平衡二分木 [#vbf19a8c]
-基本だと、1,2,3,4,5,...,nの入力でなんかヤバくなる
-どんなものが平衡二分木？
--赤黒木(std::map)、スプレー木(Link-cut Treeに使う。ならしO(log n)だが最悪時間O(n)なので注意)、Treap、AVL木、くらい覚えとけばよさそう
-平衡
--左右の深さが偏らないように回転 (rotation)
--回転＝''順序を保存したまま''木構造を変形。
---順序を保存＝同じ順序関係を表す二分木であるという意味。[[参考(111ページ)>http://www.ioi-jp.org/camp/2013/2013-sp-tasks/2013-sp-day4-spaceships-review.pdf]]
---Left Rotationが左を下げること、Right Rotationが右を下げること。
-クエリ
++insert, erase
++split, merge: [0, k)と[k, n)の2つの列に分割、マージ
++値に関する質問・更新: sum, addなど
-各論
--Treap: キーと一緒に「優先度」を持つ。キーを見ると二分探索木、優先度を見ると二分ヒープ（常に親が子より大きい）になるように木を構成
--Splay: 2つ親までを見れば、回転によって平衡化が可能なことを利用した平衡木。頂点xを根の場所まで移動させてできる木を返す
***重軽分解 [#o65c3095]
-例題
--http://math314.hateblo.jp/entry/2014/06/24/220107
--http://sigma425.hatenablog.com/entry/2015/06/15/043041
--http://lattemalta.hatenablog.jp/entry/2016/02/18/220938
--http://solorab.net/blog/2016/05/18/arc-048-d/
--http://solorab.net/blog/2015/11/13/yuki-235/
***Link Cut Tree [#s3519b6f]
-Link-cut Treeのなりたち（下に行くほど実装が重い）
++頂点vから根へのパスをつなげる（expose, 必須で平衡二分探索木のsplit, mergeを使う）
++頂点の親を変更(link)、削除(cut)
++木の根を求める(root), 木の根を変更(evert)
++パスに対する頂点・枝の値のクエリ（sum, max, 更新）
-コンセプト
--ツリーを分解してパスにします。
--パスをsplay木で管理します（パスの順序さえあってればいいので、根は自由に選べる。よく実線をsplay木内部の辺、点線をsplay木間の辺として表記する）
***Euler-Tour Tree [#te83cdc8]
-Euler-tour treeとLink-cut treeは同様に神がかり的木
***永続 [#a102d4f4]
-永続(persistent)＝バージョン管理して、undoできる！
**ゲーム [#x7278192]
-参考
--[[Grundy-Sprague数の数理>http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1956-10.pdf]]
--[[Grundy数とNIMの対応>http://d.hatena.ne.jp/nanikaka/20120524/1337797626]]
***ゲームの分類 [#m4c4746b]
-二人
--四人（麻雀）
--二人（将棋・囲碁・オセロ）
--一人（ソリティア）
-有限
--有限回で終わるゲーム
--ゲーム木（＝局面全体を頂点集合とし、局面Pから局面Qに移動できるとき、PからQに矢を作って得られるグラフ）において、どの頂点から始まる有向パスの総数も有限
**スパーステーブル [#h5c3962e]
-http://yukicoder.me/wiki/range_minimum_query
**Gray Code [#pbb0f21e]
-面白い特徴のバイナリ表示らしい。
**ビット並列アルゴリズム [#b7c1db31]
-intが32bitなのに対して欲しいものが8bitとかの時にまとめて計算する並列化手法。文字列でよく使われてる
--http://d.hatena.ne.jp/tsubosaka/20091102/1257174409
--http://www.emit.jp/prog/prog_b.html
--http://www.ieice.org/iss/de/DEWS/DEWS2007/pdf/c1-9.pdf
--http://www.osakafu-u.ac.jp/data/open/cnt/3/9433/1/k1574.pdf
**埋め込み [#a6b2f1a4]
-漸化式の途中計算を0, 10000, 100000などと埋め込むことで、高速化する方法。
--http://d.hatena.ne.jp/wata_orz/20111218/1324226179
-式そのものを埋め込むことも
--http://d.hatena.ne.jp/wata_orz/20091223/1261582436
**コンパニオン行列の累乗 [#ha083fee]
-きたまさ法
--http://yosupo.hatenablog.com/entry/2015/03/27/025132
--http://d.hatena.ne.jp/wata_orz/20091223/1261582436
--http://www.slideshare.net/kmjp/yukicoder-no194
--https://dl.dropboxusercontent.com/u/109915284/companion20140318.pdf
--http://kmjp.hatenablog.jp/entry/2015/06/03/0930 ←ライブラリもある
**Sparse Table [#i7facda0]
-クエリO(log log n)でRMQ
**ADS [#ha6ba129]
-超上級
-http://iwiwi.hatenablog.com/
**乱択 [#r0cd8b69]
-http://www.slideshare.net/iwiwi/ss-13293754
**NTT [#oa27d6ac]
-Number-theoretical Transform
-http://xn--w6q13e505b.jp/method/fft/modular.html
**Blackbox Algebra [#z83f02a0]
-antaさんの記事を見る
**boyer moore search [#g2e32c26]
-早い文字列検索
-m文字を探す時、BM法の計算量は、最悪O(n)、平均的な場合O(n/m)
**bit並列 [#i1b31998]
-bitの状態をまとめて持つことによるDPの高速化。64bitだと64倍高速化になることも！
--[[とても親切で読みやすい>http://d.hatena.ne.jp/xiaohuli3/20111209#1323451593]]
**幾何 [#nafe853c]
***計算のロバストネス [#vab2db48]
-誤差が非常に効いてくるケースが少ないので、なるべく計算誤差が少ないような演算方法が重要
***点の進行方向 [#hd7549da]
-ccwはロバストな進行方向の計算方法
-angle は三角関数の計算という不動小数の計算を必要とするが，ccw は係数環の演算だけで構成されているので，極めてロバスト
***凸包構築 [#be3cc680]
-凸包は基本的にはO(n log n)
-基本的にはAndrew's Monotone Chainを使うのがいい
--上凸と下凸包を計算して、あとでマージする。
**Connectivity [#le77daac]
***Incremental Connectivity [#f900b025]
-Union Find Tree
***Decremental Connectivity [#e871cac9]
-えー
-問題によっては逆から見ればUFに落ちるらしい
***Dynamic Connectivity [#ca9e974e]
-切れるUF
-追加クエリO(log n), 削除クエリO(log^2 n), 連結性判定O(log n / log log n)
-antaさんのライブラリがめっちゃ速い。
-雑多情報
--[[pekempeyさん解説>http://pekempey.hatenablog.com/entry/2016/06/25/124538]]
--[[解説スライド（英語）>https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss12/AdvancedGraphAlgorithms/Slides08.pdf]]
--[[Dynamic Connectivity論文>http://www.cs.princeton.edu/courses/archive/spr10/cos423/handouts/NearOpt.pdf]]
--[[Dynamic Connectivity解説>http://codeforces.com/blog/entry/15296]]
---なぜ非連結要素を数えた…UFしてくれ…
--[[Dynamic Connectivity Contest>http://codeforces.com/gym/100551]]
--[[verify用問題>http://www.spoj.com/problems/DYNACON2/]]
**細々した定数倍高速化 [#rc47f333]
-[[vectorをreserveすると、環境依存だが1.1〜2倍高速化>https://ideone.com/hqxrRC]]
-[[ループアンローリング]]
-emplace_backを使うとmoveが呼ばれるので少し早い
-以下の2つはほぼ同じだが、メモリ確保回数が減る
vector<vector<int>> vvi;
vvi.push_back(vector<int>(10));
vvi.emplace_back(10);
**ヒープ [#if3dc73d]
-二分ヒープがpriority_queue
-フィボナッチヒープが最速
**Convex Hull Trick [#g52e67c3]
-[[Convex Hull Trick>http://pekempey.hatenablog.com/entry/2016/03/04/202648]]
-[[僕が書いた解説>https://docs.google.com/document/d/1u_f0RA8G4No-n5zGJRABdPjmKrj_adUJN-qK3cP6fH0/edit]]
**Mo's Algorithm [#ub81e980]
-http://pekempey.hatenablog.com/entry/2016/01/23/185143
*浮動小数点 [#i676a960]
-(ll)pow(3, 3) = 26なので、roundを使うこと
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
