Hatena::Grouptopcoder

k_operafanのTopCoder日記

2011-12-14提出前チェックリスト

Competitive Programming Advent Calendarの第14日目の記事です.

わたしにとって競技プログラミングをやっていて一番悔しいことは,本質に関係の無いちょっとしたミスで正解を逃すことです.

そういうミスを避けるために,陥りやすいミスをまとめてみました.

提出してしまうとRuntime Errorになってしまうミス 23:59

スタックオーバフロー

再帰の深さが大きくなりすぎると,スタックオーバーフローを起こしてしまいます.

特にメモ化再帰で深さが10000を超える場合は注意が必要です.

巨大なケースを試してみて,正常に終了するかを確認して,メモ化再帰だったらDPに書き換えたり,末尾再帰等ならループに書き換えるようにしましょう.

対策
  • 巨大なケースを試す.
  • ローカルで実行するならスタック領域を増やす.
  • メモ化再帰→DP

などなど

配列外アクセス

配列外アクセスは例えばDPなどで起こりやすいです.

char型配列で文字列を持つ場合の最後の'\0'は忘れがちなので気を付けましょう.

対策
  • 巨大なケースで試す
  • ある程度多めに配列を確保するようにする
  • char型配列を使わずにstringを使う

などなど

オーバーフロー

.NET系の言語ではオーバーフローは例外になります

提出してしまうとWrong Answerになってしまうミス 23:59

初期化忘れ

テストケースが複数ある問題の場合,初期化を必ず忘れないようにしましょう.

対策
  • 複数ケースの場合をかならずチェックする

など

オーバーフロー

各型の保持出来る値の範囲は以下のようになっています.

C++ Java .NET(C#/VB) 値の範囲
char char char/Char -128~127
short short short/Short -32768~32767
int int int/Integer -2147483648~2147483647(≒-2*109~2*109)
long long long long/Long -9223372036854775808~9223372036854775807(≒-9*1018~9*1018)
- - decimal/Decimal -79228162514264337593543950336~79228162514264337593543950335(≒-7*1029~7*1029)

これを超えることが無いかあらかじめ計算するようにした方が良いです

対策
  • 巨大な数のケースをチェックする
  • 多倍長整数を使う

などなど

浮動小数の誤差

整数に対してpowやsqrtを用いた場合も若干の誤差を生じることがあります.

実装依存ですが,例えばa=5,b=2の時に,(int)pow(a,b)=(int)24.9999999999=24になってしまったりすることがあります.

これを防ぐために,答えが整数であることを期待している場合でも(int)(pow(a,b)+1e-7)のように適当な小さい値を足すようにした方が良いと思います.

対策
  • 微小値を足す
  • powの場合はループで,sqrtの場合は二分探索などで自前実装する

などなど

MODの値のミス

問題によっては答えの値をMで割った余りの形で出力させるものがありますが,Mを間違えると当然答えが変わってしまいます.

108+7と109+7はともに素数で間違えやすいので特に気を付けましょう.

対策
  • 問題文からコピーペーストする

など



提出してしまうとTime Limit Exceedになるようなミス

メモ化忘れ

メモ化再帰においてメモ化を忘れてしまうと,TLEしてしまいます.

大きなケースでチェックするのを忘れないようにしましょう.

対策
  • 大きなケースでチェックする
  • 最初からメモ化するようにする

などなど

入出力方法

入力の数がとても多い問題の場合,遅い入力方法を使うとTLEしてしまうことがあります(特にPKUでは顕著).

入力が多いとき,

C++でcinを使っている場合はscanfやreadを

Javaでscannerを使っている場合はBufferedReaderを

使うようにしましょう

対策
  • 入力を早い方法に変える

非正規化数

kou_miyamさんのhttp://d.hatena.ne.jp/komiyam/20111210/1323503019に詳しくかつ分かりやすく載っています.

遅い標準ライブラリ

時間制限が厳しい問題の場合,hypot関数やstd::setなどのように若干遅い関数等を使うとTLEしてしまうことがあります.(これもやっぱりPKUで顕著 -O2欲しい)

対策
  • 自前で実装した高速なものを使う

通る人通る人2011/12/15 23:52challenge Integer.MAX_VALUE ?

k_operafank_operafan2012/01/02 09:11Challenge Succeed!

BoomerBoomer2012/11/15 08:57All of my questions setlted-thanks!

xmimisyrhxmimisyrh2012/11/17 05:22IMxCtU , [url=http://qdasntgfcpon.com/]qdasntgfcpon[/url], [link=http://njumodhpdivd.com/]njumodhpdivd[/link], http://culsmafenbge.com/

lupbuvhlupbuvh2012/11/17 12:2177HEfx <a href="http://yzztpjtvxzxi.com/">yzztpjtvxzxi</a>

iuqchfunkaiuqchfunka2012/11/17 21:47MK9m7k , [url=http://lgglcwpigfob.com/]lgglcwpigfob[/url], [link=http://wnxysjrvjnzr.com/]wnxysjrvjnzr[/link], http://khcneckuryza.com/