![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
*概要 [#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]] -[[チャレンジ記録>https://docs.google.com/spreadsheets/d/1D5qSJOgARVwHmPSAyQScb5Mri_nmSA_DdLodHuKv2xQ/edit#gid=0]] *下位ページ [#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] -重要度順 **重要 [#oba90b1d] -Cartesian Tree -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]]（木で最強） -インタバル木 --二次元平面の範囲点クエリ？ -Dancing Links -[[マージ可能ヒープ>https://topcoder.g.hatena.ne.jp/spaghetti_source/20120929/1348886107]] --skew, 乱択、フィボナッチ、Pairingソートなど -分割統治法，逐次構成法， -平面走査法 -Gray Code -永続 --配列 --平衡二分木 --set --UF --セグメントツリー -動的 --セグメントツリー --遅延セグメントツリー --永続遅延セグメントツリー -しゃくとり法 -ベルマンフォードって何のために使うの？(LatteさんのSelf-constructing witchが1つの解答になるかも) -AhoCorasick --http://codeforces.com/contest/710/submission/20191222 **そこそこ [#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 -区間ふるい -MCS --マックスクリークサーチ --http://yukicoder.me/submissions/111984 -[[DM分解>http://www.misojiro.t.u-tokyo.ac.jp/~murota/lect-ouyousurigaku/dm050410.pdf]] **どうでもいい [#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 *ライブラリ [#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||| |
