初心者向けバグ取り

「バグったたすけてー」と言っている初心者の人のコードを見たとします。 バグを見つけてあげるのは（多くの場合）簡単ですが、それを伝えただけでは成長につながらないかなぁとも思います。

「こういうところをこうやって確認したよ」「そしたらこうなったので見つかったよ」みたいなことを教えてあげるといいと思ったのですが、毎回やると面倒なので、記事にまとめます。 あくまでえびちゃんの方法なので、他の人は違うことをしているかもしれません。

最近あまり他人のデバッグをしていないので、記憶と妄想で書いているところはあります。 追記したいことが発生し次第、追記しようと思います。

---

記事の本編では C++ を仮定します。

Python の人向けデバッグ：

• numpy か何かの演算でオーバーフローしている
• 整数の切り捨て除算を浮動小数点数を介していて誤差が生じている
• その他、あきらめる

他人のコードのデバッグをするときは、まず #define int long long をしているかどうかを確認しておきましょう。 オーバーフローしていそうな箇所を見つけてから「実は long long でした」というのはかなり嫌な気分になるので。

前提

一応 verdict ごとに分けて考えますが、「配列外参照（未定義動作）の結果、TLE が発生した」とかはありえる話なので、「TLE なんだから配列外参照とかではないはず」のような決めつけはいけないですね。

あと心構えの話なのですが、「1 ケース WA だから少し変えるだけでいいはず」のような考え方はやめた方がいいと思います。全くの嘘解法だった場合に気づくのが遅れる原因なので。 逆に言えば「全ケース WA だから少し変えても通らないはず」というのもよくないです*1。

とりあえず、まず、コンパイラの警告を見ます。「初期化されてないよ」とか「関数の返り値がないよ」などは、そこが本質的な場合もあるので。 そこが問題なければ、verdict に従い、典型的なミスを探していきます。

確認することたち

TLE

多くの場合は、計算量の見積もりを間違っているんだと思います。

_GLIBCXX_DEBUG

これはあくまでデバッグ用の機能であり、関数によってはオーダーが悪化することもあるので、（わかっていてそうする場合を除いて）提出コードで書くのは避けましょう。 なんのことかわからない人へ：

rsk0315.hatenablog.com

コンテナの無駄なコピー

関数に vector などのコンテナを渡すとき、以下のように書くと、関数を呼び出すたびにコピー（サイズに対して線形時間）が発生します。

int f(vector<int> v) { ... }

関数の中で線形時間の操作をしているなら定数倍の違いしかないので問題がないことは多いです*2。 そうでない場合（一部の要素だけを見て終わる場合など）は、オーダーが悪化してしまうので、以下のように直しましょう。

int f(vector<int>& v) { ... }

v を書き換えないのなら、次のように書き換えてもいいです。

int f(vector<int> const& v) { ... }

イテレータの操作

set<int> s;
lower_bound(s.begin(), s.end(), x);

これは線形時間なんですね〜。

rsk0315.hatenablog.com

WA

mod が間違っている

1000000007 なのに 998244353 を使っているとか、998244353 を書き間違っているとかです。 他のミスに比べてすぐ確認できるはずなので、すぐします。

毎回あまりを計算するたびに %= 998244353 とか書いている人がいたらやめましょうね（確認が面倒なので）。 適当に定数を宣言して、それを使いましょう。

const int mod = 998244353;

大文字小文字が間違っている

これもすぐですね。 YES と Yes とか、そういうやつです。 特に、場合分けが複雑で、複数回書かされる場合は注意が必要です。

オーバーフロー

掛け算しているところを一通り確かめます。

ある数で割ったあまりを求めるとき、a * b * c % mod だと、a * b * c の時点でオーバーフローするとだめです。 また、c がとても大きいときは　a * b % mod * (c % mod) % mod のようにする場合があるでしょう。制約を見ながらちゃんと考えます。

足し算でオーバーフローする問題はあまりない気もしますが、これも気をつけましょう。

精度

浮動小数点数は無限精度ではないので、期待通りに動かないことが多いです。 悪いのは浮動小数点数ちゃんではなくて、変な期待をする人です*3。 たとえば、double で \(2^{53}+1\) などを計算してみましょう。偶数が出力されてびっくりです。

精度が足りなそうなのに過信したようなコードが書かれていたら、そこを注意深く見ます。 該当しそうな問題としては、ルートのやつ とか、掛け算のやつ とかがありますね。

off-by-one エラー

添字などが +1 や -1 の書き忘れや不要な書き足しなどで間違いになっているものの総称です。 極端なケース（サイズが最小の場合、添字が最大の場合など）を考えると、おかしいときは気づきやすいことが多いです。

こういう記事もあります： rsk0315.hatenablog.com

変数名の間違い

xa xb ya yb みたいなのがたくさん出てきてあれこれするコードは、使い間違っていても気づくのが大変です。 出現回数が同じであるべき変数名の出現回数が違ったら「おかしいな」とは思いますが、そうでないと面倒です。いやですね。

謎貪欲などの嘘考察

自分では気づきにくいことが多いです。 あとで紹介する方法と併せて、小さいケースで手で確認すると、「たしかにこの貪欲はおかしいね」となれる場合が多いです。

RE

配列外参照

配列サイズはちゃんと確認しましょう。 処理が複雑な場合は、「アクセスすることになる添字に対してサイズは十分か？」みたいなことを考える必要があると思います。

ゼロ除算

除算のたびに、割る数がゼロではないか確かめても十分なくらいです。数学でそうするのと同様です。 割る数が x-1 のような場合、x が 1 にならないか確かめるとかですね。 これ とかです。

それ以外

あんまりなさそうです。 ロジックが間違っていて、再帰が無限に発生しているとかはあるかも？

だめだった場合

C++ の仕様の勘違いで間違っているとかはあるかもしれません。 暇だったら これ とか これ とかを見てがんばればいいと思うんですが、そうも言ってられない場合の方針を示します。

愚直解を書きます。 ここで愚直解が正しく書けないとどうしようもないのですが、そこはがんばってほしいです。

ここで言う愚直解というのは、たとえば、「制約が \(n \le 10\) だった場合に書くコード」のようなものを考えてください。 bit 全探索をするとか、8 重ループを書くとか、全順列を next_permutation で試すとか、いくらでもやりようはあるはずです。

...というのを書きます*4。

次に、テストケースを自分で生成するコードを書きます。 乱数を発生させるのが大変だったりしますが、手軽には、以下のようなものが考えられます。

#include <iostream>
#include <random>

std::random_device rd;
std::mt19937 rng(rd());

int randint(int lo, int hi) {
  // lo 以上 hi 以下の乱数を返す
  return std::uniform_int_distribution<int>(lo, hi)(rng);
}

int main() {
  // 10 以上 20 以下の乱数を出力する
  std::cout << randint(10, 20) << '\n';
}

こういうのを駆使しながら、該当する問題のフォーマットに沿ったケースを生成するコードを書きましょう。

あとは、これを使って、元々の自分の書いたコードの出力と不一致になるケースを探します。

online-judge-tools を知っていますか？ それを導入するのが一番手っ取り早いはずです。 pip3 が使えるとして、以下のコマンドを実行しましょう。

$ pip3 install --user online-judge-tools

online-judge-tools.readthedocs.io

たとえば、元々の解法の実行ファイルが ./X、愚直が ./X-naive、ケースの生成器が ./X-generator だとします。 以下のコマンドを実行すると、不一致になるケースが見つかるまで勝手にがんばってくれます。

$ oj g/i -c ./X-naive --hack ./X ./X-generator

見つかると、そのケース（入力と、想定される出力、それから誤った自分の出力）が出力されるので、それを見ながら、手や頭を使って考えます。 「どう考えてもおかしい考察じゃん」とか、「手では合ってるんだから実装がおかしいはずじゃん」とか気づくはずです。 後者なら、適宜 print デバッグ*5などをするなりして、バグを探してください。

人によっては（chokudai さんとかね）、解法のコードにテストを直接書き込んだりする方法を紹介しています が、えびちゃん的にはあまりおすすめしないです。 テスト部分の消し忘れで入力を読み間違えたとか、愚直の方が実行されるまま提出してしまったとか、そういうミスが懸念されるためです。 というかミスをしないにしても、「テストがうまくいった」の後の「提出用に書き直す」の手間を避けたいです。

前述の方法であれば、./X はテスト用と提出用で書き換える必要がないので、提出が楽でよいです。 提出するのはテストに通ったコードそのままなので、書き直しミスとかを心配する必要もありません。

それでもだめだったら

そんなことある？ 自分でコーナーケースっぽいものを考えて、愚直解と比較したらいいんじゃないですか？

小さいケースでは発生しないバグとかもあるとは思います。えーーー、うーん、だったらもう少し愚直を改良して大きめのケースで試せばいいんじゃないですか？ 大きいケースだとどう間違っているか調べるのが大変だったりしますが。

あーあと、「こんなの愚直の書きようある？ どうしようもなくない？」というのは、どうしようもなさそうです。あきらめて。 構築系の問題とかはある程度大変かもしれませんね。

おわり

AC おめでとう。

ねこ

たぶん、えびちゃん自身は、off-by-one と嘘考察以外だと、上記に当てはまるコードはそもそも最初から書かない気がします。 嘘考察の種類は人によってある程度違うと思うので、「自分が考察の際に漏らしやすいこと一覧」みたいなのをまとめておくといいんじゃないですか？ たぶん自分で書くことにも意味はあると思います。

そういえば、ICPC に初めて出たときは、ライブラリに「やりがちなミス一覧」みたいなのを載せてた気がします。

*1:構築で、出力の行数を書き忘れていたり、Yes を書き忘れていたりなど。サンプルも落ちるのはおかしいということで見直すべきですね。

*2:だとしても、わざわざ定数倍の重い書き方をするメリットは、多くの場合無いはずですが。

*3:思想が出ています。

*4:コンテスト後であれば、他人の適当な AC コードを持ってくるとかも考えられますが、訓練だと思って自分で書いてください。自分で書くのに慣れていればコンテスト中に困っても対応できるので。

*5:変数を適当な箇所で出力して、自分の想定通りか確認する方法です。