- 追加された行はこの色です。
- 削除された行はこの色です。
[[TODO]]
*概要 [#p5677d79]
-プロコンで考えるべきこと
-解いた問題数を増やすのは良い事なんだけど、解いた問題数を増やすためだけに、簡単な問題を解きまくるのってすげえ時間の無駄
-プロコンで必要となる知識のまとめ。
-難問を解いて自分のものにする、短時間で学習するサイクルが回せ。
-役に立つとは別の軸でプログラミングの面白さを主張することで裾野を広げる活動
-競技プログラミングのメリット
--脳内シミュレーション能力の向上
--コードで語り合う、技術力を認め合い、語り合う。
--ある問題を一緒に解く時の一体感が楽しい。
*下位ページ [#qc53e894]
-[[アルゴリズム]]
#ls
*目次 [#n328e6e1]
#contents
*記録 [#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/1te9YVPWrE8QLM6KR12gD-0g-VzeM8RHdMfvVxrSrj5s/edit#gid=7]]
-[[プロコン記録>https://docs.google.com/spreadsheets/d/1zYQDdJYxtZRr9s7U_dCtZEHfehu5_Qq7wtGemNM3tT4/edit#gid=0]]
-[[チャレンジ記録>https://docs.google.com/spreadsheets/d/1D5qSJOgARVwHmPSAyQScb5Mri_nmSA_DdLodHuKv2xQ/edit#gid=0]]
*下位ページ [#qc53e894]
#ls
*目次 [#n328e6e1]
#contents
*失う信用 [#s3831077]
-人が作った問題を解くという枠組みから出られていない
--いつも自分が作った問題を解いているわけではないでしょう？サーベイの高速化になる。
--じゃあどういう枠組みかというと、「世界中から10秒以内で解ける全ての問題を集める」世界なので
--別に人が作った問題を解くのも面白いじゃん…
-意味のないことをしている
--競技プログラマのコード速度を見たことがありますか？めちゃ早いよ。
--無意味だからやらない、と人事の人が言っていると、優秀層エンジニアが逃げる。
--強いエンジニアは往々にして「技術が面白いから技術をする」ので、そういう優秀層エンジニアが逃げる。
-お金が儲からない
--コード速度が上がることはお金が儲からないと思っているの？
--お金が儲からないからやらない、となると優秀層エンジニアが逃げる。
-社会貢献できていない
--プログラミングの能力を高めるのが社会貢献に繋がらないなら、仕事ばっかりやって成長しないゴミエンジニアを応援してそう
-承認欲求に取り憑かれている
--それは真逆で、やると自信がどんどんなくなってくるので、承認欲求は満たされない。
--実績を求めるという話もある。競技や資格以外に求められる人はやらなくてもいい
--レートを見ればどれくらいのコーディング能力があるか一目瞭然なので、就活にも役に立つみたいになっていく。
* [#z020d369]
-REPマクロは妥当な作法
--生for文は言語の欠陥
--boost::irangeやiota_viewなどが使えない状況ならREPマクロで対処するのは必要。
--慣れてない人に「汚い」とか言われたりするかもだけど、そういう場合はLinuxのソースコードとかを見せれば解決すると思う
--Linuxのソースコードには #define for_each_...(...) のような定義が100個以上存在している
--マクロによる構文の拡張はC言語における妥当な作法だと主張することができます
--by うさぎさん
*アルゴリズムの勉強必要性 [#m362b357]
-特にこのページはアルゴリズムのまとめ。
-アルゴリズムが判ってない、計算量が判ってないから、「○○は遅いからダメ」みたいなのをあらゆる状況で言っちゃう人は割と多い。必要なところだけ早くすればいい。
-以下の問題を何とかしたいから勉強しているのだけど、キリがないという気分
++正しいと信じてるプログラムが間違ってるケースを減らしたい
++脳内でこうやればできる、というところと実装の溝を減らしたい。実装を単純作業にしたい
++トップレベルの人でも普通知らない、非自明かつ一般的なアルゴリズムを使えるようになりない
++典型なのに知らずに解けないケースを減らしたい
-上位者の提出の早いコードを読んで学ぶ必要性
-コンテスト中だけでもいいから、「ちゃんと最後まで問題に向き合う」というのは大切
-「サンプルが通った時の提出前の回答の信頼度」みたいなのもまるで計れないと、テストの数をどれくらいにすべきかの直感がなくなる
-実装に時間がかかった問題は、ちゃんと上位陣のコード読んでリファクタリングしないと、実装力の伸びは鈍化する。ちゃんとシンプルな実装を学ぶのとても大切。
*レートの直感 [#a87a1ba3]
-AtCoderは赤→銀→金は4倍ずつレアになる。そこから先は倍々。茶色以下は歪められている（本当は負のレートになるはず）
-将棋との対応
--[[[僕は大体13%>http://sucrose.hatenablog.com/entry/2016/10/03/234723]]
--[[将棋ウォーズを見ると13%は二段相当>http://hayashikun-shogi.blog.jp/archives/1171079.html]]
--[[将棋ウォーズ二段はアマチュア二段～三段相当と公式が認定している>https://www.shogi.or.jp/license/howto.html]] （将棋ウォーズは少し段位認定が厳しいらしい）
*マネタイズ [#pebf1761]
-Atcoder 定期コンテスト1回で100万-200万（AGCだと1コンテストで15万円くらいを業務委託で払っている？）, マラソンも1問30万くらい？オンライン一発だと150~200万、予選＋決勝方式だと300~400万くらい
--Codefestivalは異常なので一回問題だけで1000万以上
-Topcoder
--[[Topcoderでお金を得る>https://www.topcoder.com/community/member-programs/algorithm-problem-writers/]]
--topcoderのビジネスはデザインとかがメイン。マラソンは割と外注あるが客寄せが大きな目的。
*参考 [#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
-1000万の案件も
*言語 [#g0319e36]
-AtCoderの言語アップデートでPythonにsortedcontainersってのが入ってたんですか！？（YouTubeのコメントで知りました）競プロでのPythonのデメリットの3割くらいが消えました。
*練習方法 [#i6ed9c7a]
-解いた問題数を増やすのは良い事なんだけど、解いた問題数を増やすためだけに、簡単な問題を解きまくるのってすげえ時間の無駄
-Codeforces
--黄色の人とかがCFのBCD埋めるのは典型力と非典型力と実装力が程よくついていいと思うけどE埋めは本当に虚無なのでやめた方がいいと思う
--Eには典型重実装がたくさんあって不毛
-AOJ-ICPC
--多くの人にはオススメできない気がしてきました。
--自分はすごい実力ついたと思っていたけれど、赤になってから実装力不足が目立ち始めたから始めただけ
--赤になるまでは質の高い問題をひたすら解くべき
-アプローチの
--アプローチの手法とは例えば「N=1のときはどうか」と簡単版の問題を考えてみるとか「この条件がないとNP-hardになるからここが本質か」とかそういう風に問題のどこが難しいのかを探る手法
--考察力とは、僕は問題に対するアプローチの手法の引き出しをどれだけ持ってて使えるかって感じだと思っています。
--問題解決能力と呼ばれてるのと近いと思います。
--エレガントな問題解決って本とか[[アルゴリズムパズルっぽい本>https://www.amazon.co.jp/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%83%91%E3%82%BA%E3%83%AB-%E2%80%95%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9E%E3%81%AE%E3%81%9F%E3%82%81%E3%81%AE%E6%95%B0%E5%AD%A6%E3%83%91%E3%82%BA%E3%83%AB%E5%85%A5%E9%96%80-Anany-Levitin/dp/4873116694
]]とかはそういう部分扱ってるように見えます
*コンテストの目的 [#fededab5]
-コンテストの役目は、優秀な人材を育てることではなくて、優秀な人材と、そうでない人材とを容易に見分けることが可能な場を提供すること
--A+Bが解けないみたいなやつを足切りするなど
-実は緑くらいあれば、ウェブ開発とかは普通にできる。
*勉強すべきこと [#x5163fe2]
-重要度順
**重要 [#oba90b1d]
-monge
--DP高速化の数学的理論
--https://topcoder.g.hatena.ne.jp/spaghetti_source/20120923/1348327542
--https://topcoder.g.hatena.ne.jp/spaghetti_source/20120915/1347668163
--四角不等式みたいなものを満たすと、O(n^3)->O(n^2)とかに落ちて嬉しい
-ウェーブレット木
--動的ウェーブレット木
--永続ウェーブレット木
--動的永続ウェーブレット木
--ウェーブレット行列
-Blackbox Algebra
-[[Link-Cut Tree>http://www.slideshare.net/iwiwi/2-12188845]]（木で最強）
-SA-IS (Suffix Array) O(n)
-インタバル木
--二次元平面の範囲点クエリ？
-Dancing Links
-[[マージ可能ヒープ>https://topcoder.g.hatena.ne.jp/spaghetti_source/20120929/1348886107]]
--skew, 乱択、フィボナッチ、Pairingソートなど
-分割統治法，逐次構成法，
-平面走査法
-Gray Code
-永続
--配列
--平衡二分木
--set
--UF
--セグメントツリー
-動的
--セグメントツリー
--遅延セグメントツリー
--永続遅延セグメントツリー
-しゃくとり法
-ベルマンフォードって何のために使うの？(LatteさんのSelf-constructing witchが1つの解答になるかも)
*外部の人への説明 [#l5a84ce6]
-「単体テストは用意されているけど、単体テスト専用対策による不正がされないように、不正解ケースを教えてくれないシステム」
**そこそこ [#j33d1bea]
-カタラン数
-山登り法
--マルチスタートローカルサーチ（ローカルサーチのスタート地点を複数点設けます）
--焼き鈍し法
--遺伝的アルゴリズム
--タブーサーチ
-[[モンゴメリ乗算>http://yukicoder.me/wiki/%E3%83%A2%E3%83%B3%E3%82%B4%E3%83%A1%E3%83%AA%E4%B9%97%E7%AE%97]]
--antaさん記事
-[[高速アダマール変換>https://twitter.com/uwitenpen/status/767795344310620161]]
--CSAcademyのどれかのF 16/08/23
-区間ふるい
**どうでもいい [#xbed802b]
-ADS
-2-SAT
-[[Treap, RBST(k-th tree), 平衡二分木>https://docs.google.com/document/d/1QuPsq6an9MKjTOGxKnNi2TwAqgS7o5Aissnipzl6OOI/edit]]
-デク・優先度付キュー
-ボロノイ図とデローネイ三角形分割
-美術館問題
-最短路問題
-埋め込み
-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)で処理できないという結論に至った。（今の僕には）
-Shunting-yard algorithm
*参考 [#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
*ライブラリ [#ff8ddfbd]
-[[はむこのライブラリ>https://github.com/hamko/procon/tree/master/library]]
-TODO
--エラトステネスのかわりに区間篩を使って実装。
--区間篩じゃないとかなり大きい範囲の素数全列挙はできないという噂
-まだ追記が必要なものまとめ
|アルゴリズム|概要|計算量|h
|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|||
*ライブラリ [#ff8ddfbd]
-[[はむこのライブラリ>https://github.com/hamko/procon/tree/master/library]]
*アルゴリズム各論 [#gc237b0d]
**全探索 [#w93906b1]
***n^k [#bf592990]
-rep(i, ni) rep(j, nj) rep(h, nh) rep(k, nk) cout << i + j + h + k << endl;
***深さ・幅優先探索 [#s90a9a4b]
|名前|データ構造|デメリット|メリット|h
|DFS|stack|最適性は保証されない|省メモリで全探索可能|
|BFS|queue|メモリをいっぱい使う|HITしたものが最短経路経路であることが保証される|
-深さをメモするqueueの実装は、unordered_mapやmapが必要
--[[AOJ Reverse Sort>http://purple-jwl.hatenablog.com/entry/20140419/1397922062]]
--そもそも深さ付きDFSはvectorをqueueとして使ったほうが楽
--queueでやりたいなら、queueに突っ込むnodeのunordered_mapを用意して、node tmp = q.top(); ll cost = depth[tmp]; q.pop();とかやるしかない。
***木 [#rbb4e9d3]
-DFSしてください
***グローバルにデータを持つDFS, BFS [#w3066d64]
-木の持つデータが大きい場合、「逆操作が軽い」DFSならば、メモリ使用量をO(1)に出来る。
--Codeforces 368 D2D
-もし操作が「戻れる」なら、再帰関数を呼ぶ前と後に状態変化を書くことで、グローバルにデータを持てばよい
***n! [#i81576c4]
-next_permutation
***nCr [#ia4f999c]
-next_combination
-めんどい場合はnext_permutationを使っても良い
***総和を固定する全探索 [#f1fd51fc]
-数列aに対して、総和Sが含まれる評価式を満たすaを1つ挙げたい
--しかし、数列aは非常に探索空間が大きいので無理
-なぜ難しいか？
--''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が構成可能
**状態 [#bee84f80]
-アルゴリズムでは「状態」が重要である。
--全探索は状態を全て走査する
--DPは状態と遷移の組み合わせを考察する
--ゲーム理論ならgrundy数には状態が必須
-状態の抽象度
--一見n!であっても、上手く見ると状態を減らせる、というのが非常に重要
+順序 n!
--一番一般的なもの。
+被覆+最後 n 2^n
--被覆とは、集合のどれかを選ぶという意味。
--巡回セールスマン問題
---被覆とその最後に使うノードを指定する
+被覆 2^n
--集合のどれかを選ぶ
+区間 n^k
--1次元の区間は[l, r)で表される。
--2次元の区間は[(a, b), (c, d))で表される
+個数 n
--個数だけ見ればよい、という問題
+mod n
--法をとっても同じ、という意味
+偶奇 2
--mod nの2バージョン。よく使う。
**基本 [#j26520be]
***二分探索 [#w120e7b6]
-デバッグ
--特性関数だけまず確認したほうがいい
while (1) {
ll t; cin >> t;
cout << check(t) << endl;
}
-二分探索内全探索
--全探索内での二分探索としたほうが枝刈りができて速い
--http://d.hatena.ne.jp/wata_orz/20100910/1284108575
--状態s, 探索空間nとして、O(s log n)からO(s + log n log s)に落ちる
-実装
--二分探索の変数名をpassとfailとすると超わかりやすい
--l, rは厳しい
***しゃくとり法 [#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/]]
**問題の見方 [#p4e122be]
-アルゴリズムの重要なことは、脳内の整理
-図や表を多用しまくることが重要
***基本的なこと [#cc839a12]
-凸凹してたら
--全探索
--DP
--半分全列挙
--分枝限定法
--枝刈り全探索
-マッチング
--フロー
--二部グラフ（結局これもやってることはフロー）
-割り当て（全体の拘束のもと、満足度を最大化）
--最小費用流
-「5歩で」「10回で」
--半分全列挙
--AOJ Reverse sort, yukicoder 五輪ピック
-「辞書順最小で」
--辞書順は取れるときにとれば最適になる
--待っていても良い物がこないし、一回一回で最適なものを選べばいいだけだから
-「n<200のグラフ」
--Nが小さいグラフはとりあえずワーシャルフロイドで全点から全点にすぐ行けると思うと良い
-「全て異なる」
--割り当て問題。「n人の人がm個の仕事をする。人iが仕事jをするときの達成度vのリストが与えられる。全体で最大の達成度はなにか。同じ仕事は複数人で受けられない。」
--厳密に小さいと全て異なることになる。全部異なるものを仕事側とすると、割り当て問題の「同じ仕事は複数人で受けられない」に相当することになる。
--AOJ Dangerous Tower
***問題の図示 [#ha502211]
-http://agc002.contest.atcoder.jp/tasks/agc002_e
--↓の図を左と↓下から食っていく
##
###
#######
########
-http://abc038.contest.atcoder.jp/tasks/abc038_d
--LISを二次元平面上にプロット
***変数の動きの整理 [#h11f07ae]
-例えば以下のようなプログラムで
int a; cin >> a;
b = a * a;
c = a * b + (a > 0);
-以下の様な表を書く
a b c
--------
-1 1 -1
0 0 0
1 1 2
**用語 [#s9de2f16]
-multiset
--同じ要素が複数入っていても良いデータ構造。eraseでは全部ではなく1個だけ消す(Codeforces 367 D2D)
**データ構造の数学的構造 [#l4d6eb6a]
***俯瞰 [#o5d9483d]
-データ構造Gと演算○のセットを、(G, ○)という。
-これがどのような代数的構造を持っているかで、適用可能なアルゴリズムを限定できる。
-アルゴリズム構築に重要な代数的構造は以下である
|名前|特徴|具体例|h
|モノイド|並列処理可能性|(整数, min), (整数, max)|
|群|0-indexだけ計算すればi-indexに出来る|(整数, +)|
|ベクトル空間|行列演算可能性|(実数, +, *)|
***代数的構造のまとめ [#v6959c60]
-読み飛ばしてOK
-[[わかりやすい>http://ufcpp.net/study/math/group/field/]]
-環からは、2つの演算子に関する代数的構造。
-下に行くほど、制約が強い
-演算子について
|名前|定義|具体例|h
|マグマ|(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上のベクトル空間とする」などと表現する
|名前|定義|具体例|h
|環上の加群|左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)は左イデアルであるため、これを日本語では「零化イデアル」と呼ぶこともある。
***モノイド [#q02636e6]
-「データ型T, 二項結合演算op、単位元T0」が定義できる
-[[単位元を持つ二項結合演算とは？>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|
***群 [#k2b7a7a2]
**データ構造の機能の名称 [#g9af5208]
-動的
--木・配列・グラフなどの構造そのものが変わること。
--動的凸包、動的kd-Tree、動的Ford Fulcarsonの場合、「削除ができること」という意味。
-オンライン
--構築後にデータの更新ができること。
-永続
--データ構造の途中結果に、更新が終わったあとにアクセスできること。
--入門には[[永続Union-find>http://pekempey.hatenablog.com/entry/2016/08/01/165036]]が一番わかりやすい。
--だいたいのデータ構造は永続にできる。永続配列、永続平衡二分木(RBSTがよく使われる)、永続union-find、永続set、永続セグメントツリー、永続ウェーブレット木…
-範囲更新
--[s, e)までに演算を行う、木の頂点sを根とする部分木全てに演算を行う、木の頂点sから木の頂点eの最短パスの全てに演算を行う、など。
**永続 [#m291af39]
-[[永続の基本的なところ>http://d.hatena.ne.jp/kyuridenamida/20141223/1419346780]]
***DFSでできる永続 [#o07591e3]
-逆操作が簡単な永続データ構造は、ただ「グローバルにデータを持つ」DFSを掛けばよいだけ。
--Codeforces 368 D2D
**mod [#ee04def5]
***分数のmod [#kdbf4433]
-AOJ Fast Division
***Z/pZ体の逆元 [#m9d95b8f]
-*a^(p-2)が逆元となる。
-重要なのは、pが素数でない場合には、必ず逆元が存在しないこと！
--逆元が存在しない場合は、ダブリングのようなもので代用することを考える。
***nCr [#e7ca8ebe]
-n!と1/n!をO(n log mo)で前計算することで、nCrはO(1)で計算可能
***拡張ユークリッドの互除法 [#q6424420]
-拡張ユークリッドの互除法を、非再帰のユークリッド互除法→Blankinship's algorithm→線形方程式の求解として見る→単因子標準形、と拡張する。
--https://topcoder.g.hatena.ne.jp/spaghetti_source/20130126/1359171466
**素数 [#gf10bd32]
-素数系のライブラリは、隣接性を利用したものと、しないものを明確に分けなければならない。
--隣接性利用: O(n log log n)
--隣接性非利用: O(n sqrt(n))
***構築付き素数判定 [#g0996101]
-エラトステネスのふるい
--長い配列を用意して、必要のないところにはそもそも試し割りしないようにしながら素数を列挙する
--O(n log log n)
-同じようなアイディアで、試し割りするともに素因数の数を数えることで、隣接100万くらいの素因数なら全列挙できる。
----具体的には、SRM 565 D1Mのように隣接100万個の素因数の数え上げはO(n log log n)と高速である一方、構築後の素因数を一つ一つ見るのでO(n sqrt(n))となりn=100万では無理。
***非構築素数判定 [#x19c8b97]
-Millar-Rabin Test
--O(20)くらいで構築なし、64bitの素数判定ができる！
***区間篩 [#z62dd889]
-大きな範囲の素数全列挙にはこれが必要との噂
**範囲クエリ [#e487317a]
***まとめ [#o7ffb4ef]
|名称|数学的構造|構築後のデータ変更|構築|参照クエリ|更新クエリ|更新タイプ|h
|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 [#l54345ef]
-Fenwickは、「点更新」「範囲参照（''0-indexにしかならない！''）」
--もしデータと演算が群ならi-indexになる
-Fenwick Tree=BIT=Binary Indexed Tree
--実装が簡単で高速。
***Segment Tree [#ib2b69ef]
-Segment Treeは、「範囲更新」「範囲参照」（範囲更新はlazyによって実現）
-セグメント木
--モノイドでいいので応用力が高く、自分で考える部分が大きい。
-コツ
--非遅延セグメントツリーは、結合二項演算と単位元だけあればできる。
-練習問題
--Do Use Segment Tree
---（セグメントツリー＋重軽分解）
---http://d.hatena.ne.jp/simezi_tan/20140624/1403554584
--[[難しいセグメントツリー>http://hogloid.hatenablog.com/entry/20121227/1356608982]]
--[[セグメントツリー中級に良さそう>http://d.hatena.ne.jp/DEGwer/20131211/1386757368]]
--[[問題集>http://kagamiz.hatenablog.com/entry/2012/12/18/220849]]
--[[問題集>http://algoogle.hadrori.jp/algorithm/segment-tree.html]]
***Lazy Segment Tree [#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]は使わない
-lazy segtreeに必要な条件、集合A上の+っていう演算結果が欲しくて、更新クエリが写像A -> Aの部分集合Fの元になっているとき、(A,+)がモノイドで、Fが合成で閉じていればokな気がした。あとはFの元f,gについて合成f*gとf(x_i)の区間和が高速に計算できれば
***永続Segment Tree [#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://sigma425.hatenablog.com/entry/2014/12/30/164148]]
--[[永続構造スライド>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]]
-実装
--[[pekempeyさんの実装>http://pekempey.hatenablog.com/entry/2016/04/21/235157]]
--[[pekempeyさんの実装2>http://pekempey.hatenablog.com/entry/2016/05/16/235152]]
***動的Segment Tree [#jec91c24]
-[[動的セグメントツリー>http://d.hatena.ne.jp/DEGwer/touch/20131211/1386757368]]
***範囲クエリ上での二分探索 [#cee036ad]
-つまり、範囲で見ると単調性が現れるものが、範囲クエリでの二分探索に相当する。
-数列のminとmaxは範囲に対して単調になる。
-''全要素が正ならば、積分すると単調になる
--segment tree上の二分探索が可能''
--Segment tree上の二分探索、要するに積分すると単調=全要素が正ってことなんだよね。
***imos法 [#jbb00e6f]
-コツ
--n要素配列の累積和なら、n+1個用意して0番目を単位元にする。
-二次元でも累積和できる。
-imos法
--範囲和が実現可能
--[[多次元・多字数・特殊座標への拡張が容易>http://imoz.jp/algorithms/imos_method.html]]
***二次元Fenwick [#ba74d0a3]
http://codingmelon.com/2015/12/17/range-sum-query-2d-mutable-leetcode-308/
***二次元セグ木 [#ha893e3a]
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
遅延二次元セグ木は？
**ソート [#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]]
**グラフ [#e6cfd076]
***グラフに関する基本的名称 [#cbeb31ed]
-頂点
-辺
-入次数・出次数
-DAG
--ループが無いグラフのこと
-平面グラフ
--双対なものが作れるらしい。かなりすごい性質。
-Functional Graph
--頂点が入次数、出次数がともに1
--Topcoder Sunny Graph, Codeforces Educational 16くらいのやつ（Functional Graphはサイクル分解しなくてもダブリング出来るよ、という問題）
-二部グラフ
--二色彩色可能なグラフ
***有名問題とそのクラス [#xd8c4703]
-概観
--いろいろ長い問題名が出てくる。同じ名前で違う呼ばれ方がするので、以下に統一
--問題＝最小独立パス被覆問題、最小頂点被覆問題、最大独立集合問題、最小パス被覆問題、最小辺被覆、最大マッチング
--性質＝DAG、推移性、二部グラフ
-最小''独立''パス被覆問題
--グラフの頂点を、''非連結な''何個のパスで全て覆い尽くすことが出来るか？
--''非連結な''の部分が「独立」に相当している。重要。これがないと、多項式時間にするのに推移性が更に必要になる。
--DAGだと多項式時間で解ける
-最小頂点被覆問題
--頂点被覆＝全ての辺が、選んだ点に接続するようにする頂点集合
--グラフの頂点に色を塗る。色を塗られていないところの隣に必ず色が塗られているようにしたい。色を塗る最小回数を求めよ（NP完全）
--|V|=最小点被覆+最大独立集合
--一般にはNP完全
-最大独立集合問題=最大安定集合問題
--独立集合=辺で隣り合っていないような頂点集合
--一般にはNP完全
-最小パス被覆問題
--グラフの頂点を、何個のパスで全て覆い尽くすことが出来るか？二回同じ頂点を使っても良い。
--推移性があるDAGだと、最小独立パス被覆問題に一致し、多項式時間で解ける。
-最小辺被覆
--全ての点が、選んだ辺に接続するようにする頂点集合
--[[詳しくは>http://pekempey.hatenablog.com/entry/2016/05/01/155644]]
-推移性
--「a->bとb->cに辺があるならば、a->cにも辺がある」を満たすDAGに関する性質
--推移性のあるDAGなら、最小独立集合問題と最小パス被覆問題と最小独立パス被覆問題は一致し、多項式時間で解ける [Dilworth 1950]
-二部グラフ
--二色彩色可能なグラフ
--二部グラフでは、最大マッチングが多項式時間で求まる
--二部グラフならば、最小頂点被覆＝最大マッチング
***複雑なグラフ構築のコツ [#hf7f02ca]
-グラフ構築ゲーはname server作ったほうがいい（name server = 文字列からノードの番号を得るmap）
--ルイージの酒場
***最短経路問題 [#m572b1d2]
-ベルマンフォードって何のために使うの？(LatteさんのSelf-constructing witchが1つの解答になるかも)
|名前|計算量|アルゴリズム|特徴|h
|ベルマンフォード法|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が高速
***閉路検出 [#ia83b6ad]
-有向閉路検出→SCC
-無向閉路検出→BFSで二度来たら閉路あり。
***グラフのDAG化 [#sd510ab5]
-強連結成分を縮約すると、任意のグラフはDAGになり、トポロジカルソートができるようになる
***トポロジカルソート [#oaec51dd]
-入次数が0のものから1つづつ取っていけばいい。
--トポロジカルソート自体がすごいというより、これを利用するしてアルゴリズムを組む。
--[[queueの代わりにpriority_queueを使うケースもあり>http://tenka1-2016-quala.contest.atcoder.jp/submissions/823048]]
***全域森 [#h9849f3b]
-重要なのは「ループがない」こと
-全域森のモチベーション
--なるべく少ないコストで全部繋ぎたい
--なるべく少ないコストでグラフのループを消したい
|プリム法|O(ElogV)|統合頂点群から未統合頂点への最小距離をメモする。未統合頂点のうち統合頂点群に最も近い頂点を探す。統合頂点群に追加する。頂点追加によって、最小距離が変わるので更新する。|最も近い頂点を貪欲的に追加する方法|
|クラスカル法|O(ElogV)|辺をコストの小さい順に並べる。コストの低い順に見て、閉路ができないならば連結していく。閉路ができることは連結先と連結元がUnion-Findで同一かによって検知可能|最もコストの小さい辺を貪欲的に選び続ける方法|
***Functional Graph [#x3aa0215]
-全ての頂点が唯一の有向辺を持つようなグラフ。
-木の頂点がサイクルでつながっている形をしている。
-実は、サイクルを分解しないでダブリングできる（Educational codeforces 15のE問題)
***最小パス被覆 [#gff412eb]
-DAG上だと多項式時間で解ける
--AOJ Merry Christmas
-「DAGを無理やり二部グラフにしたもの」を「2V個の頂点V, V’を用意して、元のグラフx->yに辺があるならばx->y’に辺を張る、としたときの二部グラフ」と定義する
-DAG上での最小パス被覆（全頂点を通るような）は、|V| -無理やり二部グラフにしたものの最大マッチングである
***最小費用流 [#sfb2727e]
-最小費用流は割り当て問題を解ける。
--「''全体で''限られた資源で、個々人が資源を使うことにより''個々人の不満度''が定義され、その不満の総和を最小化する」ということができる
--「''全体で''限られた資源で、個々人が資源を使うことにより''個々人の満足度''が得られ、その価値の総和を最小化する」ということができる
-[[最小費用流の非常に良いテキスト>http://dopal.cs.uec.ac.jp/okamotoy/lect/2013/opt/handout14.pdf]]
--輸送問題
--割り当て問題
--複数シンク
--特定の枝に少なくともこれだけのフローを流す、といった制約も解説
--特にオアシスの例は非常にわかりやすい
-[[輸送問題>https://www.msi.co.jp/nuopt/docs/v18/examples/html/02-08-00.html]]
-AOJ Dangerous Tower
***二部グラフ [#g11a7942]
-グラフから二部グラフ構築はたったのO(n)
--二色彩色可能ならば、塗った白黒を左右に振り分けて、必ず二部グラフを構築可能
--二食彩色不可能ならば、二部グラフは構築できない
--AOJ RabbitWalking
***最大流 [#m3d94d9f]
-マッチング問題が解ける(AOJ Luigi's Tarvan)
-Ford Fulcarsonを動的にする問題が大量にある
--残余グラフの理解が必要
-残余グラフ
--Ford Fulkersonでは、「流せる余力」を表したグラフを作る
--元のグラフと何が違うかというと、「さっき順方向に2だけ流したから、逆方向に2だけ流す余力がある」というのを許可する点。
--これを前提すると、大概の操作が貪欲に行うことが出来る！
--また、流れているフローを、順方向の辺に対応する逆辺の容量を見ればよい。
-動的Ford Fulcarson
--辺Add:
---残余グラフの余力が増える→フローが流せるか試すだけ。簡単
--辺Erase:
---フローが流れていないなら、消すだけ。flowは変わらない。
---フローが流れていれば、まずその辺のフローを他のルートに押し付ける！これは、辺を含む閉路が存在したら押し付けることが出来る。
---その結果フローが流れなくなったら、消すだけ。flowは変わらない
---もしフローが足りないなら、終点から始点への消すフローFの増加路を押し戻す。そうすると、上記閉路が必ず存在するようになるので、他のルートに押し付けて、自分は消える。
-参考、専門家による[[最大動的流>http://www.kurims.kyoto-u.ac.jp/~tanigawa/coss/coss2012/kamiyama.pdf]]
-計算量
--O(V^3)の最大流 Push-relabel
***最小カット [#s564479c]
-最大流に一致する！
***雑多 [#ed6c14ba]
-http://www.slideshare.net/tmaehara/ss-17402143
--本「離散凸解析の考え方」
--なんか関数定義をして、それが凸かどうかを判断して、云々している。とてもよい。
-頂点は難しい、枝は簡単
-葉を指定した最小全域木→Kruskalの変形
-分散最小全域木、比最小全域木などは、パラメータ化して何かを止めると凸にする
-k-th最小全域木
**静的木 [#y4c5ec51]
-木の構造そのものが切られたり追加したりしないものでの、様々な木の上でのクエリの処理方法
-[[木いろいろ>https://topcoder.g.hatena.ne.jp/iwiwi/20111205/1323099376]]
***基本的な性質 [#nb6e1b63]
-頂点n辺n-1かつ連結なら必ず木構造
-木構造はどこを根にしても木構造
***できること [#oe4ca3dd]
|名称|計算量|説明|h
|最短パスの頂点に乗ったデータの積分（群限定）|''O(log n)''|オイラーツアー+範囲参照データ構造|
|頂点から根へ向かうパスの二分探索|O(log n)|ダブリングで可能|
-木に対する積分
|木の構造|データ対象|データの変更|できること|できないこと|備考|
|静的|部分木|可能|群積分・部分木更新|特になし||
|静的|最短パス|可能|群積分|min, max|範囲更新もできる気がする（正に加算、負に減算するような操作はlazyできそう）|
|静的|最短パス|不可能|モノイド積分|データをあとから書き換える||
|動的|最短パス|可能|モノイド積分|特になし|2D Euler-Tour+領域木で行けそう|
-辺に関するクエリは、頂点に持たせることで同様に積分できそう
***オイラーツアー [#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 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)で計算できる。
***頂点から根までの列の二分探索 [#y5026aa7]
-先祖のダブリングによって実現
**再帰 [#ocefc68a]
***返り値をメモするタイプの再帰 [#u21ab921]
-異常条件→メモ条件→''遷移→メモ''→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;
}
***条件を満たし続ける再帰 [#a1527546]
-異常条件→メモ条件→''メモ→自分→遷移''→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;
}
**座標圧縮 [#t52a4fa3]
-疎でも実際には数が少ないならば、圧縮して良い
-http://algoogle.hadrori.jp/algorithm/compress.html
-AGC 2Dのグラフ圧縮のように、逆に利用することも出来る
**DP [#mb392f04]
-DPはとにかく、''ある状態にいる人の気持ちになって考える''=状態を固定した時に、次にどこに行くか、を考えることが非常に大事
-難しさ
--分かったつもりで実際に問題をといても、アクセプトされない。
--デバッグしにくいので、しかも何でアクセプトされないかわからない。
--解説を見ても、DPは図を書かないと絶対理解不能。漸化式を文章で書かれても困る。
-DPの類型化
--本当はやりたい。
--無理矢理でもとにかく大量の（200問以上の単位で）ものを分類したい
***参考 [#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]
-数列や盤面に対して、非常に典型的な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 [#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
***確率DP [#o2aceb23]
-確率のDPは条件付き期待値を計算すると良い（つまり今までのことを考えてはならない！！！）
--これは、DPの遷移で、その和が必ず1になるように注意できるから。assertとかも最悪掛けられる。
--656 D1E
***未確定のDP [#vc20069b]
-「n個未確定で」というタイプ
-AOJ 箱根駅伝
***Monge [#d1c516d3]
-DPのMonge性
--O(n^3)->O(n^2)（Knuth-Yao Speedup）
-Totally monotone性
--O(n^2)->O(n)
-ちゃんとまとめたい
***問題特有の構造による状態削減 [#d0636de8]
-yukicoder ドーナツ
--ストレス溜めすぎるのは良くない
-Rabbit Walking
***包除原理のDP [#bd4b5a1b]
-AOJ Hyperrectangle
**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;
**最小辺カバー [#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]]
**FFT [#kc84e8b2]
***FFT [#meae5360]
-[[結構自然な問題>http://atc001.contest.atcoder.jp/tasks/fft_c]]
-添字の順序の総和が一定となるような掛け算の総和は、O(n log n)で計算できる！
-用途
--多項式同士の掛け算
--線形漸化式の計算
--行列演算
***線形漸化式と畳み込み [#yf9344c4]
-線形漸化式は本質的に畳み込みになっている。
--添字の順序を逆にするとすぐわかる
***NNT=高速余剰環畳み込み [#z3c23d95]
-[[コード>http://math314.hateblo.jp/entry/2015/05/07/014908]]
--任意のmodで行けることも書いてある
-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の時はこうも呼ばれる。適切な演算子が使えるので定数倍が高速
**拡張ダイクストラ法 [#a60567a3]
-何を指して言っているのか？
-http://d.hatena.ne.jp/about_hiroppy/20121014/1350199668
-http://d.hatena.ne.jp/m-hiyama-memo/20100630/1277872470
-http://purple-jwl.hatenablog.com/entry/20120709/1341845396
**誤差 [#j839cc7f]
-[[誤差>http://misawa.github.io/others/avoid_errors/techniques_to_avoid_errors.html]]
***浮動小数点 [#i676a960]
-例えば、(ll)pow(3, 3) = 26
--このケースで言えば、roundを使うこと
-とにかく浮動小数点は誤差が出る。
***誤差の減らし方 [#x793926e]
-誤差が厳しい場合
--long doubleを使う
--ハフマン符号のように小さい数値から足していくだけでも誤差減る
***「long longのcastで大きくなる」誤差 [#ta1498de]
-前提として丸め誤差は大きくなる
--doubleの精度が15桁であるが、17桁を扱おうとするなどしたら起きる誤差
-本当の答えが0.999999999999とかである時、丸め誤差が発生すると1.00000000000001とかになる。
--long longのキャストせよという問題なら、本当は0であるべきところが1になる。
-yukicoder 413
**XOR [#u3ce3a65]
***GF(2)の加算としてのXOR [#taecf611]
XORは、余剰体Z/2Zの加算演算である。
--なお乗算はAND
***加算かつ減算 [#wb972263]
-a xor a = 0
***最大化 [#je68418a]
-かなり凸凹した演算なので、基本的にはDP
***最大化クエリ [#p83c86ac]
-Trieを使うことでXORをO(log n)で最大化することができる。
--Codeforces 367 D2D
***累積和するといいことがある [#u0c36487]
-XOR範囲和が0となるような範囲の数え上げ SRM 565
**ウェーブレット木 [#c13f5ddc]
-値域に注目した木構造
--ビッグデータの多くのクエリをO(1)で処理できるすごい木
-[[永続動的ウェーブレットマトリックス>http://minpcontest.appspot.com/e/THEGTHNUMBER.html]]
-[[ウェーブレット木の解説>http://www.slideshare.net/pfi/ss-15916040]]
-[[ウェーブレット木の問題>http://pekempey.hatenablog.com/entry/2016/05/16/235152]]
-antaさんコンテスト、G番目の数字が永続動的ウェーブレットマトリックス。すごい。
**Subset Convolution [#pca4d5b8]
***高速ゼータ変換 [#qef794e9]
-「集合への値xを、部分集合への値に変換する」
-[[高速ゼータ変換の語源>http://link.springer.com/chapter/10.1007%2F978-3-642-16533-7_7]]
-[[コード付きで非常に簡潔>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]]
-[[高速メビウス変換>http://d.hatena.ne.jp/simezi_tan/20130522/1369203086]]
***高速メビウス変換 [#rac193d0]
-「積集合の値を、和集合の値に変換する」
-[[高速メビウス変換の語源>http://web.stanford.edu/~rrwill/presentations/subset-conv.pdf]]
**文字列操作 [#m84550f2]
***文字列でやりたいこと [#ab61c763]
-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|h
|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)の使い方 [#fc6b6d1d]
-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 [#ob2cc3a7]
-早い文字列検索
***MP [#g53e105b]
-0からの回文をO(n^2)ではなくO(n)で全列挙できる！
-[[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)で計算できる。
-[[ローリングハッシュ、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]]
--[[H問題「二次元のローリングハッシュ」>http://www.slideshare.net/chokudai/thanks2014-a]]
-[[ローリングハッシュハック>http://yukicoder.me/problems/652]]
-[[ローリングハッシュのメリットは群的であること>http://odan3240.hatenablog.com/entry/2015/02/16/111938]]
-[[ローリングハッシュ、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]]
***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]]
-重要なのは、これを使うと「TとSのLCP（Tは唯一）は、Zアルゴリズムで構築O(n) 参照O(1)で可能。」ということ
--AOJ Almost Same Substring
***Suffix Array [#ic007404]
-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の構築方法>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の実体験
-[[IS-SAとスパーステーブルを作ってて面白そう>http://mayokoex.hatenablog.com/entry/2015/08/12/000830]]
***問題集 [#fe74311a]
-面白そうな例題
--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]]
--[[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]]
***Trie [#x92a9bfb]
-接頭辞の木
-http://d.hatena.ne.jp/ishikado/20131009/1381296254
-XORクエリの最大化でも使える
***k-mismatch-matching [#r8a075b6]
-k個未知の文字列"he?lo wor??"が、もう片方の文字列に含まれているか
--SA-ISでO(k n)で解けるはず。AOJ Almost Same Substring講評参照
**二分木 [#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木間の辺として表記する）
-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]]
***Euler-Tour Tree [#te83cdc8]
-Euler-tour treeとLink-cut treeは同様に神がかり的木
**ゲーム [#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]]
***解き方の大まかな分類 [#e07dedbf]
+深さ探索するもの
+状態列挙してGrundy数を使うもの
+ゲーム特有の性質を使うもの
***WL-Algorithm [#s8eb9405]
boolean isWinning(State pos){
State[] nextStates = { posから到達できる全ての次の状態 };
for(State s : nextStates){
if(!isWinning(s)) return true;
}
return false;
}
-このタイプの理解の方法
--「勝ち状態w」「負け状態l」を定義する
-二つの状態の定義があり、この曖昧さによって混乱が生じる！どちらの立場なのかをきちんと明確にすること。
--勝ち状態wを「この状態''から始めた人は''必ず勝つ」、負け状態lを「勝ち状態ではない」と定義する。（こっちのほうが一般的！）
---遷移は、「次に負け状態を相手に押し付けられる遷移が選べるならば勝ち」＝「遷移先にlがあればw, なければl」
--勝ち状態wを「この状態''で終わっ人は''必ず勝つ」、負け状態lを「勝ち状態ではない」と定義する。
---遷移は、「終わったあと、勝ち状態を相手が選べてしまうなら負け」＝「遷移先にwがあればl, なければw」
--基本的には、「始め」の勝ち状態のほうを、一般的に勝ち状態と言う。
-勝ち負けゲームの定番解法「勝ち状態にwを置いて、負け状態にいけないなら負け、負け状態にいけるなら勝ち」
--rngさんのAGC02 E問題の解説(youtubeに上がっている)を見るとわかりやすい
***ゲームの分類 [#m4c4746b]
-二人
--四人（麻雀）
--二人（将棋・囲碁・オセロ）
--一人（ソリティア）
-有限
--有限回で終わるゲーム
--ゲーム木（＝局面全体を頂点集合とし、局面Pから局面Qに移動できるとき、PからQに矢を作って得られるグラフ）において、どの頂点から始まる有向パスの総数も有限
***Grundy数 [#s2354410]
-[[pekempeyさんの良い解説>http://pekempey.hatenablog.com/entry/2016/01/16/190208]]
-定義
--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なら使える''
**幾何 [#nafe853c]
***計算のロバストネス [#vab2db48]
-誤差が非常に効いてくるケースが少ないので、なるべく計算誤差が少ないような演算方法が重要
***点の進行方向 [#hd7549da]
-ccwはロバストな進行方向の計算方法
-angle は三角関数の計算という不動小数の計算を必要とするが，ccw は係数環の演算だけで構成されているので，極めてロバスト
***凸包構築 [#be3cc680]
-凸包は基本的にはO(n log n)
-基本的にはAndrew's Monotone Chainを使うのがいい
--上凸と下凸包を計算して、あとでマージする。
**Connectivity [#j08172ad]
***Incremental Connectivity = Union-Find Tree[#f900b025]
-「同じ集合は同じ根を持つ木である。根は-要素数を持つことでsizeを持つ」である
-工夫も実は簡単で、(1) uniteの時に木の浅い方にくっつける。 (2) Findの時に、通ってきた経路を全部根からの多分木にするである。
--片方でO(log n)両方でO(A(n))
-[[盤面問題をUnionFindで>http://arc031.contest.atcoder.jp/submissions/297951]]
***永続Union-Find [#x2d0901d]
-[[永続union find>http://pekempey.hatenablog.com/entry/2016/05/23/041232]]
-2007年、ACM SIGPLAN の Workshop on ML において、Sylvain Conchon と Jean-Christophe Filliâtre
--計算機支援証明システムCoqを使って形式的に正しさが証明されている
-永続Union-Findは、永続配列・永続平衡二分木の両方で実装可能
--[[永続配列によるUnion-Find>http://agc002.contest.atcoder.jp/submissions/826150]]（←速いし簡単だしこっちおすすめ）
--[[永続平衡二分木によるUnion-Find>http://pekempey.hatenablog.com/entry/2016/05/23/041232]]
***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/]]
**乱択 [#r0cd8b69]
-YES-NOを聞く全探索
--n=1000でO(n^3)だから無理？
--しかし、YESがたったの1/n^3しか無いことはあるのだろうか？
--例えばAOJ Symmetryでは、n^3個の中にn個くらいYESとなるケースがある。つまり、AmortizedでO(n^2)！
-なんとなく幾何と乱択は相性がいいような気がする
-http://www.slideshare.net/iwiwi/ss-13293754
**ヒープ [#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]]
***概要 [#n8ba26b3]
-さばけるクエリ
--直線f_i(x)=a_i*x+bをリストに追加する O(log n)
--max f_i(x) を計算する O(log n)
***Increasing Convex Hull Trick [#lac86e69]
-直線の削除ができない！
-a_iが単調増加、xが単調減少の場合
--直線追加がO(1)になるらしい
***Dynamic Convex Hull Trick [#i23b330f]
-更に、直線の削除が可能
--計算量はO(loglog n)
**Mo's Algorithm [#ub81e980]
-http://pekempey.hatenablog.com/entry/2016/01/23/185143
**貪欲 [#o4d7eb30]
***証明方法 [#w31dcfcf]
***ビームサーチ [#l740ecc1]
-n個残す貪欲法
-[[ちょくだいさんの基本的な解説>https://twitter.com/chokudai/status/713976934506496000?ref_src=twsrc%5Etfw]]
--chokudaiコンテストとかも見るといい
***証明の練習問題 [#e4dcc413]
-Topcoder SRM 697 D1E
--&ref(./IMG_0596.JPG,20%);
--全てのf_iが真となるようなa_iは存在するか
--1<=b_i<=10
--これに対して、http://hamayanhamayan.hatenablog.jp/entry/2016/08/19/112400 みたいな、謎貪欲解がある(chokudaiさん、kmjpさん解法)。これが正しく動くことを示せ。
-ARC 53C
--上がって下がってする奴
--あの貪欲の構成は面白かった気がする
-AGC 03B
**行列 [#h2343e9e]
***行列の種類 [#l00e3042]
-[[参考>http://d.hatena.ne.jp/anta1/20130114/1358108415]]
-コンパニオン行列
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
***行列のクラスと計算量 [#p085c330]
|名称|行列と行列の積|普通のk乗行列累乗|k乗行列累乗(BLA)||h
|一般|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): 行列とベクトルの掛け算
---単純なアルゴリズムではT(n)=O(n^2)
--M(n): 多項式乗算の時間計算量
---単純なアルゴリズムではM(n)=O(n^2)だが、R=Z/mZの場合は余剰環上のFFTを用いることでM(n)=O(n (log n) log(log n))にできる。
-Blackbox linear algebraによる行列式
--O(n^2+n T(n))
***行列累乗 [#q6fe35c8]
-普通の行列累乗について、
--行列累乗は行列を先に計算するとめっちゃ遅くなるので、行列xベクトルを計算しましょう。
--構築ありの行列累乗だとメモ化できるので早い
--参考 AOJ Three-way branch
***行列式 [#r9cb625e]
-普通には全体でO(n^3)
-行列木定理と呼ばれる定理は、 グラフが与えられたとき、全域木の個数を行列式を用いて求められる
--非自明数え上げが多項式時間でできるすごい。
***Blackbox linear algebra [#n71642f1]
-行列累乗
--普通O(n^3 log k)で、テプリッツ行列・巡回行列・コンパニオン行列などでO(n^2 log k)だった。
--めちゃくちゃ大雑把にいうと、これのlog kを分離してO(n^3 + log k)やO(n^2 + log k)にする手法
-[[antaさんの記事>http://yukicoder.me/wiki/black_box_linear_algebra]]
-ライブラリ
--http://codeforces.com/contest/668/submission/17496606
--http://yukicoder.me/submissions/64177/source
-以下の時、「線形漸化的」であるという。（antaさんの造語？[[N階線形漸化式を満たすという表現>http://www.math.sci.hiroshima-u.ac.jp/~m-mat/TEACH/sentan2005.pdf]]）
--''これはまさに、無限列が実は初期値＋線形多項式で生成できる、という意味！''
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で計算できる。[[資料>http://www.math.sci.hiroshima-u.ac.jp/~m-mat/TEACH/sentan2005.pdf]]
--証明不明
-体上のベクトル{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)
-これらから、行列累乗の高速化が実現された。
-
***コンパニオン行列の累乗 [#ha083fee]
-[[最も数学的に良い説明>http://misawa.github.io/others/fast_kitamasa_method.html]]
--ちゃんと理解するにはこれ読んで。
-''二つの実装方法があり、後者のほうがメモリ効率が良いためかなり速い''
--行列の形に注目するもの
--線形漸化式の線形性と、本質的に多項式の乗算除算であることを使う（[[つまりはこういうこと>http://kmjp.hatenablog.jp/entry/2015/04/27/0930]]）
-[[その他説明>http://kmjp.hatenablog.jp/entry/2015/06/03/1000]]
-[[コンパニオン行列の累乗>https://dl.dropboxusercontent.com/u/109915284/companion20140318.pdf]]（''これが前者の方法で、これを実装すると遅いので注意''）
--古くは Krishnamurty [2] に発見され，その後 [1, 3, 4] によって再発見されている．
--ヘッセンベルク行列のべき乗への拡張は Datta and Datta [5]によって提案されている
--O(n^2 log k)
-きたまさ法
--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
--http://kmjp.hatenablog.jp/entry/2015/06/03/0930 ←ライブラリもある
-高速きたまさ法
--O(n log n log k)
--余剰環では畳み込み演算にFFTを使うことで、更に高速化できる
--http://kmjp.hatenablog.jp/entry/2015/06/03/1000
--http://nitcoder000.hatenablog.com/entry/2015/06/04/003508
--http://math314.hateblo.jp/entry/2015/05/07/014908
***加群の行列演算 [#c7caab58]
-環R上の左加群なら、(+, *)じゃなくても行列演算が可能
-零元と単位元が何かをものすごく気をつける必要あり。意識しないと死ぬ。
--零元「足し算すると変わらない、かつ掛け算すると0になる」
--単位元「掛け算すると変わらない」
-普通の行列演算でいう0を零元、1を単位に書き換えないといけない。
**非自明数え上げ [#q843d965]
***無向グラフの頂点iから頂点jにちょうどk歩で行く場合の数 [#h7f24928]
-[[参考>http://spinda2.blog48.fc2.com/blog-entry-494.html]]
-「無向グラフの頂点iから頂点jにちょうどk歩で行く場合の数」＝「隣接行列Aとする。A^kのi, j成分」である。
-閉路を考えるなら、i==jとすればよい
-注意点
--交差しているものも数え上げる！
--i=A, j=B, k=4としたとき、A->B->A->B->A->Bとかも数える。
***無向グラフのk歩で戻ってくる閉路の個数 [#y0a14a1e]
-[[参考>http://spinda2.blog48.fc2.com/blog-entry-494.html]]
-[[ライブラリ>https://github.com/hamko/procon/tree/master/library/short-cycles]]
-無向グラフのk歩で戻ってくる閉路の個数
--開始頂点は指定できないので注意！
--k=3からk=12くらいまでは公式がある。
--公式は非常に複雑なので、[[ここ>http://spinda2.blog48.fc2.com/blog-entry-494.html]]を見るか、ライブラリをそのまま使う。
-例（k=3だとtr(A^3)/6）
--[[例1>https://www.wolframalpha.com/input/?i=%5B%5B0,1,0,1%5D,%5B1,0,1,0%5D,%5B0,1,0,1%5D,%5B1,0,1,0%5D%5D%5E3]]
--[[例2>https://www.wolframalpha.com/input/?i=%5B%5B0,1,1,1%5D,%5B1,0,1,0%5D,%5B1,1,0,1%5D,%5B1,0,1,0%5D%5D%5E3]]
***無向グラフの全域木の数え上げ [#sf1250c6]
-「無向グラフの全域木の数」＝「ラプラシアン行列のn-1次部分行列の行列式」
--ラプラシアン行列とは、n行n列行列で、その (i,j) 成分が
---i=jのとき、頂点iの次数（＝頂点iから出ている辺の数）
---i≠jのとき、隣接行列の(i,j) 成分の−1倍
-行列木定理 (Matrix-Tree Theorem)と呼ばれているもの。
***二部マッチングの数え上げの偶奇 [#h4f0ed59]
-隣接行列の行列式で計算できる。
-二部マッチングの数え上げそのものはNP完全
--これは具体的には、n!パターンの隣接行列の和
元の隣接行列
011
110
011
数え上げるべき組み合わせ
001
100
010
010
100
001
--これはsgnをつけると行列式になる！
***転倒数の数え上げ [#lfc4a591]
-問題そのものは「クロッシング問題」と呼ばれる。
-要するにバブルソートの交換回数。転倒数は反転数とも呼ばれる。
--愚直にはO(n^2), 普通にはO(n log n), 世界最速はO(n sqrt(log n))
-解法
--BIT使ったり
--表使ったり
***オイラー閉路の数え上げ [#y7f1ffee]
-BEST theorem
-オイラー路はグラフの全辺を使うパス
-オイラー閉路は、閉路であるオイラー路。
**多項式 [#j4d01541]
***畳み込み [#v3364d2c]
-FFTとかNTTを使うとO(n log n)で計算できる
--NTTは任意のmodで行ける
***公式 [#u566dd01]
-総和の分解
--&ref(./IMG_0570.JPG,20%);
--ARC 59C
-くくりだしの漸化式
--&ref(./IMG_0569.JPG,20%);
--ARC 59C
***ラグランジュ補完 [#gd3613fc]
-N次式で(N+1)個の値がわかっているので、ラグランジュ補間で完全に式を求めることができる。
***母関数 [#pde5bb61]
-第k項が無限列{a_i}となる関数。
-漸化式と母関数 [#ya65cdad]
--[[講義資料>http://dopal.cs.uec.ac.jp/okamotoy/lect/2014/dme/handout04.pdf]]
--[[漸化式→母関数>http://www.h6.dion.ne.jp/~ooya/Suugaku/bokansuu.pdf]]
---母関数に関する漸化式を立てる
--母関数→一般項は非常に簡単
---ただマクローリン展開すればいいだけ
--母関数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次の係数を求めよ」
**場合の数 [#f3dec70f]
***カタラン数 [#q5f2eba4]
-https://ja.wikipedia.org/wiki/%E3%82%AB%E3%82%BF%E3%83%A9%E3%83%B3%E6%95%B0
-http://www.geocities.jp/yoimondai/e16.html
-どんなものがカタラン数？
--対角線をまたがない格子状の経路数え上げ＝0を超えないみたいなのありそう
--N個の分岐を持つ二分木
--()を正しく並べる方法（！）
--平面グラフの交差 2n人が円になって手を交差させないで握手をする場合の数はカタラン数 Cn である。
-カタラン数よりも、その計算方法の方が大事
--AOJ 10歳の動的計画法を参照
--禁止領域基準に鏡写しにしたものを引くやつ
**点群処理 [#j31ab0b5]
***2つのsetを同時更新 [#k3408d4b]
-範囲のどれかが0であれば、2つのsetを同時更新するだけでkd-tree相当の処理がO(log n)、しかもnot amotizedで処理可能
--set<int, int> fs, sf; // first-second, second-first
-[[CF 366 D2C>https://docs.google.com/document/d/1ZgaZr65B21bnYrWFArfo7MGyx4JeBrMeglGm1cCbmrg/edit]]
***kd-tree [#zc7a4d13]
-平衡Dynamic kd-tree
--spaghetti codeにあるやつ
--二次元閉区間の点を追加、点を削除がO(log n + k), k=ヒット数、amortizedで処理可能。
--点に情報を乗せることもできるはず
--スケープゴート的に平衡処理する
-[[CF 366 D2C>http://codeforces.com/contest/705/submission/19712089]]
***応用：2D Euler Tour [#eecdbdb8]
-iwiwi先生の木のクエリ完全制覇
--1D Euler Tourだと群的データしか載せられなかったのが、これだとモノイドも載せられるっぽい
**盤面 [#yaa22051]
***上書き [#n06a6674]
-盤面、上書きは後ろから塗りはがして?にしていく
--Topcoder 655 D1E
***DP [#y3cc7338]
-愚直かつ典型に、O(n^4)の区間DPが可能。
**マトロイド [#k7077c30]
-よくわかってないし必要かもよくわからない。
-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!
-https://topcoder.g.hatena.ne.jp/spaghetti_source/20121103/1351911603
--ここからスパゲッティソース。ここ数週間の解説はすごくガチ
-「典型DP」を覚えておくのと同じノリで「典型マトロイド」を覚えておくのが重要だと思います．
--具体的に抑えておくべきこととしては，
--有名なマトロイド：自由マトロイド・線型マトロイド・グラフ的マトロイド・マッチングマトロイド，ガンモイドなど
--既知のマトロイドから新しいマトロイドを作る操作： 制限，縮約，マイナー，ユニオン，誘導
-逆に「任意の重みで貪欲法が最適解を出す」ならば，マトロイドである
-[[そして離散凸、M凸・劣モジュラへ>https://www.math.kyoto-u.ac.jp/~kfujiwara/shioura.2010.dehn.pdf]]
**Gray Code [#pbb0f21e]
-面白い特徴のバイナリ表示らしい。
**細々した定数倍高速化 [#rc47f333]
***vectorのreserve [#i7285f9c]
-[[vectorをreserveすると、環境依存だが1.1〜2倍高速化>https://ideone.com/hqxrRC]]
***ループアンローリング [#p7c5ed9c]
-[[ループアンローリング]]で20%くらいの高速化できることがある。
-キャッシュが乗るらしい。よくわからない。
***emplace_back [#s7ec5d2f]
-moveが呼ばれるので少し早い
-たとえば以下の2つはほぼ同じだが、メモリ確保回数が減る
vector<vector<int>> vvi;
vvi.push_back(vector<int>(10));
vvi.emplace_back(10);
***bit並列 [#i1b31998]
-これは「細々として」ないかも
-bitの状態をまとめて持つことによるDPの高速化。64bitだと64倍高速化になることも！
--[[とても親切で読みやすい>http://d.hatena.ne.jp/xiaohuli3/20111209#1323451593]]
-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
***SSE [#w6c08225]
-[[SSE]]
-SSE具体的には、mask使うとifを簡単に表現できたりするけど、コンパイラもそこまではやってくれないとか
**Dancing Links [#j3a89071]
-幼稚園児高橋君のやつ
**埋め込み [#a6b2f1a4]
-漸化式の途中計算を0, 10000, 100000などと埋め込むことで、高速化する方法。
--http://d.hatena.ne.jp/wata_orz/20111218/1324226179
-式そのものを埋め込むことも
--http://d.hatena.ne.jp/wata_orz/20091223/1261582436
**Range Tree [#ub4e5bea]
-特に、指定された区間や点にオーバーラップする全ての区間を探すという問題を効率的に解くことができる。
-例えば、表示されている地図内に見えている全ての道路を求めるとか、3次元のシーンで見えている全てのオブジェクトを求めるといった用途に使われる。
**「データ構造をマージする一般的なテク」 [#h18e045d]
-挿入が定義されたデータ構造が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)
**整数計画法 [#fd1f63cd]
-大概のアルゴリズムは整数計画に落ちる
-綺麗な形なのでなんとなく楽しいが、実際に解くのはNP困難の上、IPソルバは非常に長いので現実的には使えない（と思っている）
-整数計画に落としたあとに、多項式時間で解くためのコツをまとめる
***変数定義 [#w5ec97f1]
-ベクトルxが未知変数
-ベクトルaが係数
***証明でよくある手法 [#j280d7f8]
-S=Σxと置く。
-Sから1つかけているなら、S-x_iときちんと変形
-T>Sなる超大きな定数を前提する（あとでそのようなTが存在することを示す必要あり）
=存在性証明の顔をして一例あげてしまう
***存在性証明の顔をして一例あげてしまう [#k48b5af2]
-存在性証明は、順逆の証明をするのだが、まるで二回順方向に証明しているように示す
++まず必要条件を示す
++つぎに解を具体的に提示（むつかしい。元の拘束条件から求める）
++その解を拘束条件に代入して、必要条件と同値を示す
-&ref(./IMG_0595.JPG,20%);
*ヤバくて手が付けられてないもの [#r5cb052f]
**ADS [#ha6ba129]
-超上級
-http://iwiwi.hatenablog.com/
**フロンティア [#w72b5342]
-フロンティア法の長い解説
--[[C++プログラムも>http://www-lsm.naist.jp/~jkawahara/frontier/]]
--[[資料>http://www-lsm.naist.jp/~jkawahara/frontier/frontier_lec.pdf]]
-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)
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
