![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
まとめること †
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 |
