プロコン/特有の注意 のバックアップ差分(No.23)

• バックアップ一覧
• 現在との差分 を表示
• ソース を表示
• バックアップ を表示
• プロコン/特有の注意 へ行く。
  • 1 (2016-05-04 (水) 09:41:40)
  • 2 (2016-05-04 (水) 10:28:44)
  • 3 (2016-05-05 (木) 00:18:14)
  • 4 (2016-05-05 (木) 05:53:14)
  • 5 (2016-05-08 (日) 13:36:07)
  • 6 (2016-05-09 (月) 10:48:18)
  • 7 (2016-05-12 (木) 05:50:52)
  • 8 (2016-05-12 (木) 09:56:48)
  • 9 (2016-05-14 (土) 04:19:06)
  • 10 (2016-06-01 (水) 12:18:09)
  • 11 (2016-06-11 (土) 04:49:40)
  • 12 (2016-06-16 (木) 07:26:08)
  • 13 (2016-06-20 (月) 13:50:20)
  • 14 (2016-06-26 (日) 14:50:13)
  • 15 (2016-06-27 (月) 12:47:30)
  • 16 (2016-07-11 (月) 15:43:01)
  • 17 (2016-08-18 (木) 17:17:05)
  • 18 (2016-08-20 (土) 02:10:23)
  • 19 (2016-08-22 (月) 04:59:09)
  • 20 (2016-08-25 (木) 05:33:13)
  • 21 (2016-09-02 (金) 09:08:05)
  • 22 (2016-09-09 (金) 05:57:37)
  • 23 (2017-01-16 (月) 20:14:39)
  • 24 (2017-05-18 (木) 00:14:03)
  • 25 (2017-05-24 (水) 15:57:44)

• 追加された行はこの色です。
• 削除された行はこの色です。

[[プロコン]]

*目次 [#fdd746bd]
#contents

*プロコンサイト [#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点に相当する難易度らいしですね（できない理由を分析しても意味ないので力をつけたい）
-Topcoderは、時間がギリギリかもしれなかったら、テストケースを追加することでサーバの実行時間を調べることが出来る。


**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使わない

-Codeforces Div.1 母数600人で
--400位 1900（紫）
---''2完しないと絶対落ちる！''
---だいたいABをめっちゃゆっくり解くとこれくらい
--300位 2000
---これくらいでDiv.2 60位/4663位
--200位 2200（黄）
--150位 2300
---これくらいで3完してる
--100位 2400（赤）
--60位レーティング2600（赤赤）
--20位レーティング2900（赤赤赤）

-Div.1のハック
--ハック祭りになる時とならない時で、かなり差がある
--基本的にはHack祭りにはならないが、[[こういう>http://codeforces.com/contest/687/standings]]時もある。

**Atcoder [#j0c642d0]
-日本語、解説が付いているのが良い。
-他の人のコードを気軽にコピーできるので比較もしやすい。
**csac academy [#a8adb765]
-https://csacademy.com/contests/

**AOJ [#x252091c]
-systemという単語が入ってるだけでJudge Not Availableになる

**Leetcode [#l0b2194b]
-制約書いていない。
--この感じ、実務的でよいかも。
--就活対策でよく使わられているらしい

*問題の見方 [#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]]

*テスター [#gc4f780a]
-テストケースをassertなどで（REにならないか）制約の確認していただく。
-ACしてもらう。
-問題文におかしくないか（日本語的に理解し難い・複数解釈できるなど）