ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

競プロでWAが出たときのランダム入力データ生成入門

プログラミング 競技プログラミング

概要

競技プログラミングで提出コードがWAになったとき、実際に不正解となるような入力データを入手できると役に立つ場合があります。ただ多くのコンテストサイトでは、コンテスト中には入力データを見ることはできません。

そのような時に、小さめの入力データを乱数で大量生成して、提出コードと愚直解法の結果を突き合わせ、答えが一致しないものを探すという方法があります。もちろんそのようなデータを確実に得られる保証はありませんが、もし見つかればデバッグの大きな助けになります。

今回の記事はその手順を紹介します。また、生成コードの例としてC++とPythonを扱います。

手順1：愚直解法コード作成

まずは問題に対する愚直解法のコードを書きます。小さな入力データで回すので、 O(N^{3}) だろうと O(2^{N}) だろうと気にせず書きましょう。これがバグっていると破綻するので計算量よりも正しさ優先です。

C++等の場合はコンパイル時に提出コードのものと別の実行ファイル名になるようにしましょう。g++であれば -o オプションで実行ファイル名を変えられます。

手順2：乱数データ生成コード作成

乱数で入力データを生成するコードを書きます。

データサイズ・各データの値ともになるべく小さいものが見つかるほどデバッグしやすいです。私はまずは数列であれば4～10要素程度、値は20以下くらいで作っています。見つからなければ後で増やせば良いです。

乱数の作り方は言語によって異なります。以下の制約に従う入力データを標準出力に出力する、C++とPythonの実装例を示します。

生成する入力データ

制約：

  • 4 \le N \le 10
  • 1 \le a_{i} \le 20

入力形式：

N
a1 a2 ... aN

C++コード

#include <bits/stdc++.h>
using namespace std;

int main(){
    random_device seed_gen;
    mt19937_64 rnd(seed_gen());
    
    uniform_int_distribution<int> dist_N(4, 10), dist_A(1, 20);
    int N = dist_N(rnd);
    vector<int> A(N);
    for(int i=0; i<N; i++) A[i] = dist_A(rnd);

    cout << N << endl;
    for(int i=0; i<N; i++) cout << A[i] << " \n"[i==N-1];
    return 0;
}

乱数生成器まわりのコードの書き方が少し面倒なのでコピペで使ってください。ある範囲の整数をランダムに得る時は剰余演算などを使っても良いですが、明示的に範囲を指定できる uniform_int_distribution のほうがミスが少ないと思います。

" \n"[i==N-1] という書き方について少し補足しておくと、これは i==N-1 のときに改行、そうでないときにスペースとなり、結果的に数列のスペース区切り＋改行が出力されます。仕組みとしては、" \n" はスペースと改行を並べた2文字の文字列です（改行がコード上2文字なので分かりづらいですね…）。i==N-1 は true または false になるので、整数として解釈すると 1 または 0 になります。これらがインデックスとして解釈され改行またはスペースが取り出されます。

注意：Windows/MinGW環境の場合

注意点ですが、WindowsのMinGWでC++環境を作っている場合、このコードでは毎回同じ乱数になってしまうという問題があります。本来であれば random_device が実行ごとに異なる乱数シードを与えてくれるのですが、MinGWではこのシードが毎回同じになってしまうためです。

対処法ですが、今回の用途では厳密な乱雑さは必要なく、実行ごとに異なるシードになってくれればそれでいいので、現在時刻をミリ秒単位で取ってきて与えるという方法があります。先程のコードのmain先頭2行を以下に置き換えればよいです。

int64_t seed = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count();
mt19937_64 rnd(seed);

Pythonコード

import random
N = random.randint(4, 10)
A = [random.randint(1, 20) for i in range(N)]
print(N)
print(*A)

文字列の生成について

例えば英小文字をランダムに生成したい場合は、C++であれば0～25の乱数を作り 'a' に足すだけでOKです。Pythonの場合は以下のように書くとランダムな英小文字を1つ選べます。

import random
import string
c = random.choice(string.ascii_lowercase)

手順3：ひたすら回すスクリプト作成

愚直解法コードと乱数データ生成コードができたら、以下の処理を行うスクリプトを書きます。

  1. 入力データを生成する
  2. 提出コードと愚直コードをそれぞれ実行する
  3. 出力を比較し、異なっていれば終了する。同じであれば1に戻る。

このときの入力データですが、私は毎回ファイルに出力しています。どんな入力データが出ているか視覚的に分かるのと、スクリプトが止まった時に確実に入力データが保存されているので。その分毎回のファイル書き込みのぶん時間ロスがあるかもしれません。

RubyやPythonなどを使うほうが色々楽だと思いますが、実行環境がなくてもいいように一応シェルスクリプトとPowerShellの例を示しておきます（実行方法は調べてね）。各実行コマンドは使っている言語やファイル名に応じて変更してください。

※私自身は普段はRubyでやっているので、これらのスクリプトはこの記事用に急ごしらえしました。特にシェルスクリプトはWSLのbashでしか動作確認していないので、動かないところがあれば教えてください。

シェルスクリプト（Mac, Linuxなど）

while true; do
    ./make_random.out > input.txt
    ans1=$(./a.out < input.txt)
    ans2=$(./guchoku.out < input.txt)
    if [ $ans1 != $ans2 ]; then
        echo "Wrong Answer"
        echo $ans1
        echo $ans2
        exit
    fi
done

PowerShell（Windows）

while(1){
    ./make_random.exe > input.txt
    $ans1 = (Get-Content input.txt | ./a.exe)
    $ans2 = (Get-Content input.txt | ./guchoku.exe)
    if($ans1 -ne $ans2){
        Write-Host "Wrong Answer"
        Write-Host $ans1
        Write-Host $ans2
        exit
    }
}

これをしばらく回してみて、不正解データが見つかったらラッキーです。手計算したりコードの途中経過を細かく追ってみましょう。見つからなかったら、入力データの生成方法を変えてみるか潔く別の方法を取りましょう。

特殊な入力制約

制約に特殊な条件がある場合の作り方です。

数列の各要素が相異なる

既に出現したデータをsetなどで持っておいて、かぶったデータは捨てます。

順列も同じ考え方で作ることができます。コンプガチャみたいになるので要素数が多いと余計に時間が掛かりますが、小さいデータなら問題ないでしょう。

グラフが木である

Union-Findを使いましょう。頂点2つをランダムに選んだ後、その2点がまだ連結でないなら辺として採用します。クラスカル法のイメージです。

直線やウニなどの偏ったグラフは生成されにくくなります。

無向グラフが連結である

Union-Findを使って全頂点が連結になるまで辺を追加します。

頂点 s から頂点 t に到達可能である

無向グラフならUnion-Find。有向グラフなら辺を足すたびにDFSなどで確認しましょう。

グラフに自己ループや多重辺がない

頂点2つをランダムに選んだ後、その2点が異なっていることと同じ辺が既に出現していないことを確認してから辺を足します。ランダムに作っちゃうと意外と忘れがちな制約なので注意。

問題の性質による注意点

答えが偏る問題

Yes/Noやゲームの勝ち負けを判定する問題で、入力データをランダムに作ると高確率で答えがどちらか片方になってしまう…ということがあります。例えば「ある操作の繰り返しで数列 A を数列 B に一致させられるか判定せよ」という問題で、その一致条件が厳しい場合には、 A, B を独立に作るとほとんどNoになってしまいます。

こういう場合は、必ず答えがYes（起こりにくい方）になる入力を作れないか考えてみましょう。つまり先に A をランダムに作ってから、何回かランダムな操作を施して B を作れば、必ず答えはYesになるはずです。

ただ、このような問題は愚直解が書きにくい傾向があります。この生成方法であれば答えがYesと分かっているので「Yesケースだけを生成してNoと誤判定されるまで回す」ことで片側のミスは探せます。しかし逆にNoケースをYesと誤判定するミスは探せません。なかなか難しいですね。

特殊な出力の問題

構築問題の場合は出力を単純比較してもダメです。この場合は構築結果が問題の要求に合っているかを直接ジャッジするコードを書きましょう。

また小数出力で許容誤差が設定されている場合も単純比較はできません。出力結果を数値として受け取って誤差評価をすれば判定できますが、私自身は使ったことがありません。

さいごに

ランダム入力データの生成と愚直解法との突き合わせについて、色々書いてみました。

この方法は万能ではありませんが、慣れればコンテスト中でも短時間で準備できるようになります。私個人の感覚としては、コードや考察を見直している裏で回しておいて、もし見つかったら儲けものというくらいです。

そしてこの方法が取れるかどうかは問題の性質にかなり依存します。愚直解を書くのがそもそも難しかったり、本文中に書いたように特殊な入出力がある場合にはこの方法は向いていません。

この準備作業に手間取ってしまうと本末転倒なので、実戦投入する前にちょっと練習しておいたほうが良いかもしれません。あと、もちろんランダム生成だけに頼らず、偏ったケースを自分で色々作って試してみるという作業も大事です。

まずは非コンテスト時でWAの原因が分からず困ったときなどに、よかったら試してみてください。