プログラミングコンテスト

プロコンサイト

level.png

Topcoder

  • div2 Hard は難易度的には div1 medium より簡単なイメージ
  • CodeProcessor
  • Challenge [#e9ce53e8]
    • vectorのチャレンジの仕方
      hoge,foo,test
    • とすると、vector[3]={hoge, foo, test};となる。
    • 変なスペースはつけてはならない。
    • 最後にカンマをつけてはならない。

Codeforces

Atcoder

問題の見方

流れ

  1. google翻訳に問題文を突っ込む
  2. 実験
    1. 明らかな条件を列挙し、覚えておく。自明な条件をコーナーケースとして把握する。
  3. 求められる情報量の確認
    • yes-noか、max-minか、numかなど。少ない情報ならまとめられる。
  4. 計算機特有の発想
    1. 特性関数の作りやすさ。この答え(以上・以下)は問いの答えたりえるか?という質問に簡単に答えられるかを確認する。
    2. 半分全列挙
  5. 計算量
    • アルゴリズムに要求される計算量のキツさを確認する。
  6. 頑張って実装
  7. テスト
    • 時間最大セットと、メモリ最大セットと、コーナーケースで通るかを確認する。

チェックリスト

チェック項目説明
デバッグメッセージを残すな
自前テストしたか極端な例(入力の小さいもの大きいもの)、最小の普通なもの、普通なもの、疎密(密粗密なども)
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を混ぜて使ってはいけない

計算量

  • 1秒とは?=3千万くらいは行ける。1億は無理。
計算量安全無理
O(n)3000万1億=10^8
O(n log n)100万400万
O(n^2)500010000
O(n^3)300450
O(n^4)75100
O(2^n)2527
O(3^n)1517
  • 制約2秒程度だったら、逆にどんな計算量が求められている?
制約アルゴリズム
10^6O(n)以下、軽いO(n log n)
10^5O(n log n)以下
3000O(n^2)
500軽いO(n^3)
100O(n^3)
30O(2^n)の半分全列挙
20O(2^n)、O(n 2^n)

よく使うデータ構造と関数と注意点早見表

名前メソッド注意
unordered_maperase, countソートされない。
maperase, count, find50000要素でunordered_mapの3倍遅い。比較1, 2, m.findはnot foundでm.end(), その他でイテレータを返す
setcount, erase, insert
queueempty, size, front, pop, push
priority_queueempty, size, top, pop, pushデフォルトで降順
stackempty, size, top, pop, push
dequepush_back, push_front前に挿入できるvector。前に挿入できるので添字が移動する
vectorpush_backvector<bool>は使用禁止

命名規則

  • 添字の逆引きはinvをつける。
    • 例えばvector<int> a;に対しては、unordered_map<int, int> ainv;
  • int dx={0,0,1,-1}; dy={1,-1,0,0};は、使う添字の名前を借りてdi, djに。

トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS