自分の書いたプログラムが誤っていることが保証されているが、どのようなケースで誤っているのかがわからない場合のデバッグ法（アルゴリズム系で）
概要
通常のエンジニアリングで、「自分の書いたプログラムが誤っていることが保証されているが、どのようなケースで誤っているのかがわからない」というケースは多々あります。このようなケースは、基本的には再現性のないバグであることが多いです。並列プログラミングで競合資源の扱いを間違えたり、ロボティクスであれば電源が不安定だったり、温度だったり…
しかしアルゴリズムの問題では、このようなケースは考えにくいです。なぜなら、未定義動作を踏まない限りは再現性のないバグは埋めないからです。この記事では、ある入力集合に対して、誤ったプログラムを検出する方法について検討します。
背景
AGC 27Aで19WAを出したり、ARC 101Dで16WAを出したりして、何と言うか疲れてきているので。特にAGC 27Aではパフォ300とかいう意味不明な成績を出してしまったので。
誤答パターン
問題文を読み間違えている
解いている問題が異なれば、誤答します。特に英語の場合、初めに読んだ時に、重要な条件を列挙し、求めるべきものを明示的に日本語で書くべきでしょう。
解法が間違えている
解法が間違えれば、誤答します。解法の間違いにはいくつかのレベルがあります。抽象度の高いものが上です。
- 思い込んで正しいと仮定した貪欲が誤っている(AGC 27B)
- コーナーケースに対応していない
思い込んだ貪欲から逃れるのはかなり難しいです。そもそも貪欲を埋め込んだことに気づかないという可能性も高いです（AGC 27B）。これを踏んでからのリカバリは、手で頑張って実験したり、input generatorとbrutal solverの両方が必要になる可能性が高いです。手での実験は具体的な値というよりは、変数で考察するほうが望ましいケースも多々あります。具体的な数字だと考察結果を汎化しづらすぎます。
コーナーケースはどうしても踏むものなので、全てが同じとかnが最小など簡単にテストできるようなものは手で作って、ちゃんと確認しましょう。
解法は正しいが、時間が足りない
乱択や「出来る限りやる」解法では、評定が誤答であれ、実質時間切れであるようなケースが考えられます(ARC 101D, AGC 27C)。
「できる限りやる」解法では、収束条件を明示的に記述すべきです（AGC 27C）。そもそも、「出来る限りやる」の収束時間が非自明であるケースは考えられても、収束条件が非自明であるようなケースは非常に少ないです。収束条件をサボることによって、「解法が間違えている」「解答は正しいが時間が足りない」の切り分けを困難するのは損です。常に収束条件をチェックする戦略であれば、時間が足りないならばそのように評定を受けたほうが情報量が増すので、常に得をします。
乱択でWrong Answerを得る場合は、時間切れによるWAなのか解法のミスによるWAなのかの区別が付きません（ARC 101D）。乱択の収束について確信がある場合は、時間不足については度外視して考察すべきです。乱択の収束についての確信がない場合は、試しに投げて、適当な高速化をしたらとっとと方針自体を替えるべきです。この場合は、出力の自由度が低く誤答数が1個などでない限りは、きちんと考察をし直すべきです。そもそも、解法が思いつかないから乱択をする、というムーブそのものが冒涜的です。
未定義動作を踏んでいる
オーバーフローがあると誤答します。誤答前に、全てのリテラルにllをつけるなどすることで回避できます。また、誤答後には全てのリテラルにllがついているかを確認することで回避できます。また、最大ケースが自明である場合は、input generatorを書くことで回避できます。最大ケースが自明でない場合は、オーバーフローしそうな場所に対してdouble型で計算した計算結果がLLONG_MAXを超えていないかなどによってチェック可能です。(AGC 27A)
添字の範囲外参照があると誤答します。添字の範囲外参照は、長さnの配列でa[n]にアクセスするような添字計算ミスが考えられます。もしくは添字の書き間違えによって発生します。どちらも、誤答前にvalgrindでチェックすればよい話です。チェックのためには、
テストケースハック
AtCoderではassertを使ってテストケースを特定して、それに特化した答えを提出するということができます。特に1ケースだけミスなどの場合、これを行ってACをもぎとることができます。これを行いたい場合は、以下の2パターンに類別されると思います。
- ACをもぎとりたい場合。これは出力の自由度が小さい場合に限ります（YES/NOなど）。
- WAしているケースが大きいか小さいかだけを知りたい場合。これはオーバーフローしているのかコーナーケースでミスしているのかの切り分けに使えます。
戦略
まず意識すべきことは、input generatorやbrutal solverの構築は思っているよりコストが低いということです。これは急いで作問すると、簡単な問題ならば1時間で済むことからも自明です。1時間は10WAくらいでひっくり返ってしまうので、基本的にはこれらは脳死で作っても問題ないです。ここで注意すべきことは、input generatorは多少まともに作ったほうが良いということです。最大ケースを網羅しない雑なinput generatorでは、最大ケースでオーバーフローするような簡単に気づけるバグを検出できません（AGC 27A）。したがって、多少ロバストに作ることを意識すべきです（少なくとも、n, amax最大をチェックできるように）。
予防
- 問題概要を日本語でまとめる
- リテラルには必ずllをつける
- サンプルは必ずvalgrindでテストする
- 考えられる小さいコーナーケースは必ずテストする
- 出力にassertを入れる（例: 答えは0以上n以下であるはずである、など）
- 解法が思いつかないから乱択をする、というムーブそのものが冒涜的なので、避ける（ロボット屋なのでやりがち）
- 時間切れ時にちゃんと時間切れと評定を出すプログラムを書く
誤答後
- おちつく。
- 誤答が1ケースなどであっても、すぐにテストケース特定に走らない。これをやって良いのは、
- 出力がYES/NOのみであり、特定が容易である場合
- テストケースの傾向をつかむためのassertくらいは、1回くらい投げてもいい（nがnmax/2よりも大きいかどうか？とか）
- 解法が乱択想定と思われないならば、多少の定数倍高速化をして投げて、すぐに他の解法を探す。
- 定数倍高速化で頑張ったり、乱択でガチャするのは、WAを大量に出すので、そのデメリットをきちんと検討すること
- リテラルにllがついているかを確認、オーバーフローを疑う
- テストケースを手で書いていくつか試す
- ある程度ロバストなinput generatorを書く
- input generatorで未定義動作を踏まないかを確認する
- brutal solverが書けるならば書いて比較し、答えを違うようなケースを探す
- brutal solverが書けないならば、具体的な数字や変数を交えたり、極端なケースで、仮定した貪欲的な操作が誤っていないかを確認する
それでもダメなら
- 他の問題に移る
