本記事は、競プロ Advent Calendar 2021の12/7の記事です。（12/18に遅刻投稿しました。）

2022-08-21 更新: シェルスクリプトの実行コマンドを追記
2023-01-28 更新: xargsコマンドの注意点を追記

こんにちは、shu8Creamです。
この記事では、AtCoder Heuristic Contest（以下AHC）に参加したい人・参加し始めた人向けに、大量テストケースの試し方を解説します。
なお、僕がAHCで使用している言語はC++であるため、他言語を使っている場合参考にすることが難しい場合がありますのでご了承ください。

なぜ大量テストケースを実行したいのか
入力の受け取り方
出力の仕方
- もっと便利にするために
全テストケースの一括実行
おわりに

なぜ大量テストケースを実行したいのか

AHCでは、ツールの中に50~100個のテストケースが与えられることが多いです。スコアの改善度合いは、多くの場合、テストケースを実行して平均を取ってみなければ真に改善されているか判断がつきません。（50個のテストケースでは足りない場合がほとんどかも）
そこで重要なのが大量テストケースの実行です。

入力の受け取り方

まずは入力を受け取りましょう。 AHCは普段のアルゴリズムのコンテストとは違い、入力がとても多いため、コピペでターミナルなどに貼り付けて実行すると、前の実行結果が遥か上に消えていってしまいます。この状況をファイル入力する方法で改善していきます。

ツールをローカル環境にダウンロード（図１）
ファイルを解凍し、扱いやすい階層に配置する（図２）
tools/in/ ←この階層の下にテストケースがたくさん入っているのでこれを元に実行時に入力を行う（図２）
./a.out<tools/in/0000.txt のように実行

これだけで大量の入力をわざわざコピペする必要がなくなります。 tools/in/0000.txtの赤字部分を変更すればさまざまなテストケースが試すことができます。「ツールは使わないし必要ない」と思ってダウンロードしていなかった方もテストケースが入っているのでダウンロードしてみましょう。 Webビジュアライザからテストケースのみをダウンロードすることもできます。

出力の仕方

C++の場合、コンパイル後に実行ファイルが生成され、それを実行します。実行時に以下のようにするだけで好きなファイルに書き込みができます。

./a.out < ./in/0000.txt > ./out/0000.txt

厳密に言うと、このコマンドでは標準出力をoutディレクトリ配下の0000.txtというファイルに書き込むことができます。

別の方法として、コード上でどのようにファイル出力するかを記載する方法があります。どのようにするかコードを見ながら解説します。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(n); i++)

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

// ①僕は元々出力デバッグ用に使っていました。
#ifdef _DEBUG
#define debug(...) debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

const int N = 400;
const int M = 1995;

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

// ②ファイル出力のためのお作法
    #ifdef _DEBUG
    FILE *fp;
    fp = fopen("./tools/out/0000.txt", "w");
    #endif

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    Input();
    
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

//③実際にファイルに書き込むための部分
    #ifdef _DEBUG
    if(isUse[i]){
        fprintf(fp, "%d\n", 1);
        connected[i] = 1;
    }else{
        fprintf(fp, "%d\n", 0);
        connected[i] = 0;
    }
    #else
    if(isUse[i]){
        cout << 1 << endl;
        connected[i] = 1;
    }else{
        cout << 0 << endl;
        connected[i] = 0;
    }
    #endif

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

//④これもファイル出力のためのお作法
    #ifdef _DEBUG
    fclose(fp);
    #endif
}

#ifdef ここに好きな名前

上記のような形で宣言して、#else, #endifを駆使して分岐を書くことによってコンパイルするものとしないものを選ぶことができます。僕の場合、この機能を利用することで、

g++ -std=c++17 -D_DEBUG

赤字部分をつけるかどうかで、ファイル出力するしないを自在に選ぶことができます。僕は出力先を②のように指定しています。toolsフォルダの中にoutフォルダを作成して、そこにテストケースごとに出力して見やすくしています。

もっと便利にするために

ファイル出力が自由にできるようになりましたが、コンパイルコマンドの記述量が増えてしまいました。この記述を楽にするために、alias機能を利用します。ターミナルでは、特定の記述に対して呼び出し方を決めることで独自のショートカットを作ることができます。僕が使っているものだと、

alias a='./a.out'
alias g='g++ -std=c++17 -O3'
alias gd='g++ -std=c++17 -D_DEBUG'

alias gs='git status'

個人的にはgit系はもっと登録していますが、競プロの用途だと上3つを多く使用しています。 AtCoderのYouTube公式解説放送でsnukeさんが利用していたものを参考にしていたりします。

// 普通はこうしなくちゃいけない
g++ -std=c++17 -D_DEBUG ver1.cpp

// こっちの方が楽チン
gd ver1.cpp

実行がこれで随分と楽になります。

全テストケースの一括実行

ファイル書き込みできるようになったので、いよいよ複数テストケースを一気に実行します。これを実現するため、僕は下記のようなシェルスクリプトを書いています。

#!/bin/bash
## ファイル名：exec.sh

S=$(printf "%04d\n" "${1}")
## N,Kを入力ファイルから取ってきてスコアファイルの中に記録
awk 'NR==1' in/${S}.txt >&2 > score/${S}.txt
./a.out < in/${S}.txt > out/${S}.txt 2>> score/${S}.txt

# 実行コマンド
seq 0 99 | xargs -P4 -I{} ./exec.sh {} # 0~99の入力ファイルを実行

これはAHC013参加後に作ったもので、参加中も似たようなものをPythonで書いて計測をしていました。シェルファイルを作って、実行コマンドをターミナルなどで叩くと実行できます。実行コマンドは並列実行できるようにしていますが、並列化することでスコアに影響が出る可能性があるため検証が必要です。並列化の性能は使用PCの環境に依存するため、確かめてから使用するか、1ケースずつ実行する（-P4を外す）と良いです。このシェルファイルでは実行結果（実際に採点される出力）は標準出力へ、内部で計算しているスコアや実行時間、焼きなまし時の試行回数などは標準エラーへ出力しています。僕はscoreディレクトリ配下に各テストケースごとの結果ファイルが溜まるようにし、これを入力に平均スコアを算出しています。こうすることで、AHC013のようにN,Kが可変の場合どのケースで点が取れているのか、取れていないのか偏りを見る事ができます。
全テストケースのスコアを一覧で見ると、ある場合でのスコアの悪さに気づくことができ、何がボトルネックになっているか考察の助けになるでしょう。

※注意※
xargsコマンドを使用する場合、Permission deniedの類のエラーが出ることがあり、chmodコマンドでexec.shに実行権限を付与する必要があります。

おわりに

今回はヒューリスティックコンテストで大量テストケースを一気に実行する方法を紹介しました。
僕がAHCに参加し出した時、入出力、改善度合いの評価にとても苦労しまして、多くの初心者が苦労するポイントではないかと思い、今回記事としてまとめてみました。
この記事を参考に、コンテストへの参加者が少しでも増え、強くなる人が増えれば嬉しく思います。
最後まで読んでいただきありがとうございました。

shu8Creamのブログ

競プロブログ。

ヒューリスティックコンテストで大量テストケースを一気に実行したい！