競プロで出がちなREの原因をまとめる

この記事はISer Advent Calendar 2020の15日目として書かれました。 14日目の記事はfushiguさんの tf-idfについて - fushigu’s blog でした。

自分用に書いていたメモをブログのネタにしようと思います。記事の特性上、問題のネタバレを含みます。

sh_mugというアカウント名で競プロをやっています。 (執筆時のレート: 1965)

使用言語はC++です。

RE (Runtime Error)
プログラムの実行中にエラーが発生しました。コンパイル時に検知できなかったエラーがあります.スタックオーバーフロー、ゼロ除算などが原因です.
(引用元: Glossary - AtCoder Beginner Contest 185)

自分が2020年に出した全32個のREのうち、気になったものをタイプ別に分類していきます。

配列の範囲外にアクセスすると、セグメンテーション違反でRuntime Errorが出がちです。コードテストでは、終了コードが139になります。

for (int i = 0; i < h; ++i) { ...   // OK. これを書きたかった
for (int i = 0; i < n; ++i) { ...   // NG. hとnが似ていて気付きづらい

if (i < N && a[i] == hoge) { ...    // OK. i>=Nのときa[i]にアクセスされない
if (a[i] == hoge && i < N) { ...    // NG. i>=NでREする

さすがにやらないだろうと思っていたが、やっていた。終了コードは136です。

原因　自作の約数列挙関数と、桁和計算関数の双方が原因になっている。詳しく説明すると、
- -1の約数を列挙→ 0以下が入力になることを想定しておらず、-1の約数列として{1, -1} が返される
- -1 + 1 = 0進数として桁和を計算→桁シフト時に0除算が発生
対策　まず除算、剰余演算において除数が0になる場合がないか確認する。あるいは、あらかじめ十分に処理の場合分けをする。

bool b; ...
std::sort(a.begin(), a.end(), [&](int x, int y){return b^(x<y);});    // NG
// b==trueのときx==yでcomp(x, y) == comp(y, x) == trueになってしまう