shuのブログ

好きな時に好きなこと書くブログです。

ヒューリスティック初心者の取り組み方

本記事は、競プロ Advent Calendar 2021の12月7日の記事です。 (12/18日に遅れて投稿されています。)

競プロ Advent Calendar 2021 - Adventar

こんにちは、shu8Creamです。

この記事は、AtCoderヒューリスティックコンテストに参加したい人、参加し始めた初心者向けに テストケースの試し方・大量の入力に対しての大量の出力をどのように扱えば良いのかを 僕の実際行っている方法をベースに解説しようと思います。

なお、僕がヒューリスティックコンテストで使用している言語はC++であるため、 他言語を使っている場合参考にならないことがあるのでご了承ください。 また、かなり基礎的な部分も含んでいます。

始めたばかりのときに困ったこと

僕がヒューリスティックコンテストに初めて参加した時、入出力どれくらい改善したかどうかを試すのにとても苦労しました。 初心者が苦労しがちなポイントではないかと思い、今回記事としてまとめることにしました。 私もまだヒューリスティックに挑む形式を確立しているわけではないので、この記事を通してさらに学びがあれば嬉しいと思っています。

入力の受け取り方

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

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

f:id:shu8Cream:20211218180512p:plain:w400
図1
f:id:shu8Cream:20211218181353p:plain:w300
図2

これだけで大量の入力をわざわざコピペする必要がなくなります。 tools/in/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'

AtCoderYouTube公式解説放送でもsnukeさんが利用していたりします。 git系はもっと登録していたりしますが、競プロ用だと上3つを使っています。

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

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

実行がこれで随分と楽になると思います。

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

AtCoderヒューリスティックコンテストでは、ツールの中に50個のテストケースが与えられることが多いです。 スコアの改善度合いは、多くの場合前テストケースを実行して平均を取ってみなければ真に改善されているか 判断がつかない場合が多いです。(50個のテストケースでも足りない場合もあるとか。。。)

そこで重要なのがテストケースの全実行でこれを簡単に実行するため、僕は下のようなシェルスクリプトを書いて実行していることが多いです。

#!/bin/bash
for var in {0..49}
do
    S=$(printf "%04d\n" "${var}")
    command="./a.out<./tools/in/${S}.txt "
    eval ${command}
done

コマンド実行をシェルスクリプトで記載してループを回すだけの簡単なものですが、これで各テストケースのスコアを吐き出させて平均を見ることでスコアの改善度合いを測ることができます。全テストケースのスコアを一覧で見ると、あるテストケースで極端に低い値が出ていてそこに何らかのボトルネックがあることがわかったりすることもあります。

正直ここのテストケースの全実行方法は、まだまだ改善の余地があると思っています。

おわりに

今回紹介したものが、僕がヒューリスティックコンテストに取り組む上で身につけてきたテクニックです。 ヒューリスティックでは、問題自体のぱっと見のとっつきづらさ以外にも初心者には上記に書いたような様々な課題があると思っています。 この記事を参考にして、課題を解消してヒューリスティックコンテストへの参加者が増えれば嬉しく思います。

ここまで読んでいただきありがとうございました。