プログラミングコンテストを解くときに気をつけること
Google Code JamやTopCoderに参加してみて得た教訓です。今後の糧とするために。
なんか素人丸出しな感じですが…。しばらく後にこれを振り返ったとき「初めはこんなもんだったなー」と感慨深そう。
思いつきしだい随時追加していきます。
- intはけっこうすぐあふれる
- 10万*10万や2000*2000*2000でもうだめ
- 怪しそうだったら「とりあえずlongで」
- doubleの誤差を見くびるな
- 怪しそうだったら「とりあえずBigDecimalで」
- パラメータの取り得る大きさを確認する
- サイズが10^5を超えるあたりからO(n^2)だとつらいという感じ?
- アルゴリズムのオーダーと計算量の感覚は、問題数を解いて養おう
- 問題の意図を読み違えない
- かなりありがち
- 問題を間違って解釈してたら、ただの時間の無駄になってしまう
- しらみつぶしの解法でもまず書いてみる
- その過程で見えてくることもある
- ものによってはしらみつぶしで十分だったりする
- 境界値テストケースは自作する
- サンプルのテストケースはあくまでサンプル
- 変数名は短く
- つい仕事の時の癖で説明的な名前を付けて無駄にタイプ数を多くしてしまうので
- 数学的考察がキモなこともある
- プログラムをがんがん回さなくても数学的に解けちゃうことがある(例:GCJ Round1A の問題C)
- いかにキャッシュを効果的に効かせるか
- 数学的検証を厳密にするより、見切り発車でやらないと仕方ないこともある