[[プロコン]] *目次 [#fdd746bd] #contents *チャレンジ [#f0b5b24f] -自分が思いついたけどダメだった貪欲解を実装しておく --SRM4回目、XORの貪欲では、4chal成功した -topcoderでは[[事前にチャレンジケースを作っておく>https://twitter.com/chokudai/status/766257809344241664]] -topcoderでは''負の点数になるとチャレンジできなくなる!!なので、初めのチャレンジは非常に慎重に!!'' *プロコンサイト [#m0ecf4a6] &ref(./level.png,50%); **Topcoder [#meace356] -難易度は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 [#od15d7fb] -''別のフォルダを開いてる可能性があるので、ちゃんと注意!!'' -レートの直感 --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 [#j0c642d0] -日本語、解説が付いているのが良い。 -他の人のコードを気軽にコピーできるので比較もしやすい。 **csac academy [#a8adb765] -https://csacademy.com/contests/ **AOJ [#x252091c] -systemという単語が入ってるだけでJudge Not Availableになる *問題の見方 [#h414205c] **流れ [#hf705694] +google翻訳に問題文を突っ込む +実験 ++明らかな条件を列挙し、覚えておく。自明な条件をコーナーケースとして把握する。 +求められる情報量の確認 --yes-noか、max-minか、numかなど。少ない情報ならまとめられる。 +計算機特有の発想 ++特性関数の作りやすさ。この答え(以上・以下)は問いの答えたりえるか?という質問に簡単に答えられるかを確認する。 ++半分全列挙。問題を半分にすると、マージが楽ではないか? ++DP。問題を極限まで小さくしたら、自明な解が存在しないか?そして、小さい問題から大きい問題の答えにできないか? ++ダブリング。半分半分の漸化式が作れるか? +計算量 --アルゴリズムに要求される計算量のキツさを確認する。 +頑張って実装 +テスト --時間最大セットと、メモリ最大セットと、コーナーケースで通るかを確認する。 --疎な最大ケース 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;とかすると死ぬ| |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と判断されたりなど超絶面倒なバグが起きる| *コーディング注意 [#qdeeca6a] |注意点|説明|h |盤面など添字が複雑な場合は、なるべく命名規則を一貫させること|(i, j)の盤面の大きさはni, njなど| |.size()などが利用可能なら、なるべくnとかmのようなコピーしたものではなく、sizeを使う|デバッグ時、nってなんだっけ?とかなるので| *入出力 [#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>は使用禁止| |list|push_back, push_front, erase(消したら次の要素を返す)|++, --は定義されているが、+, -オペレータは定義されていない!やりたいなら、advance(it, n)とprev(it, n)を使うこと。| |tuple|make_tuple, get|ほぼ何でもあり。unordered_mapに突っ込めない。| -メモの速度 --unordered_mapは定数倍が20くらいかかるので、できることならちゃんと配列でメモすること! --かかる時間は、vector : unordered_map : map = 1 : 20 : 40 (5000要素) --かかる時間は、vector : unordered_map : map = 1 : 20 : 60 (50000要素) -スコープ外で一回定義してclearと、内部で何回も定義するのは、速度が同じ。 --わかりやすくなるので、内部で何回も定義する方向で *命名規則 [#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 ); -repのメリット --タイプ量が短い --変数名の変更に強い --forは長いので、repなのか変な条件のループなのかわかりにくい --逆に for があったら注意して見る必要があるとわかる *レーティングごとの正答率 [#mc95363c] -Topcoderのレーティング維持には、要約すると以下が必要。 --「黄下位でE50%, M5%」 --「黄上位でE75%, M10%」 --「赤下位でE75%, M30%」 --「赤上位でE80%, M40%, H5%」 --「的でE90%, M60%, H10%」 -参考データ |name|rating|Easy|Med|Hard|h |tubo28|1450|42%|5%|0%| |konjo|1550|60%|4%|0%| |shindannin|1600|63%|8%|0%| |btk|1650|50%|6%|0%| |mayoko|1700|50%|5%|0%| |pekempey|1700|55%|10%|0%| |darsein|2000|72%|13%|0%| |kyuridenamida|2100|75%|13%|2%| |DEGwer|2200|75%|28%|5%| |misawa|2200|68%|28%|7%| |kmjp|2200|68%|27%|0%| |yosupo|2400|77%|43%|2%| |chokudai|2700|80%|40%|4%| |snuke|2800|74%|46%|7%| |iwi|3100|87%|60%|12%| |Petr|3700|97%|89%|66%| *悪問 [#c9e583ce] -[[作問の失敗例>http://tozangezan.hatenablog.com/entry/2015/12/02/000030]] |