- 追加された行はこの色です。
- 削除された行はこの色です。
*概要 [#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
*失う信用 [#s3831077]
-人が作った問題を解くという枠組みから出られていない
--いつも自分が作った問題を解いているわけではないでしょう？サーベイの高速化になる。
--じゃあどういう枠組みかというと、「世界中から10秒以内で解ける全ての問題を集める」世界なので
--別に人が作った問題を解くのも面白いじゃん…
-意味のないことをしている
--競技プログラマのコード速度を見たことがありますか？めちゃ早いよ。
--無意味だからやらない、と人事の人が言っていると、優秀層エンジニアが逃げる。
--強いエンジニアは往々にして「技術が面白いから技術をする」ので、そういう優秀層エンジニアが逃げる。
-お金が儲からない
--コード速度が上がることはお金が儲からないと思っているの？
--お金が儲からないからやらない、となると優秀層エンジニアが逃げる。
-社会貢献できていない
--プログラミングの能力を高めるのが社会貢献に繋がらないなら、仕事ばっかりやって成長しないゴミエンジニアを応援してそう
-承認欲求に取り憑かれている
--それは真逆で、やると自信がどんどんなくなってくるので、承認欲求は満たされない。
--実績を求めるという話もある。競技や資格以外に求められる人はやらなくてもいい
--レートを見ればどれくらいのコーディング能力があるか一目瞭然なので、就活にも役に立つみたいになっていく。
*目次 [#n328e6e1]
#contents
* [#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のビジネスはデザインとかがメイン。マラソンは割と外注あるが客寄せが大きな目的。
-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が解けないみたいなやつを足切りするなど
-実は緑くらいあれば、ウェブ開発とかは普通にできる。
*外部の人への説明 [#l5a84ce6]
-「単体テストは用意されているけど、単体テスト専用対策による不正がされないように、不正解ケースを教えてくれないシステム」
*参考 [#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|||
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
