「プロコンでのWrong Answerの原因」ビンゴ

一時期なんちゃらビンゴというものがTwitterで流行っていて, そのときに競技プログラミング界隈向けにWrong Answerの原因ビンゴというものを作りました. 自分が遭遇したことのある間違いばかりを並べたこともあって,ほとんど当たってしまう人も多かったようです. せっかくなので,いくつかの番号について少し書こうと思います.

1: i, jの書き違い (例: for(int i = 0; i < n; i++) for(int j = 0; j < m; i++) )
2: 問題文の読み違え
3: 変数名の重複
4: 提出するコードを間違える
5: 初期化忘れ
6: 計算量の見誤り
7: builtin関数の未定義動作 (例: __builtin_ctz(0) )
8: 二分探索の最大値・最小値の見誤り
9: forの++,--を逆にする (例: for(int i = n - 1; i >= 0; i++) )
10: long longなのにint用の関数を使う
11: オーバーフロー
12: 配列のサイズ不足
13: free!
14: set, mapが遅くてTLE
15: 剰余を取るのを忘れる
16: コーナーケース
17: n = 0のときを忘れる
18: 0除算
19: メモ化できていない
20: 嘘の貪欲解法
21: 出力する文字列のスペルミス
22: 浮動小数点の誤差
23: 負の数の剰余の扱い (例: 間違い: a = (b - c) % MOD, 正解: a = (b - c + MOD) % MOD)
24: 入力をcinで取ってTLE
25: 配列外参照

1: i, jの書き違い

for(int i = 0; i < n; i++){
    for(int j = i + 1; j < n; i++){
        if(list[i] > list[j]){
            swap(list[i], list[j]);
        }
    }
}

上のようにi,jを使った二重ループを書くことはC++では非常に多いです. そのときに内側のfor文の中のjを誤ってiと書いてしまうことがあります.

この間違いの面倒なところの一つは,フォントによってはiとjがとても似ていて,目で区別がつきにくいところです. 二つの変数の見分けがつきやすいようにi, jの代わりにi, kを使う人もいるらしいです.

競技プログラミング界隈の賛否両論な習慣の一つとしてREPマクロというものがあります.

#define REP(i,n) for(int i=0; i<(int)(n); i++)

REPマクロを嫌う人も多いですが,このマクロは変数名を1回しか書かないので,このバグを防げるという意味では大変合理的な方法です.

3: 変数名の重複

int ans = ...;
for(int vi : v){
    ...
    int ans = ...;
    ...
    ans += ...;
}

このように異なるスコープで同名の変数を宣言してしまったために,意図せぬ動作を引き起こすことがあります. コンパイラオプションに-Wshadowをつけると警告を出してくれるので,ぜひつけると良いと思います.

4: 提出コードを間違える

特にICPC国内予選ではこの間違いは致命的です. ICPC国内予選は過去に提出したコードや解答を見れないシステムになっているので, 仮に間違いの可能性に気づいたとしても確認する方法がないので,ペナルティー覚悟で再度提出して確認するしか方法がありません.

5: 初期化忘れ

たぶんプロコンにかぎらず,一般によくあるバグな気がします. C++の構造体のメンバ変数は,グローバル変数と違って0で初期化されないので注意しましょう. 一度うちのチームでこのバグに引っかかりました.

10: long longなのにint用の関数を使う

long longの変数に対して__builtin_popcount()を使ってしまったことがあります. long longに対しては__builtin_popcountll()というものがあります.

11: オーバーフロー

これもプログラミングコンテストに限らずよくある有名なバグです. 最近では,INT_MIN * -1がint型に収まらないことを罠にした問題をよく見る気がします.

12: 配列のサイズ不足

入力サイズより少し大きめの配列をとる習慣をつけると,このバグをいくらか防げるようになります.

14: set, mapが遅くてTLE

setやmapは定数倍が大きいので計算量が大丈夫そうに見えてもTLEしやすいです. 同じ計算量でもvectorを使うと速くなることがあります. 例えばuniqueな数列が欲しいときには,下のように,setの代わりにvectorを使うと速くなります.(確認してないので嘘かもしれません.)

// setを使う場合
set<int> s;
for(int i = 0; i < n; i++){
    int x;
    cin >> x;
    s.insert(x);
}

// vectorを使う場合
vector<int> v;
for(int i = 0; i < n; i++){
    int x;
    cin >> x;
    v.push_back(x);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

15: 剰余を取るのを忘れる

一行に長い式を書いたときに,計算の途中で剰余を取るのを忘れて オーバーフローしてしまうようなバグが起こりやすいです.

17, 19

提出の前に,最小ケース・最大ケースで解答を確認するとだいたい防げます.

21: 出力する文字列のスペルミス

x:ambigious o:ambiguous

23: 負の数の剰余の扱い

負の数の剰余はプログラミング言語によって結果が変わります(参考). 割られる数が正になるように割る数をあらかじめ足すこと,などで避けましょう.

24: 入力をcinで取ってTLE

入力を取るだけでTLEになるようなひどいオンラインジャッジが存在します.

More Reading