AHC015 参加記 - eijirouの競プロ参加記

トヨタ自動車プログラミングコンテスト2022（AtCoder Heuristic Contest 015）お疲れ様でした。

161,011,437 点で優勝しました！

問題概要

$10 \times 10$ マスの空の箱があります。そこに 100個のキャンディーを1つずつ追加します。追加する場所は空きマスの中から無作為に選ばれます。事前に $t$ 番目に受け取るキャンディーの種類が $f_t$ $(1 \leq f_t \leq 3)$ であることがわかっています。

1つのキャンディーが追加される度に、箱を前後左右のいずれかの方向に傾けます。箱を傾けると、各キャンディーは箱の壁や他のキャンディーとぶつかるまで移動します。

100個のキャンディーを追加し終えたときに、同じ種類のキャンディーが隣り合わせで連結されているほど得点が高くなります。

傾ける方向をうまく選んで得点を最大化してください。

詳細は公式の問題文を参考にしてください。

atcoder.jp

簡単な考察

探索する場合の探索空間について考えます。傾ける方向が4種類あり、全部で99回傾ける¹ため、出力パターンとして $4^{99}$ 通り考えられます。

ビームサーチなどの手法を用いて探索したくなるかもしれませんが、キャンディーを置く場所が1ターンずつ与えられるという隠しパラメータを含む問題であり、出力パターンに対応する期待値を簡単には求めることはできません。具体的には空きマスの数を $n$ として $n!$ 通りの隠しパラメータが考えられます。終盤はともかく、序盤や中盤で隠しパラメータを全探索することは不可能です。

効率よく探索するのが難しそう²なので、まずはルールベース解法で高得点を出すことを考えます。

ルールベース

突然ですが、キャンディーが2種類の問題を考えます³。

次のキャンディーがイチゴなら前に傾け、スイカなら後ろに傾けると、イチゴを下に、スイカを上に偏って配置させることができ、高確率で満点をとれます。

キャンディーが3種類の問題に戻します。

2種類の場合と同じように、種類ごとに特定の場所に偏って配置させることを目指します。

左上にスイカ、右上にパンプキン、下にイチゴを寄せるというように、どの種類をどこに置くかをあらかじめ決めておきます⁴。

次のキャンディーと傾ける方向の対応は下の表のようになるでしょう。

次のキャンディー	傾ける方向
スイカ	右
パンプキン	左
イチゴ	前

実はこのままだとうまくいきません。

下の画像のようにイチゴが置かれた後、次にパンプキンが来る場合を考えます。

左に傾けてもキャンディーは動かず、どこにパンプキンが置かれてもイチゴと混ざってしまいます。

この場合は後ろに傾けると次のようにうまくいくでしょう。

この例のように、前のキャンディー、あるいは前に傾けた方向まで考慮してルールを作るとよさそうです。

例えば次のような対応が考えられます。

前のキャンディー \ 次のキャンディー	スイカ	パンプキン	イチゴ
スイカ	後ろ（右）	左	前
パンプキン	右	後ろ（左）	前
イチゴ	後ろ	後ろ	前

括弧を付けたほうを採用すると 133 M 点ほど、括弧が付いていないほうを採用すると 135 M 点ほどになりました⁵。ルールベース解法だけで順位表の100位程度に入れます⁶。

モンテカルロ法

ルールベース解法は非常に高速に動作して実行時間がもったいないうえ、キャンディーが追加された場所の情報を使用していません。まだまだ最適化の余地がありそうです。

そこで、モンテカルロ法を使用しました。おおよそ次のような流れです。

全体の流れ

長さ100のルールベース解 $a$ を作成する。
として次の処理を繰り返す。
1. 入力 $p_t$ を受け取ってキャンディーを置く。
2. モンテカルロ法で t 回目に傾ける方向を決めて出力する。

モンテカルロ法の流れ

制限時間を求める。
制限時間を過ぎるまで次の処理を繰り返す。
1. に対して次の処理を繰り返す。
  1. 方向 d に箱を傾ける。
  2. プレイアウトを行う。具体的にはに対して次の処理を繰り返す。
    1. 空きマスを無作為に選んで種類 $f_u$ のキャンディーを置く。
    2. ルールベースで決めた方向 $a_u$ に傾ける。
  3. スコアを計算する。
スコアの平均値が最も高かった方向を t 回目に傾ける方向として採用する。

t 回目の処理で t 回目に傾ける方向を確定します。各方向に傾けたときの期待値⁷を知りたいのですが、当然ながら簡単には求まりません。そこで t + 1 回目以降の傾ける方向がルールベースで作成した方向であると仮定し、モンテカルロ法で期待値を推定しました。

t + 1 回目以降に傾ける方向の一部をランダムにするという方法も考えられるのですが、実装してみたらスコアが下がったのでやめました⁸。

上記の方針で 154 M 点ほど獲得できました。順位表の4位相当です。

上記アルゴリズムの改善

上記のアルゴリズムでは t 回目に傾ける方向として前後左右の4方向に対してプレイアウトを同じ回数ずつ行っていますが、期待値が低いとわかっている方向についてはプレイアウトをしなくてよさそうです。

前のキャンディーと次のキャンディーを見て、プレイアウトを行う方向を下の表のように制限しました⁹。

前のキャンディー \ 次のキャンディー	スイカ	パンプキン	イチゴ
スイカ	後ろ、右	後ろ、左	前、左、右
パンプキン	後ろ、右	後ろ、左	前、左、右
イチゴ	後ろ*	後ろ*	前、左、右

*を付けたところは、候補となっている方向が1つしかないため、プレイアウトを行わずに決定しました。

また、最後の20回については、プレイアウトのコストが低いなどの理由で、キャンディーの種類にかかわらず4方向全てを試すようにしました。

この方針で 161 M 点ほど獲得しました。

以下、細かい実装について説明します。

時間管理

コンテスト中の実装では毎回ほぼ等しい時間を使うようにしました。具体的には、t 回目の処理で残り時間を 100 - t で割った時間を消費するようにしました。

1回のプレイアウトで使用する時間は、およそ 100 - t に比例するため、残り時間の $\frac{100 - t + \alpha}{\sum_{u=t}^{100}{100 - u + \alpha}}$ を使ったほうがプレイアウトの回数が大体そろっていいかもしれません。 $\alpha$ はスコア計算などの定数部分にあたります。

プレイアウトの回数をそろえた場合、各 t に対し、全方向合わせて1500回程度のプレイアウトを行えました。最大3方向しかプレイアウトを行わないので、各方向に対して少なくとも500回程度はプレイアウトしたことになります。

乱数生成

各方向で使用する乱数を等しくしたほうがいいと思い、乱数を先に生成して使い回しました。

t が変わっても等しい乱数列を使用することで、乱数生成回数を最小限に抑えました。

シミュレーションの実装

初心者向けにシミュレーション部分の実装を簡単に紹介します。言語は C++ です。

grid[x][y] で座標 (x, y) のキャンディーの種類を表すものとします。(x, y) が空きマスのときは grid[x][y] = 0 とします。

キャンディーを置く

左上から順に空きマスを数え、指定した数になったらその場所にキャンディーの種類を代入するだけなので、簡単に実装できると思います。

void put(int f, int p) {
    // put a f-type candy at p
    for (int x = 0; x < n; ++x) {
        for (int y = 0; y < n; ++y) {
            if (grid[x][y] == 0) {
                if (--p == 0) {
                    grid[x][y] = f;
                    return;
                }
            }
        }
    }
    cerr << "Error: p is invalid in State.put" << endl;
}

箱を傾ける

傾ける方向として前後左右の4つが考えられるので、取り敢えず4つに場合分けします¹⁰。

void tilt(char d) {
    if (d == 'F') {
        // tilt forward
    } else if (d == 'B') {
        // tilt backward
    } else if (d == 'L') {
        // tilt left
    } else if (d == 'R') {
        // tilt right
    } else {
        cerr << "Error: unknown direction '" << d << "'" << endl;
    }
}

前に傾ける場合を考えます。

様々な実装方法が考えられますが、ここでは空間計算量を抑えた実装を紹介します。

// tilt forward
for (int y = 0; y < n; ++y) {
    int cnt = 0;
    for (int x = 0; x < n; ++x) {
        if (grid[x][y]) {
            swap(grid[cnt++][y], grid[x][y]);
        }
    }
}

swap 関数の部分がわかりにくいですが、やろうとしていることは

if (cnt != x) {
    grid[cnt][y] = grid[x][y];
    grid[x][y] = 0;
}
cnt++;

と同じです。cnt == x のときは上に空きマスがないときなので変更する必要がなく、cnt != x のときは最も上の空きマス grid[cnt][y] に grid[x][y] を移動させ、grid[x][y] を空にしています。

何度も呼ばれる関数ですので、ある程度は高速化に拘ったほうがいいと思います。

スコアを求める

BFS や DFS で連結成分を数えればよいです。DSU を用いたほうが実装が少し楽かもしれません。

bool in_grid(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < n;
}

int dfs(int x, int y, array<array<bool,n>,n> &visited) {
    // return the size of the group
    int candy = grid[x][y];
    assert(1 <= candy && candy < 4);
    visited[x][y] = true;
    stack<pair<int,int>> todo;
    todo.push({x, y});
    int cnt = 0;
    while (!todo.empty()) {
        ++cnt;
        auto [x, y] = todo.top();
        todo.pop();
        for (auto [dx, dy] : dxdy) {
            int xd = x + dx;
            int yd = y + dy;
            if (in_grid(xd, yd) && !visited[xd][yd] && grid[xd][yd] == candy) {
                visited[xd][yd] = true;
                todo.push({xd, yd});
            }
        }
    }
    return cnt;
}

int score() {
    array<array<bool,n>,n> visited{};
    int ret = 0;
    for (int x = 0; x < n; ++x) {
        for (int y = 0; y < n; ++y) {
            if (visited[x][y]) {
                continue;
            }
            int group_size = dfs(x, y, visited);
            ret += group_size * group_size;
        }
    }
    return ret;
}

正確なスコアを求めてもよかったのですが、少し面倒だと思ったので、連結成分の大きさの二乗和をスコアとみなしました。

提出コード

コンテスト中のコードを一部変更したものです。

atcoder.jp

最後に

参加記というより解説らしい記事になってしまいましたが、解法は一例です~~し、調子に乗って自分の解法を正当化しすぎている可能性がある~~ので参考程度にしていただけたらと思います。

主催企業のトヨタ自動車様、writer の chokudai さん、wata さん、参加者の皆さん、ありがとうございました。

次の AHC も楽しみにしてます。

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

100回目は箱を傾けてもキャンディーが動かないので考えないことにします。↩
効率がいい探索手法を私が思いつけなかっただけで、もしかしたらあるかもしれません。↩
コンテスト中に2種類の場合の問題を考えたわけではありません。説明をわかりやすくするために書きました。↩
コンテスト中に上、右、左下というような分け方も試しましたがうまくいきませんでした。また、どの種類のキャンディーをどこに配置するかを事前情報から決定するとよさそうですが、あまり本質ではないと思います。出現回数が少ない種類のキャンディーが下に配置されるようにしたつもりでしたが、コンテスト中の私の提出ではバグでパンプキンが下にくるように固定されていたと思います。↩
[11/4 追記] 前のキャンディーだけでなく、前に傾けた方向まで見ないと高スコアを出せないかもしれないです。私の実装では前に傾けた方向も使用していました。詳しくは提出コードをご覧ください。↩
130 M 点台の人が多いので、ちょっとした改善で20位ぐらいまで伸びるかもしれません。↩
毎回、最適な方向に傾けたときの期待値のことです。無作為な方向に傾けたときの期待値ではありません。↩
モンテカルロ木探索の要領で、プレイアウトでうまくいった方向を優先して採用すればうまくいくかもしれません。私は実装していません。↩
手動で設定しました。前に傾けた方向や直前にキャンディーが置かれた位置なども考慮すれば、事前の枝刈りを細かく設定できそうです。プレイアウトを繰り返す途中で枝刈りするという手法も考えられます。↩
賢い人は場合分けの数を減らせるかもしれません。↩