[[アルゴリズム]]
*まとめること [#g7e12367]
-https://yukicoder.me/wiki/slide これ読む
-https://www.slideshare.net/iwiwi/2-12188757 平衡二分木（区間の最小値と、区間の反転は流石に平衡二分木が必要）
-いい感じのデータ構造のまとめhttp://d.hatena.ne.jp/hirokazu1020/20140427/1398591122
-両方向PriorityQueue https://topcoder.g.hatena.ne.jp/spaghetti_source/20121006/1349491389
-ライブラリverifyのまとめ。これめっちゃいい。ウェーブレット行列とか永続配列とかもあって素晴らしい。
--http://d.hatena.ne.jp/hirokazu1020/20140801/1406924897
-Eが言い問題っぽい
--http://pekempey.hatenablog.com/entry/2016/12/31/162212#E-New-Year-and-Old-Subsequence
-[[ベルマンフォードで最長距離>http://hamayanhamayan.hatenablog.jp/entry/2017/05/14/134606]]
--最長距離ってNP困難じゃなかった？？
-Moの上位互換 [[Rollback平方分割>http://snuke.hatenablog.com/entry/2016/07/01/000000]]
-[[メモリアラインメント>http://www5d.biglobe.ne.jp/~noocyte/Programming/Alignment.html]]
-これ面白いっぽい
--https://topcoder.g.hatena.ne.jp/iwiwi/20120428/1335635594
-最近はヤバ目のデータ構造がホイホイ出ます。青コーダーなのにこんなんやる時代です、とかいって激ヤバデータ構造を淡々と紹介したい
Leetcode
・b&(1ll<<i)みたいなのは01ではないので!!しないとつらい
木の中心と半径の全探索は任意に頂点を二つ取る
全探索の変数を減らすためには、「他の変数が決まった時、この変数は一意に定まらないか？」と考える。
期待値とかは全状態に確率を定義してしまう
・これくらいの実装問題になってくると、もはや早解きのために雑に変数を定義するより、コメントをきちんと書いたりテスト駆動的にやったりするほうがパフォーマンスがでるCodeforces 402 D2E
実装問題
テスト駆動的にする。つまり部分関数を20行程度に分割して、単体でテストできるような設計にしておく。
コメントを積極的に入れる。
変数名にこだわる
nとかmではなく、v.size()などを利用する。
・sumとprodの操作方法について
Sumの空間を二分する
依存しないものを交換・前へ持ってくる
Sumはそもそも、i \in Sみたいな、集合であることを明確に意識すべき。高校の書き方がむしろおかしい。
CF250D1A
辺に着目する。必ず辺は全部なくなる。
CF250D1B
グラフの問題は構築していくことを考える
逆から構築
簡潔データ構造、実装も簡潔ならなぁ
平衡二分木、普通のセグ木の操作に加えて、列を途中で切断したり、2つの列をくっつけたりするなど動的な操作ができるようなやつです
Chokudaiコンテスト1, 2は両方単調劣モジュラ関数の最適化
http://bit.ly/2ws0IeB
http://tasusu.hatenablog.com/entry/2015/12/01/000608
http://www.orsj.or.jp/archive2/or58-05/or58_5_267.pdf
劣モジュラ最適化と機械学習1章 https://www.slideshare.net/ssuser77b8c6/1-71256266
近似評価関数と厳密得点の相関を見るとかすると面白そう。
最長経路問題は重みなしでもNP完全
だが、DAGならO(V+E)（トポソして前からDP）
CFの乱択D
解空間が多いような話は、乱択すると行けることがある（特に最適化じゃないものに関しては）
マラソンっぽいｗじゃなく、きちんとやる。
http://hamko.hatenadiary.jp/entry/2017/04/23/190630
手戻り最小化基準で実装、部分問題を別関数に分ける、を意識して次からやろう
CF Div.2 Cの精密実装が難しすぎる…多い添字の操作って精進というより、記憶力とか地頭な気がするから死にたい。成長しなそう。。
例えば行列ABの掛け算で、i行j列の情報を決定するのにAのi行のk列目とBのj列のk行目を全部足し合わせる、とか頭の中ではとっても簡単にできることがわかるんですが、いざプログラムを書こうとすると、kのゼロ点とかがどこだかわからなくなったりして辛くないですかというやつ
流石に行列は大丈夫になった（大学2年生の頃はつらかった）。
他には文字列AとBの最長一致する部分文字列とか、Aのi番目からj文字取った部分文字列がBのk文字目から一致するかチェックするために、Bのk文字目から始まる添字l<j文字目と、Aのi文字目から始まるl文字目が全一致とかね。
セマンティクスでいうと、配列aの添字をaiとかにして混乱を防いでるけど、物理世界での^{i}P_{i+1}みたいなものをi+1の意味でniとかつけるのでたまに混乱する
謎のWAへの対応
assertを入れてランダム入力
''forの範囲に注目''。ループ回しそこね(n+1で回すべきところをnしか回していない)。
コーナーケース。
R木というものがあるらしい
kd-treeの構築と、以下の探索機能を実装してます。結構いろいろできる。例えば
最近傍探索 (Nearest neighbor search)
k-最近傍探索 (K-nearest neighbor search)
半径内に含まれる近傍の探索 (Radius search)
CF415 D2C
式を大きく精密に書きましょう
なんか典型問題力が圧倒的に足りていない気がする
あと、「ちゃんとした思考回路をたどる」というのが大事な気がする…
http://codeforces.com/contest/810/problem/C
http://arc071.contest.atcoder.jp/tasks/arc071_b に似ているらしい
A問題難しそうな解き方してる人がいる気がするんですが、F(a) = max(a) - min(a) だからそうすればいいのでは（n_vipさん）
最大クリークはO(n 2^n)とO(n 2^{2m})の２つがある。
http://researchmap.jp/uno/%E8%B3%87%E6%96%99%E5%85%AC%E9%96%8B/
http://research.nii.ac.jp/~uno/codes-j.htm
あるグラフの最大クリークを求めることと、その補グラフの最大独立集合を求めることは同値である。
二部グラフにおいては最小点カバーと最大マッチングが一致すること、および、一般のグラフにおいて最小点カバーと最大独立集合の和が節点数と一致することから、対象の補グラフが二部グラフである場合には最大クリークを簡単に求めることができる。
2分グラフ上の最大独立集合問題 -> 「頂点数 - 最大マッチング」が答え
これによると、最大独立集合問題はO(1.2^n)くらいで解けるらしい。
http://www.orsj.or.jp/~archive/pdf/bul/Vol.50_11_763.pdf これ、すごくよくできた最大独立集合のサーベイ
高速ゼータ変換のライブラリ、以下の問題に対応して２つとも入れておくこと。
kenさんの整理された問題集
http://d.hatena.ne.jp/drken1215/20131222/1387706789
無理やりダイナミックライブラリをくっつけることができるらしい
yukicoderで無理やりgmpをくっつける方法
http://yukicoder.me/submissions/98383
https://yukicoder.me/problems/no/456/test
GCJ 2016 Qual C
・n進数の合成数の十分条件に文字列循環というものがある
・素数判定は大変だが、雑な合成数判定は非常に簡単（2-100の素数で割ってみればよい、結構ヒットするはずなので良い）。特に例示の場合。
SRM 695 D1M
・permで雑にcombinationを作る
5 c 2なら、00011のような配列maskをnext_permutationして、配列が立っているところが集合に入っているとみなす。
・定数倍高速化
Long long -> int 全く効かない
perm -> comb 0000111をpermするcombinationは、nCrを探すのにn回走査する必要があるので、n/r倍遅いはず。(-10%)
set->bitset+vectorで高速に行う（40%）
Reserve 全く効かないが、効くケースもありそう
配列を外において使い回す
Powなど重い超関数をforで回す
Powなど重い超関数を変数変換で減らす
クエリをバッチ化する（うさぎさんのMillions of Submits!）
二分探索をニュートン法にする
http://yukicoder.me/submissions/136896
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
