プログラミングコンテスト
プロコンサイト †
Topcoder †
- div2 Hard は難易度的には div1 medium より簡単なイメージ
- CodeProcessor
- Challenge [#e9ce53e8]
- vectorのチャレンジの仕方
hoge,foo,test
- とすると、vector[3]={hoge, foo, test};となる。
- 変なスペースはつけてはならない。
- 最後にカンマをつけてはならない。
Codeforces †
Atcoder †
問題の見方 †
流れ †
- google翻訳に問題文を突っ込む
- 実験
- 明らかな条件を列挙し、覚えておく。自明な条件をコーナーケースとして把握する。
- 求められる情報量の確認
- yes-noか、max-minか、numかなど。少ない情報ならまとめられる。
- 計算機特有の発想
- 特性関数の作りやすさ。この答え（以上・以下）は問いの答えたりえるか？という質問に簡単に答えられるかを確認する。
- 半分全列挙
- 計算量
- アルゴリズムに要求される計算量のキツさを確認する。
- 頑張って実装
- テスト
- 時間最大セットと、メモリ最大セットと、コーナーケースで通るかを確認する。
チェックリスト †
| チェック項目 | 説明 | | デバッグメッセージを残すな | | | 自前テストしたか | 極端な例（入力の小さいもの大きいもの）、最小の普通なもの、普通なもの、疎密（密粗密なども） | | 1行に複数の値を返す時、きちんと最後のスペースを除け | | | コーナーケースできちんとcout << 1 << endl; return 0;せよ | Atcoder, Codeforcesなどだと、間違えてreturn ret;とかすると死ぬ | | 何もかもlong longにせよ | 掛け算でキャストミスしないために | | はじめに書いたコーナーケースを最後にも確認せよ | | | 整数同士の掛け算がオーバーフローしないか確認せよ | c[i]*c[i+1]でオーバーフローしえるので注意 | | 整数同士の割り算がlgaussかugaussか確認 | intがlgaussになるのは同符号の時だけ | | valgrindをかけよ | | | 盤面問題で、添字はあっているか確認せよ | 添字のn, mを逆にしたりしてないか？ |
コーディング中の注意 †
| 注意 | 説明 | | long longでの演算 | 10^18とかの場合、一回も掛け算してはならない！ | | 負の%とif文の相性は最悪 | 両方正にして比較すること | | Mod構造体のリテラルは必ずキャストすること | ^がxorと判断されたりなど超絶面倒なバグが起きる |
入出力 †
- cinは遅い。
- 30万変数読み込みで、scanfだと50ms, cinだと150ms
- 同期を切ると早くなる
- 切ったらもうcinとscanfを混ぜて使ってはいけない
計算量 †
| 計算量 | 安全 | 無理 | | 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) |
よく使うデータ構造と関数と注意点早見表 †
| 名前 | メソッド | 注意 | | unordered_map | erase, count, find | tupleを突っ込めない。ソートされない。でも速い。 | | map | erase, count, find | tupleを突っ込める。50000要素でunordered_mapの3倍遅い。比較1, 2, 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に突っ込めない。 |
命名規則 †
- 添字の逆引きはinvをつける。
- 例えばvector<int> a;に対しては、unordered_map<int, int> ainv;
- int dx={0,0,1,-1}; dy={1,-1,0,0};は、使う添字の名前を借りてdi, djに。
イディオム †
- 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:;
}
|
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
