[[プログラミングコンテスト]] *プロコンサイト [#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かなど。少ない情報ならまとめられる。 +計算機特有の発想 ++特性関数の作りやすさ。この答え(以上・以下)は問いの答えたりえるか?という質問に簡単に答えられるかを確認する。 ++半分全列挙 +計算量 --アルゴリズムに要求される計算量のキツさを確認する。 +頑張って実装 +テスト --時間最大セットと、メモリ最大セットと、コーナーケースで通るかを確認する。 **チェックリスト [#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:; } |