- 追加された行はこの色です。
- 削除された行はこの色です。
[[プログラミングコンテスト]]
*プロコンサイト [#m0ecf4a6]
&ref(./level.png,50%);
**Topcoder [#meace356]
-div2 Hard は難易度的には div1 medium より簡単なイメージ
-[[CodeProcessor>https://github.com/hamko/topcoder/blob/master/codeprocessor.txt]]
-Challenge [#e9ce53e8]
--vectorのチャレンジの仕方
hoge,foo,test
--とすると、vector[3]={hoge, foo, test};となる。
--変なスペースはつけてはならない。
--最後にカンマをつけてはならない。
**Codeforces [#od15d7fb]
**Atcoder [#j0c642d0]
*問題の見方 [#h414205c]
**流れ [#hf705694]
+google翻訳に問題文を突っ込む
+実験
++明らかな条件を列挙し、覚えておく。自明な条件をコーナーケースとして把握する。
+求められる情報量の確認
--yes-noか、max-minか、numかなど。少ない情報ならまとめられる。
+計算機特有の発想
++特性関数の作りやすさ。この答え（以上・以下）は問いの答えたりえるか？という質問に簡単に答えられるかを確認する。
++半分全列挙
+計算量
--アルゴリズムに要求される計算量のキツさを確認する。
+頑張って実装
+テスト
--時間最大セットと、メモリ最大セットと、コーナーケースで通るかを確認する。
--疎な最大ケース 1 100000000
--密な最大ケース 10000000000 1000000000
--疎密ケース 1 1 1 1 1 100000 100000 100000 1000000 100000 1 1 1 1 1
**チェックリスト [#yed7affe]
|チェック項目|説明|h
|デバッグメッセージを残すな||
|自前テストしたか|極端な例（入力の小さいもの大きいもの）、最小の普通なもの、普通なもの、疎密（密粗密なども）|
|1行に複数の値を返す時、きちんと最後のスペースを除け||
|コーナーケースできちんとcout << 1 << endl; return 0;せよ|Atcoder, Codeforcesなどだと、間違えてreturn ret;とかすると死ぬ|
|何もかもlong longにせよ|掛け算でキャストミスしないために|
|はじめに書いたコーナーケースを最後にも確認せよ||
|整数同士の掛け算がオーバーフローしないか確認せよ|c[i]*c[i+1]でオーバーフローしえるので注意|
|整数同士の割り算がlgaussかugaussか確認|intがlgaussになるのは同符号の時だけ|
|valgrindをかけよ||
|盤面問題で、添字はあっているか確認せよ|添字のn, mを逆にしたりしてないか？|
**コーディング中の注意 [#k8c22f3d]
|注意|説明|h
|long longでの演算|10^18とかの場合、一回も掛け算してはならない！|
|負の%とif文の相性は最悪|両方正にして比較すること|
|Mod構造体のリテラルは必ずキャストすること|^がxorと判断されたりなど超絶面倒なバグが起きる|
*入出力 [#addee05a]
-cinは遅い。
--30万変数読み込みで、scanfだと50ms, cinだと150ms
-同期を切ると早くなる
--切ったらもうcinとscanfを混ぜて使ってはいけない
*計算量 [#je245c4b]
-1秒とは？＝3千万くらいは行ける。1億は無理。
|計算量|安全|無理|
|O(n)|3000万|1億=10^8|
|O(n log n)|100万|400万|
|O(n^2)|5000|10000|
|O(n^3)|300|450|
|O(n^4)|75|100|
|O(2^n)|25|27|
|O(3^n)|15|17|
-制約2秒程度だったら、逆にどんな計算量が求められている？
|制約|アルゴリズム|
|10^6|O(n)以下、軽いO(n log n)|
|10^5|O(n log n)以下|
|3000|O(n^2)|
|500|軽いO(n^3)|
|100|O(n^3)|
|30|O(2^n)の半分全列挙|
|20|O(2^n)、O(n 2^n)|
-違い
--ならし計算量 : 時系列上での平均
--平均計算量 : 確率変数上での平均
*よく使うデータ構造と関数と注意点早見表 [#g209e9c0]
|名前|メソッド|注意|h
|unordered_map|erase, count, find|tupleを突っ込めない。ソートされない。でも速い。|
|map|erase, count, find|tupleを突っ込める。50000要素でunordered_mapの3倍遅い。比較[[1>http://arc022.contest.atcoder.jp/submissions/711340]], [[2>http://arc022.contest.atcoder.jp/submissions/711335]], m.findはnot foundでm.end(), その他でイテレータを返す|
|set|count, erase, insert||
|queue|empty, size, front, pop, push||
|priority_queue|empty, size, top, pop, push|デフォルトで降順|
|stack|empty, size, top, pop, push||
|deque|push_back, push_front|前に挿入できるvector。前に挿入できるので添字が移動する|
|vector|push_back|vector<bool>は使用禁止|
|tuple|make_tuple, get|ほぼ何でもあり。unordered_mapに突っ込めない。|
*命名規則 [#s1c358fe]
-添字の逆引きはinvをつける。
--例えばvector<int> a;に対しては、unordered_map<int, int> ainv;
-int dx={0,0,1,-1}; dy={1,-1,0,0};は、使う添字の名前を借りてdi, djに。
*イディオム [#k42b7b41]
-int a = -1;を異常値とすると、~a==1で正常値となる
-2で割れるだけ割る: n/(n&-n)
-一番下に立ってるbitだけを残して0にする: (n&-n)
-最後に続いている0の数。NLZ(x) = count_bits( (x & (-x) )-1)
-最初に続いている0の数。NTZ(x) = 32 - NLZ( (~x) & (x-1) )
-for all, there exists, goto文を使うとすごく簡潔でよい。
rep(s, 1 << n) {
rep(i, n) for (int j = i+1; j < n; j++)
if ((s & (1 << i)) && (s & (1 << j)) && !memo[P(i, j)])
goto no;
ret = max(ret, (ll)__builtin_popcount(s));
no:;
}
-浮動小数点の比較は、<=ならゆるいから+EPS, <ならせまいから-EPSなどが明確にわかるようになる
--a <= b + EPS
--a < b - EPS
-左辺値も三項演算子使える
( i < x ? a : b )++;
vector<int> v1, v2; ( i < x ? v1 : v2 ).push_back( i );
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
