1WAがとれない……ときのランダムテストのすゝめ


本記事には以下の問題のネタバレが含まれます。

ABC267 D: Index × A(Not Continuous ver.)

atcoder.jp

背景

競プロで、コード書いて、サンプルも全て通して自信を持って提出!……したのですが、テストケースで1つだけWAしてしまう……競プロerなら誰でも経験したことがあると思います。
すぐにバグの箇所が見つかれば良いのですが、クサいところを直して再提出したもののまたWAを出して順位を大きく落としてしまったり、コンテスト中にバグ箇所がわからずそのまま終了、なんてこともあると思います。
この記事では、そういった場合に役立つ「ランダムテスト」について解説します。

TL;DR

  • サンプルは全部通るのにWAが出てしまう場合、ランダムな入力データでテストを行うことで落ちるテストケースを見つけられることがある
  • 手順は以下の通り
    • ブルートフォース解法コードと、ランダム入力生成用のコードを作成する
    • これらを使ってランダムな入力を生成し、ブルートフォース解法で出力を生成
    • 生成したランダムなテストケースで元のコードをテストする
  • メリット
    • 落とせるケースを機械的に発見できる
  • デメリット
    • ランダムケース生成・総当り解法の作成にそこそこ時間がかかる
    • 適用限界があるので、全てのバグに対して落とせるテストケースが見つかるわけではない

例題

今回は、以下の問題を例に解説します。 atcoder.jp

 i 番目 A_i まで見てそのうち j 個を選ぶような部分列のうち、答えに効いてくるのはその中で最もindex × Aの値が大きい部分列のみです。
なので、そのような部分列のindex × Aの値をメモしながらDPしていけば解くことができそうです。

ということで、その通り実装してみます。

Submission #35364750 - NEC Programming Contest 2022 (AtCoder Beginner Contest 267) (WA)

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using vl = vector<ll>; using vvl = vector<vector<ll>>;
#define rep(i, n) for (int i = 0; i < n; i++)
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; }

int main() {
    int n,m;
    cin >> n >> m;
    vl a(n);
    rep(i, n) cin >> a[i];
    vvl dp(n+1, vl(m+1, -1));
    dp[0][0] = 0;
    rep(i, n) rep(j, m+1) {
        if (dp[i][j] == -1) continue;
        chmax(dp[i+1][j], dp[i][j]);
        if (j != m) chmax(dp[i+1][j+1], dp[i][j] + a[i] * (j+1));
    }
    cout << dp[n][m] << endl;
}

上記のコードでサンプルは通っているのですが、提出してみると半分くらいWAしています。

ランダムテスト用コードの作成

この問題に対して、ランダムテストでバグ箇所を発見していきます。必要なものは以下の2つです。

  • 元の問題に対するブルートフォース(総当り)解法コード
  • ランダムケース作成用のコード

それぞれ作っていきます。

ブルートフォース(BF, 総当り)解法コード

「計算量を度外視して元の問題を解くためのコード」です。 O(N ^3) でも O(N!) でも O(2 ^N) でも、とりあえず解ければ何でも良いです。 今回の問題では部分列を全て列挙する自明な O(2 ^N N) 解法があるため、これを実装します。

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using vl = vector<ll>; using vvl = vector<vector<ll>>;
#define rep(i, n) for (int i = 0; i < n; i++)
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; }

int main() {
    int n,m;
    cin >> n >> m;
    vl a(n);
    rep(i, n) cin >> a[i];
    ll ans = -1e10;
    rep(i, 1 << n) {
        if (__popcount(i) != m) continue;
        int count = 1;
        ll cur = 0;
        rep(j, n) {
            if ((i >> j) & 1) {
                cur += count * a[j];
                count++;
            }
        }
        chmax(ans, cur);
    }
    cout << ans << endl;
}

ランダムケース作成用コード

次に、テストケースをランダムで生成するコードを作成します。 これは、問題文の入出力形式と、先ほど作ったBF解法の計算量を見ながら作成します。 今回は 2 ^Nくらいの解法なので 1 \le M \le N \le 10くらいで作成すると良さそうです。
また、 A_i の範囲については特に計算量の縛りは無いですが、あまり数が大きいと後で落とせるケースが見つかったあとのデバッグが大変なので、そこまで大きくない範囲( -10 \le A_i \le 10 くらい)にしておきます。

import random

n = random.randint(1, 10)
m = random.randint(1, n)
print(n, m)
a = [random.randint(-10, 10) for i in range(n)]
print(*a)

なお、自分はランダムケース作成用のコードはPythonで書いています。
これは、書いたものをコンパイルせずにさっと実行したいことと、順列の並べ替え(numpy)や木のテストケース作成(networkx)など、使えるパッケージが豊富なことが理由です。

ランダムテスト実施

2つのコードが書けたらランダムテストを実施します。これは各々の競プロ用のテスト環境などによるのでそれに合わせれば良いですが、例えば私の場合はonline-judge-toolを導入しているので、以下のようなフォルダ構成にしてコマンドを実行します。

cases/
└d/
  └test/
  └answer.cpp
  └answer_bf.cpp(総当り解法コード)
gen_rand.py(ランダムケース作成用コード)

ランダムケース作成(100個)

oj g/i -d "cases/d/test" "python gen_rand.py" 100

ランダムケースの出力作成

cd cases/d
g++ answer_bf.cpp
oj g/o -c "./a.out" -d "test"

これでランダムケースとそれに対する出力が生成されるため、あとは通常のサンプルと同じようにテストをすればOKです。私の場合はこれもonline judge toolで実施します。

oj t -d "cases/d/test" -c "./cases/d/a.out"

テスト結果の確認とエラー箇所の修正

テストをするとWAしているケースが見つかります。例えば、以下のようなケースで落ちていそうです。

[input]
1 1
-5

[output]
-1

[expected]
-5

-5だけの数列なのに-1が出力されるのはおかしいです。どこからこの-1が出てきているのか。。。と元のコードを眺めてみると、DP配列を-1で初期化してしまっていることが分かります。 したがって、初期化を-1ではなく-1e16などにすることで元の問題をACすることができます。 ACコード

10/4追記

oj g/i--hackオプションを使うことで、落とせるケースだけを簡単に見つけることができます。
上のフォルダ構成では、例えば以下のようなコマンドで実行します。

cd cases/d
g++ answer.cpp -o a.out
g++ answer_bf.cpp -o naive
cd ../../
oj g/i --hack-actual ./cases/d/a.out --hack-expected ./cases/d/naive "python gen_rand.py" 5

指定した個数分(今回は5個)、元のコードとBF解法の出力に差がある入力が出現するまでランダム生成を実行して、それをtest/フォルダ配下に保存してくれます。

適用限界

ランダムテストの実施により「ランダムなケースに対して一定の確率で発生しうるバグ」については発見できることがあります。
しかし、逆に言うとそのような性質を持たないバグについてはランダムテストで発見することはできません。具体的には例えば、

  • 制約の境界付近(N=0, N=1など)で発生するコーナーケースへの対応不足
  • 制約の大きいところで発生するオーバーフロー(計算量の関係で、大きい数字でのランダムテストができないため)

などは発見することができないため、これらはコードを良く見返したり、元のコードにデバッグ出力を埋め込んだりして発見する必要があります。

まとめ

ランダムテストを使うことでWAがずっと取れない…と悩むことは一定数減るかと思います。
ただし、上述の通り万能ではないので、ランダムテストで発見できないようなバグを埋め込んでしまった場合は地道なデバッグの経験が効いてきます。
ランダムテストできるから、と甘えずに精進しましょう……