- 追加された行はこの色です。
- 削除された行はこの色です。
[[プログラミングコンテスト]]
*プロコンサイト [#m0ecf4a6]
**Topcoder [#meace356]
-div2 Hard は難易度的には div1 medium より簡単なイメージ
-[[CodeProcessor>https://github.com/hamko/topcoder/blob/master/codeprocessor.txt]]
-Challenge [#e9ce53e8]
--vectorのチャレンジの仕方
hoge,foo,test
--とすると、vector[3]={hoge, foo, test};となる。
--変なスペースはつけてはならない。
--最後にカンマをつけてはならない。
**Codeforces [#od15d7fb]
**Atcoder [#j0c642d0]
*問題の見方 [#h414205c]
**流れ [#hf705694]
+google翻訳に問題文を突っ込む
+実験
++明らかな条件を列挙し、覚えておく。自明な条件をコーナーケースとして把握する。
+求められる情報量の確認
--yes-noか、max-minか、numかなど。少ない情報ならまとめられる。
+計算機特有の発想
++特性関数の作りやすさ。この答え（以上・以下）は問いの答えたりえるか？という質問に簡単に答えられるかを確認する。
++半分全列挙
+計算量
--アルゴリズムに要求される計算量のキツさを確認する。
+頑張って実装
+テスト
--時間最大セットと、メモリ最大セットと、コーナーケースで通るかを確認する。
**チェックリスト [#yed7affe]
|チェック項目|説明|h
|デバッグメッセージを残すな||
|自前テストしたか|極端な例（入力の小さいもの大きいもの）、最小の普通なもの、普通なもの、疎密（密粗密なども）|
|1行に複数の値を返す時、きちんと最後のスペースを除け||
|コーナーケースできちんとcout << 1 << endl; return 0;せよ|Atcoder, Codeforcesなどだと、間違えてreturn ret;とかすると死ぬ|
|何もかもlong longにせよ|掛け算でキャストミスしないために|
|はじめに書いたコーナーケースを最後にも確認せよ||
|整数同士の掛け算がオーバーフローしないか確認せよ|c[i]*c[i+1]でオーバーフローしえるので注意|
|整数同士の割り算がlgaussかugaussか確認|intがlgaussになるのは同符号の時だけ|
|valgrindをかけよ||
|盤面問題で、添字はあっているか確認せよ|添字のn, mを逆にしたりしてないか？|
**コーディング中の注意 [#k8c22f3d]
|注意|説明|h
|long longでの演算|10^18とかの場合、一回も掛け算してはならない！|
|負の%とif文の相性は最悪|両方正にして比較すること|
|Mod構造体のリテラルは必ずキャストすること|^がxorと判断されたりなど超絶面倒なバグが起きる|
*入出力 [#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)|
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
