はじめに
競プロ er がちょこちょこハマる、(ほとんど)言語に依らない典型的なミスを整理して、それらの対策を考えてみます。
完璧な対策は無いと思いますが、よくやってしまうミスを把握して、自分なりの対策を持っておくようにすると、段々と同じようなミスは減っていくと思います。
数値計算周り
オーバーフロー
int64 を使うべきところで、int32 を使ってしまい、オーバーフローが発生してしまう。
対策
基本的には、制約と計算内容からきちんと考えることが大切です。
しかし、それが面倒な場合は、常に int64 を使うといった手段を取ることもできます。
C, C++ だと、int64 相当を常に使うために、以下のような記述が使われることがあります。
#define int long long
副作用も多いため、あまり推奨はしません。
mod の取り忘れ
-
(a * b * c) % MODのように計算し、オーバーフローが発生する -
(a - b) % MODの計算で結果が負数になり、そのまま出力してしまう
対策
Mod 用の構造体 (ModInt) などを利用するようにしましょう。
自作ライブラリでも ac-library でも良いですが、modint を利用することで、計算の度に余りを意識する必要が無くなります。
浮動小数点の誤差
-
floatやdoubleの比較に==を使い、誤差で正しく判定ができない - 精度が足りず、正解とわずかに誤差がでてしまう
対策
- 整数のみで計算を行えないかを検討する
- 例: $A / B = C / D$ を $A \times D = C \times B$ と変形して比較する
- 誤差を許容する比較関数を用意する
bool equal(float a, float b, float eps = 1e-9) { return abs(a - b) < eps }
配列周り
0-indexed / 1-indexed の混同
問題文が 1-indexed なのに、0-indexed で扱うための処理を途中で忘れてしまう。
対策
入力を受け取った直後に、すべて 0-indexed に変換してしまうのが安全です。
for (int i = 0; i < n; ++i) {
cin >> a[i];
--a[i]; // 入力直後に -1 をして、0-indexed に変換
}
配列外参照
- ループの条件文で
<と<=を間違える - サイズ $N + 1$ の配列が必要な場面で、サイズ $N$ の配列を確保してしまう
対策
- 具体的な小さい数で境界を考える
- 例: N = 3 のとき、配列の端に正しくアクセスできるかシミュレーションする
- 配列サイズを少し多めに確保する
- 例:
vector a(n + 10)
- 例:
添え字間違い
二次元配列などで a[i][j] とするべきところを、a[j][i] と書いてしまう。
対策
i, j といった抽象的な命名を避け、意味のある変数名を使いましょう。
例えば、グリッド問題なら、x, y や、row, column など、座標系や行列に対応した命名にすることで、混乱を防ぐことができます。
問題文の読み落とし・コーナーケース周り
出力形式の間違い
-
Yes/NoをYES/NOと出力してしまう - mod 998244353 の指定なのに、mod 1000000007 で計算してしまう
対策
固定の文字列や数値は、手入力を避け、問題文からコピペをするようにしましょう。
極端に小さいケース (N = 0, 1 など)
$N = 0$ や $N = 1$ のときに、ループが一度も回らなかったり、ゼロ除算が発生したりして、想定外の挙動になる。
対策
実装前に、最小の入力でも正しく動くか、を考える癖をつけましょう。
サンプルケースに最小ケースが無い場合は、手元で実際に試すといった、境界値チェックの習慣が有効です。
入出力周り
デバッグ用出力の消し忘れ
printf デバッグなどを消し忘れたまま提出してしまい、WA になる。
対策
printf デバッグ時には、標準エラー出力を利用しましょう。
多くのコンテストサイトでは、標準エラー出力はジャッジの対象外となるため、消し忘れても影響しません。
小数を指数表記のまま出力してしまう
小さい小数が 1e-07 のような形式で出力され、WA になる。
対策
小数を扱う際は、出力形式を固定するなど、言語ごとの指定方法で正しく出力されるように気を付けましょう。
おわりに
どれだけ経験を積んでもケアレスミスをゼロにすることは非常に難しいです。
大切なのは、注意力が足りなかったで終わらせずに、ミスが起きにくい仕組みを作ったり、バグに早く気付ける習慣を築いたりすることだと思います。
ミスをする度に、次にミスをしないためにはどうすればよいかを考えることで、デバッグの時間は短縮され、より本質的なアルゴリズムの考察に時間を割けるようになっていくはずです。
こうした考え方は、競技プログラミングだけでなく、普段のソフトウェア開発などでも、共通して役に立つはずです。