プロコン

目次

プロコンサイト

level.png

Topcoder

  • 難易度はD1E<<D2M<=D1E<D1H<=D1M<D1H
    • 例えばLuckySum?はDiv1 EasyがDiv2 Hard
  • Challenge
    • vectorのチャレンジの仕方
      hoge,foo,test
    • とすると、vector[3]={hoge, foo, test};となる。変なスペースはつけてはならない、最後にカンマをつけてはならない。
  • Topcoderはやたら制約が雑
    • 大体の制約がN<50
    • n!、2^n, nCn/2の全探索は無理。
    • 2^25の半分全列挙はできる。
  • 「最近のTopcoder Div.1 Easy 250点は昔の450点、最近の300点は昔の600点に相当する難易度である」という分析
    • 2個前のSRMは、参加者の21%しかEasy正答してないようです(Sunny Graphの回)。40%というとDiv.1の黄色以上、20%というと黄色上位40%以上ですね。今回のはともかく、黄40%以上の問題をEasyというのは、うーん、という感じしますね。
    • 非公式難易度の色を「この色の人なら解けるはず」とざっくり近似すると、今回のは昔の450点で、前々回のは昔の600点に相当する難易度らいしですね(できない理由を分析しても意味ないので力をつけたい)

Codeforces

  • 別のフォルダを開いてる可能性があるので、ちゃんと注意!!
  • レートの直感
    • Div.2 OnlyでDiv.1の人が入っているコンテストなら、レート1750で738 th/4199くらいが妥当な感じ(上から18%)
    • 150 th / 3000くらいを安定で出すと、紫になる。
    • 1710でぴったりRank: 535 th / 3975くらい
  • 同期切ったlong longのcinがCodeforcesだと遅い
    • 普通、同期を切ると、coutがscanfと同じスピードになるが、long longだとならない。
    • TLEを経験したので、Codeforcesでは二度とlong long以外でcin使わない

Atcoder

  • 日本語、解説が付いているのが良い。
  • 他の人のコードを気軽にコピーできるので比較もしやすい。

csac academy

AOJ

  • systemという単語が入ってるだけでJudge Not Availableになる

問題の見方

流れ

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

チェックリスト

チェック項目説明
デバッグメッセージを残すな
自前テストしたか極端な例(入力の小さいもの大きいもの)、最小の普通なもの、普通なもの、疎密(密粗密なども)
1行に複数の値を返す時、きちんと最後のスペースを除け
コーナーケースできちんとcout << 1 << endl; return 0;せよAtcoder, Codeforcesなどだと、間違えてreturn ret;とかすると死ぬ
intを全てlong longにせよ掛け算でキャストミスしないために
数字リテラルをlong long, long doubleにせよ掛け算とbit shiftでキャストミスしないように。1ll, 1.0l
INF, EPSを使っているなら、その値は正しいかINF大きすぎると、INF+aでオーバーフローしかねない。
はじめに書いたコーナーケースを最後にも確認せよ
整数同士の掛け算がオーバーフローしないか確認せよ10^18とかの場合、一回も掛け算してはならない!c[i]*c[i+1]でオーバーフローしえるので注意。
整数同士の割り算がlgaussかugaussか確認intがlgaussになるのは同符号の時だけ
valgrindをかけよ
盤面問題で、添字はあっているか確認せよ添字のn, mを逆にしたりしてないか?
負の%とif文が同時にないか確認両方正にして比較すること
Mod構造体のリテラルは必ずキャストすること^がxorと判断されたりなど超絶面倒なバグが起きる

コーディング注意

注意点説明
盤面など添字が複雑な場合は、なるべく命名規則を一貫させること(i, j)の盤面の大きさはni, njなど
.size()などが利用可能なら、なるべくnとかmのようなコピーしたものではなく、sizeを使うデバッグ時、nってなんだっけ?とかなるので

入出力

  • 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, findtupleを突っ込めない。ソートされない。でも速い。
maperase, count, findtupleを突っ込める。50000要素で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>は使用禁止
listpush_back, push_front, erase(消したら次の要素を返す)++, --は定義されているが、+, -オペレータは定義されていない!やりたいなら、advance(it, n)とprev(it, n)を使うこと。
tuplemake_tuple, getほぼ何でもあり。unordered_mapに突っ込めない。
  • メモの速度
    • unordered_mapは定数倍が20くらいかかるので、できることならちゃんと配列でメモすること!
    • かかる時間は、vector : unordered_map : map = 1 : 20 : 40 (5000要素)
    • かかる時間は、vector : unordered_map : map = 1 : 20 : 60 (50000要素)
  • スコープ外で一回定義してclearと、内部で何回も定義するのは、速度が同じ。
    • わかりやすくなるので、内部で何回も定義する方向で

命名規則

  • 添字の逆引きは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:;
}
  • 浮動小数点の比較は、<=ならゆるいから+EPS, <ならせまいから-EPSなどが明確にわかるようになる
    • a <= b + EPS
    • a < b - EPS
  • 左辺値も三項演算子使える
( i < x ? a : b )++;
vector<int> v1, v2; ( i < x ? v1 : v2 ).push_back( i );
  • repのメリット
    • タイプ量が短い
    • 変数名の変更に強い
    • forは長いので、repなのか変な条件のループなのかわかりにくい
    • 逆に for があったら注意して見る必要があるとわかる

レーティングごとの正答率

  • Topcoderのレーティング維持には、要約すると以下が必要。
    • 「黄下位でE50%, M5%」
    • 「黄上位でE75%, M10%」
    • 「赤下位でE75%, M30%」
    • 「赤上位でE80%, M40%, H5%」
    • 「的でE90%, M60%, H10%」
  • 参考データ

|name|rating|Easy|Med|Hard|h

tubo28145042%5%0%
konjo155060%4%0%
shindannin160063%8%0%
btk165050%6%0%
mayoko170050%5%0%
pekempey170055%10%0%
darsein200072%13%0%
kyuridenamida210075%13%2%
DEGwer220075%28%5%
misawa220068%28%7%
kmjp220068%27%0%
yosupo240077%43%2%
chokudai270080%40%4%
snuke280074%46%7%
iwi310087%60%12%
Petr370097%89%66%

悪問


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