Zenn
😺

AHC040参加記：(C++)インタラクティブ問題を非インタラクティブにしてデバッグする

2024/12/16に公開
AtCoder
tech

この記事は2024年11月29日から12月9日まで行われていたHACK TO THE FUTURE 2025 （AtCoder Heuristic Contest 040）のユーザー解説記事(の一つ)です。ちなみに私plasmaは202位の結果でした。

解説記事ではありますが 解法は扱いません。 この記事では「インタラクティブ問題をデバッグするために何をしたか」について記述していきます。また基本的に C++に限定した話 ですので他の言語を使ってる方には役立たないかもしれません。C#では使えそう。

以下コード例は全てC++20のコードとなります。

要約

  1. ジャッジ環境をローカルで作ったよ
  2. ローカルでは標準入力をそのジャッジ環境に差し替えるようにしたよ
  3. 差し替えを自動で行うためにマクロを使ったよ

問題文のおさらい

問題文をざっくりおさらいしておくと以下の通りです。

  • グッズ(長方形)の個数Nと操作ターンTと標準偏差σがまず与えられる
  • 次にN行に渡って長方形の大きさの計測値w'とh'がそれぞれ与えられる
  • あなたは標準出力を使って長方形の詰め方を指示できる
    • まず配置する長方形の個数nを1行目に出力する、個数は0個でも構わない
    • 次に配置する長方形の番号p、回転の有無r、詰める方向d、詰める基準bをn行に渡って出力する
  • 標準出力に詰め方を指示すると標準入力にその詰め方による配置の横幅と縦幅の計測値W'とH'が与えられる
  • 詰め方の指示はちょうどT回行われなければならない(質問より)

またローカルテスタ用の入力には以下の追加の情報が与えられます。

  • N,T,σ及び各長方形の値が与えられたあとに「真の長方形の値」と「各ターンの計測誤差」が与えられる
    • まずN行に渡ってw,hが与えられる、i行目のw,hはi番目の長方形の真の横幅と縦幅である
    • 次にT行に渡ってdW,dHが与えられる、j行目のdW,dHはjターン目の計測誤差である

要するにローカルテスタ用の入力は以下の形式で与えられます。

N T σ
w'_0 h'_0
...
w'_(N-1) h'_(N-1)
w_0 h_0
...
w_(N-1) h_(N-1)
dW_0 dH_0
...
dW_(T-1) dH_(T-1)

インタラクティブ問題を非インタラクティブにする

インタラクティブ問題はAlgorithmでも出ますが、そのときに「デバッグが難しいなぁ」と思ってる人も少なくないと思います。 なら非インタラクティブな問題にすればいいじゃない というのが今回の発想です。この問題のインタラクティブな部分は以下の部分です。

  • n個の長方形の詰め方を標準出力で渡すよ
  • その詰め方の結果を標準入力で返すよ

この部分を関数化すると例えば以下のように書けます。

std::pair<int, int> print_result(std::vector<std::tuple<int, bool, char, int>> const& answer) {
    std::cout << answer.size() << std::endl;
    for (const auto& [p, r, d, b]: answer) {
        std::cout << p << " " << r << " " << d << " " << b << std::endl;
    }
    int W, H;
    std::cin >> W >> H;
    return {W, H};
}

一方でローカルテスタ入力を使った場合は標準入出力を介さずにこの部分の答えを出せます。その部分の処理を仮にlocal_testという関数にすれば以下のように書けます。

// for local test
std::vector<std::pair<int, int>> boxes;
std::vector<std::pair<int, int>> errors;
int turn = 0;
std::pair<int, int> local_test(std::vector<std::tuple<int, bool, char, int>> const& answer);

std::pair<int, int> local_result(std::vector<std::tuple<int, bool, char, int>> const& answer) {
    auto [W, H] = local_test(answer);
    auto [dW, dH] = errors.at(turn++);
    return {W + dW, H + dH};
}

local_testに関しては次のセクションで詳しく触れます。

ローカル環境ではいくらでもプリプロセッサマクロを定義できる(ジャッジサーバーではそれは定義されない)ので、例えば以下のように書くとローカルとジャッジサーバーで自動で使い分けしてくれます。

std::pair<int, int> get_score(std::vector<std::tuple<int, bool, char, int>> const& answer) {
#ifdef LOCAL_DEBUG
    return local_result(answer);
#else
    return print_result(answer);
#endif
}

これをこんな感じでコンパイルします

$ g++ main.cpp -std=c++20 -O3 -Wall -Wextra -DLOCAL_DEBUG -o main.o

「Makefileを書いておく」「Visual Studioのプロジェクト設定で指定しておく」などこの部分もまとめておくと便利です(私はWSL2+VSCode環境でやっているのでMakefileを書いています)。

ローカルのジャッジ環境を作る

ここまでは「ローカルのジャッジ環境があるとき」の話でした。ここからはローカルのジャッジ環境を作る話になります(つまり前セクションでのlocal_testを作る話)。

まず(ローカルテスタ用の)入力の形式を再掲します。

N T σ
w'_0 h'_0
...
w'_(N-1) h'_(N-1)
w_0 h_0
...
w_(N-1) h_(N-1)
dW_0 dH_0
...
dW_(T-1) dH_(T-1)

今回使うのはNとTとw_i,h_iの部分です。まずはこれらの生成方法の確認します。

  • N: 30以上100以下の整数を生成し、それをNとする
  • T: -1以上2以下の実数rを生成し、round(N*2^r)をTとする
  • w_i,h_i: 以下の2ステップで生成する
    • まず10^4以上5*10^4以下の整数を生成し、それをLとする
    • 各w_i,h_iに対しL以上10^5以下の整数を生成し割り当てる

よってNとTとw_i,h_iは以下の制約を満たします。

  • N: 30以上100以下の整数
  • T: round(N/2)以上4N以下の整数
  • w_i,h_i: 10^4以上10^5以下の整数

Nが100以下だそうなので何かしらで全探索できそうです。ここでは配置済みの長方形を全探索します。

配置済みの長方形をどうやって保存するかは議論が分かれそうですが、N個全ての長方形を並べる必要はない(つまり配置する長方形の番号が飛び飛びかもしれない)ので連想配列を使います。配置済みの長方形については「左上の座標」と「右下の座標」を保存します(回転したあとの長方形を保存することで回転したことの情報は消す)。ここまでをコードに書き下すと例えばこんなコードになります。

std::vector<std::pair<int, int>> boxes;

std::pair<int, int> local_test(std::vector<std::tuple<int, bool, char, int>> const& answer) {
    struct box_t {
        int xs, ys, xe, ye;
    };
    std::map<int, box_t> placed;
}

xsは左上のx座標、xeは右下のx座標です(ysとyeも同様)。またboxesは入力の情報をそのまま入れているものとします(つまりboxes[i].firstはw_iでboxes[i].secondはh_i)。

続いて各配置の情報を処理します。おさらいになりますが、answer[i]をp,r,d,bに分解したとき

  • pは配置する長方形の番号
  • rは回転の有無
  • dは長方形を詰める方向
  • bは基準となる長方形、もしくはX軸かY軸

となります。

d='U'のときを考えます。このときの配置方法を要約すると以下のようになります。

  1. r=1のとき長方形を回転させる
  2. 左端のx座標を配置済みのbの右端に合わせる、b=-1のときはx=0とする
  3. そのx座標で長方形を下から動かす、配置済みの長方形かX軸に接触したところで止める

1と2は簡単ですね。ここまでをコードにしてみます。

std::vector<std::pair<int, int>> boxes;

std::pair<int, int> local_test(std::vector<std::tuple<int, bool, char, int>> const& answer) {
    struct box_t {
        int xs, ys, xe, ye;
    };
    std::map<int, box_t> placed;

    for (const auto& [p, r, d, b]: answer) {
        assert(!placed.contains(p));
        if (d == 'U') {
            assert(b == -1 || placed.contains(b));
            int nxs = (b != -1 ? placed[b].xe : 0);
            int nxe = nxs + (r ? boxes[p].second : boxes[p].first);
        }
    }
}

新しいxsとxeということでnxsとnxeという名前にしています。

3で全探索の出番です。3は「nxs < x < nxeに含まれる配置済みの長方形を全て見て、yeの最大値を上端のy座標とする」と読み替えることができます。イメージとしては以下の感じ。

赤の範囲がnxs < x < nxeです。

xsからxeまでの長方形についてnxs < x < nxeに含まれる条件は以下のどちらかです。

  1. xs <= nxsの場合nxs < xe
  2. nxs <= xsの場合xs < nxe

図示すると以下の感じ。

これをこのままif文に書きます。該当する長方形がない場合はy=0に配置することに注意してください。配置するところまで一気に書いてしまいます。

std::vector<std::pair<int, int>> boxes;

std::pair<int, int> local_test(std::vector<std::tuple<int, bool, char, int>> const& answer) {
    struct box_t {
        int xs, ys, xe, ye;
    };
    std::map<int, box_t> placed;

    for (const auto& [p, r, d, b]: answer) {
        assert(!placed.contains(p));
        if (d == 'U') {
            assert(b == -1 || placed.contains(b));
            int nxs = (b != -1 ? placed[b].xe : 0);
            int nxe = nxs + (r ? boxes[p].second : boxes[p].first);
            int nys = 0;
            for (const auto& [i, box]: placed) {
                if ((box.xs <= nxs && nxs < box.xe) ||
                    (nxs <= box.xs && box.xs < nxe)) {
                    nys = std::max(nys, box.ye);
                }
            }
            int nye = nys + (r ? boxes[p].first : boxes[p].second);
            placed.emplace(i, box_t{nxs, nys, nxe, nye});
        }
    }
}

d='L'の場合もほぼ同じ理屈で書けるので省略します。

最後にxeとyeの最大値を取ってそれらを返すことで一連の処理が完了します。

std::vector<std::pair<int, int>> boxes;

std::pair<int, int> local_test(std::vector<std::tuple<int, bool, char, int>> const& answer) {
    struct box_t {
        int xs, ys, xe, ye;
    };
    std::map<int, box_t> placed;

    for (const auto& [p, r, d, b]: answer) {
        // 省略
    }

    int W = 0, H = 0;
    for (const auto& [i, box]: placed) {
        W = std::max(W, box.xe);
        H = std::max(H, box.ye);
    }
    return {W, H};
}

終わりに

この記事ではローカルテスタを作る方法、それを使って非インタラクティブ化する方法についてまとめました。特に非インタラクティブ化する方法は今後の長期Heuristicコンテストでも活用できると思います。Algorithmでも一応使えると思いますが多分書いてる時間がないですね…。

公式が配布しているローカルテスタを使えばいい話ではありますが、自前で組み込めるようにしておくと例えば「配置予想図と実際の配置を画像で出力して見比べる」などデバッグの幅が広がると思います。

実際のところコンテスト中はこんな綺麗な書き方をしていたわけではなく「入出力の部分をクラス化しよう」とか「座標圧縮して最大値の情報を保持すれば高速化できるのでは」とか試行錯誤してたのですが、この記事では詳しくは語らないということで。

というわけでこのへんで終わりとさせていただきます。ここまで読んでいただきありがとうございました。

Discussion