競プロのデバッグで着目する２０個のこと

はじめに

プログラミングにおけるデバッグ…それはなるべく避けたいもの。
たとえ、注意していても、ミスはする。
競技プログラミングでは、高速コーディングが重要。
なので、バグを生みやすい。だから、デバッグ作業は付き物である。

まずは、よくある実行時の異常

配列外アクセス

Array Index Out Of Bounds Exception

例: a[0] ~ a[9] しかアクセスできない。

int array[10];
array[10] = 123;  // Error

スタックオーバーフロー

Stack Overflow Exception

再帰しすぎ。return; が実行されない。

例: 階乗を求めたくても、これでは return されない

int factorial(int n){
  return n * factorial(n - 1);
}

デバックで着目する２０個のこと

「コーディングできてるはずなのに！なんで？」
という場合の、デバッグポイントを並べてみる。
競技プログラミングでジャッジフィードバッグが不正解の時に確認すると良い。

1. 出力形式が合っているか

改行、大文字、小文字、要素数、桁数、有効数字
"YES" , "Yes" や "NG" , "NA" の出力ミス

2. 入力制限下で 最小値・最大値 での実行ができるか

最大値で初期化すると、演算でオーバーフローしている場合がある

3. 稀にある特別な入力が実行できるか

2次元マップ、2 x 2 以上の制約がなければ、 1 × □ , □ × 1 を試す
場合によっては乱数による実験も視野に

4. 浮動小数点の計算における誤差が発生していないか

宣言型と演算の確認
キャストによる自動型変換、型解釈に注意
d1==d2 は 危険

5. 値の初期化が間違っていないか

初期化が本当に、必要か、不要か
boolean型での true, false の定義確認
intで 0, 1 など初期化ミス

6. テストケース２つ目に対して実行できるか

正常な場所での初期化確認
テストケース1,2の順番を変えて入力してみる
大域変数は再利用されている可能性があるので注意

7. 配列要素のインデックス指定ミスしていないか

単純に i と j
2次元マップで x , y のどちらが縦か横か
混乱するぐらいなら1文字は避けて意味のある変数に

8. if や for の条件式はあっているか

i=0 など配列外アクセス絞りでミスの可能性
代入 = 、同値 == は適切か

例: if 文の条件で代入している

int i = 0;

if(i = 0){
  printf("iは0です¥n");  // 出力されない
}
else{
  printf("iは0ではありません¥n"); // 出力される
}

9. ループ初回と最終回で想定外の挙動はしていないか

値の代入また出力より先に break; , return; をしてしまう

10. 似た文字混用で指定ミスしていないか

i , 1 , l (小文字エル) , I (大文字アイ) や 0 , O , o

11. 入力値は正常に受け取れているか

C言語での scanf("%c",&var) と scanf("%s",&var)
Javaでの next() と nextLine()
改行文字は含まれるのかどうか

12. 終端文字 '\0' や ポインタ終端 NULL の記述ミスはないか

C言語、%sでの出力が適切でなければ、終端文字が怪しい

13. 問題の意図にあっているか

問題文をしっかり読めていなく、違う処理をしている
出力内容や順序をよく確認

14. 問題だけでなくテストケースを確認する

ヒントがあるかもなので、手でトレースをしてみる

15. 問題解決のアルゴリズムのミスはないか

考えが甘いかも
計算の例外がある可能性を考える

16. 提出フォーマットが不適切ではないか

クラス名がMain限定、package宣言NGなどありえる
提出時には「Wrong Answer」ではなく「Presentation Error」だったりする
言語選択ミスもありえる

17. 文字リテラルに対しての処理が適切か

文字として数を扱うと、文字から'0'を引いて整数値にし忘れる

例: 文字を整数値で出力

char num = '5';

printf("%d¥n",num); // 53

例: 1+1=2 ではない (そもそも型が悪い)

String a = "1";

System.out.println(a+a); // 11

18. インクリメントの混用

++i と i++ と i=i+1 と i+1 は違う
ループまた再帰内でのインクリメント注意

19. 条件式の実行階層や条件

else if (前ifで真なら評価しない) と if (前ifで真偽いずれも評価する) での挙動違いミス

20. データ構造の欠陥

確保すべき配列要素数の欠落など

紹介した20個をキーワードでまとめ！

1. 出力形式
2. 最小最大値
3. 特別な入力
4. 浮動小数点誤差
5. 初期化
6. 2つ目テストケース
7. インデックス指定
8. if,for条件
9. ループ初回、最終回
10. 似た文字
11. 入力受取
12. 終端
13. 問題意図
14. テストケース確認
15. アルゴリズム
16. 提出フォーマット
17. 文字リテラル
18. インクリメント
19. 条件式階層
20. データ構造