Skip to content

AHC042 - Oni wa Soto, Fuku wa Uchi ​

問題文(AtCoder) / コンテストページ

使用した主な手法:貪欲法 / ビームサーチ / bitset / Zobrist Hash / 解の後処理

問題概要 ​

N×N の盤面に、鬼(x)と福(o)がそれぞれ 2N 個ずつ置かれている。各行・列を上下左右に1マスずつ動かし、福を盤外に落とさず、すべての鬼を盤外に落とすことが目的。

操作は次の4種類。

操作内容
U j列 j を上へ1マス動かす
D j列 j を下へ1マス動かす
L i行 i を左へ1マス動かす
R i行 i を右へ1マス動かす

動かした方向の端にある駒は盤外へ落ち、反対側には空きマスができる。

例えば、ある行を左に動かすと次のようになる。

text
操作前:. x o . .
          ↓ L
操作後:x o . . .

N=20 で固定されており、操作回数の上限は 4N2=1600 手。

操作回数を T、残った鬼を X、落としてしまった福を Y とすると、得点は次のとおり。

score={8N2−T(X=0, Y=0)4N2−N(X+Y)(それ以外)

つまり、まずすべての鬼を落とすことが重要で、そのうえで操作回数をできるだけ少なくする。

問題では、すべての鬼について、上下左右の少なくとも1方向に福が存在しないことが保証されている。この性質から、福を落とさずに全鬼を除去する解を必ず構築できる。

解法の概要 ​

基本方針は、確実に鬼をすべて落とす退避解を貪欲法で作り、ビームサーチでそれより短い操作列を探すこと。

  1. 退避解を構築する:福のいない方向へ鬼を押し出し、逆方向に戻す操作を繰り返す。複数の鬼をまとめて落とせる方向を優先する。
  2. ビームサーチで改善する:盤面を状態として、合法な上下左右の操作をすべて試す。
  3. 評価関数で候補を絞る:各鬼から盤面の端までの距離をもとに評価し、有望な盤面だけを残す。
  4. 探索を2段階で行う:最初はビーム幅200、次に900で探索する。常にそれまでの最良解を保持する。
  5. 不要な操作を削除する:完成した操作列から1手ずつ削除を試し、正解のままなら削除する。
項目この実装での設定
探索手法ビームサーチ
ビーム幅200 → 900
探索の時間制限開始から 1.75 秒
状態鬼と福の配置を行・列のbitsetで管理
評価関数各鬼から4方向の端までの距離の最小値の合計
重複除去Zobrist Hash
退避解鬼のまとめ落としを優先する貪欲法
後処理1手削除しても完成するなら削除

実装の役割分担は次のとおり。

構造体・関数役割
Input初期盤面の読み込み
Action移動方向と行・列番号
State盤面・残りの鬼・評価値の管理
State::advance()盤面を1手進める
State::calc_score()盤面の評価
HashZobrist Hashの乱数表
Solver::fallback()退避解の構築
Solver::beam_search()ビームサーチ
Trace / restore()操作列の復元
remove_waste()不要な操作の削除

解法のエッセンス ​

貪欲法で必ず完成する退避解を作る ​

ビームサーチは、制限時間内に鬼をすべて落とせるとは限らない。そこで、最初に必ず完成する退避解を作っておく。

ある鬼について、左側に福が存在しなければ、その鬼が盤外に出るまで行を左に動かせる。その後、同じ回数だけ右に戻せば、残った駒の位置を元に戻せる。

text
左端                     右端

. x x . . o .   初期状態
x x . . o . .   L
x . . o . . .   L(鬼を1個除去)
. . o . . . .   L(鬼をもう1個除去)

. . . o . . .   R
. . . . o . .   R
. . . . . o .   R

実際には、取り除きたい鬼を含む先頭から k マスの範囲に福が存在しないことを確認する。

この処理を繰り返せば、盤面に残る駒の位置を保ちながら鬼を取り除ける。

ただし、鬼を1個ずつ落とすより、同じ行・列にある複数の鬼をまとめて落とす方が効率的。

そこで、各方向について先頭から k マスに含まれる鬼の個数を r とし、次のコストを最小化する。

cost=2kr

2k は押し出して元に戻す操作回数、r は取り除ける鬼の個数である。実装では整数演算のため1000倍して評価している。

cpp
int removed = 0;
rep(k, N) {
    if ((o >> k) & 1u) break;
    removed += (x >> k) & 1u;
    if (removed == 0) continue;

    int cost = (2 * (k + 1) * 1000) / removed;
    if (cost < best_cost) {
        best_cost = cost;
        best = Action(dir, p);
        best_k = k + 1;
    }
}

各方向・各行列について調べ、最も効率よく鬼を落とせる操作を採用する。

最後の鬼を落とした場合は、逆方向に戻す必要もない。

この退避解は、後のビームサーチにおいて現在の最良手数の上界としても利用する。

行と列をbitsetで管理する ​

ビームサーチでは大量の盤面を生成するため、1手の更新を高速に行う必要がある。

盤面サイズは N=20 なので、1行・1列の状態は32bit整数に収まる。

そこで、次の4つの配列を保持する。

cpp
array<unsigned, N> row_x{}, row_o{};
array<unsigned, N> col_x{}, col_o{};
  • row_x[i]:行 i の鬼の位置
  • row_o[i]:行 i の福の位置
  • col_x[j]:列 j の鬼の位置
  • col_o[j]:列 j の福の位置

行・列の両方を持つことで、上下左右の操作をビットシフトで処理できる。

例えば、行を左に1マス動かす操作は次のようになる。

cpp
x = x >> 1;
o = o >> 1;

右方向なら次のとおり。

cpp
x = (x << 1) & MASK;
o = (o << 1) & MASK;

ここで MASK = (1u << N) - 1 は、盤面外のビットを除去するためのマスク。

また、福を盤外に落とす操作は探索対象から除外する。

cpp
bool can_move(Action a) const {
    unsigned o = (a.dir == 0 || a.dir == 2)
                     ? col_o[a.x] : row_o[a.x];

    return (o & ((a.dir == 0 || a.dir == 1)
                     ? 1u : 1u << (N - 1))) == 0;
}

これにより、ビームサーチで生成するすべての盤面が「福を落としていない」という条件を満たす。

行と列の情報を差分更新する ​

行を動かした場合、列のbitsetも更新しなければならない。

しかし、毎回盤面全体を作り直す必要はない。

操作前後のbitsetのXORを取れば、駒の有無が変わったマスだけを取得できる。

cpp
unsigned old_x = x, old_o = o;

x = to_front ? (x >> 1) : ((x << 1) & MASK);
o = to_front ? (o >> 1) : ((o << 1) & MASK);

unsigned dx = old_x ^ x;
unsigned do_ = old_o ^ o;

例えば、dx のビットが1の場所では、鬼の有無が変化したことになる。

cpp
while (dx) {
    int j = __builtin_ctz(dx);
    dx &= dx - 1;

    tx[j] ^= 1u << a.x;

    int r = vertical ? j : a.x;
    int c = vertical ? a.x : j;
    hash ^= hasher.z[r][c][0];
}

__builtin_ctz(dx) は、最下位の1ビットの位置を取得する関数。

dx &= dx - 1 によって、その1ビットを消している。

これを繰り返すことで、変化したマスだけ更新できる。同時にZobrist Hashも更新する。

行と列の両方を保持し、片方の変更をもう片方に差分反映するのが高速化のポイント。

鬼から盤面の端までの距離で評価する ​

ビームサーチでは、途中の盤面を評価し、有望なものを選ぶ必要がある。

単純に残りの鬼の数だけを評価すると、鬼を落とす直前の盤面と、鬼が中央に集まっている盤面を区別しにくい。

そこで、各鬼が盤面の端にどれくらい近いかを評価する。

鬼が座標 (i,j) にあるとき、上下左右の端まで押し出して戻す概算コストは以下のとおり。

u=2(i+1)+bud=2(N−i)+bdl=2(j+1)+blr=2(N−j)+br

bu,bd,bl,br は、それぞれの方向に福が存在する場合に1、存在しなければ0となるペナルティ。

鬼1個の評価値は、

d(i,j)=min(u,d,l,r)

盤面全体の評価値は、

E=∑(i,j)∈Xd(i,j)

となる。ここで X は鬼が存在するマスの集合。評価値は小さいほどよい。

実装では次のように計算している。

cpp
int u = 2 * (i + 1)
      + ((col_o[j] & ((1u << i) - 1)) != 0);
int d = 2 * (N - i)
      + ((col_o[j] >> (i + 1)) != 0);
int l = 2 * (j + 1)
      + ((row_o[i] & ((1u << j) - 1)) != 0);
int r = 2 * (N - j)
      + ((row_o[i] >> (j + 1)) != 0);

score += min({u, d, l, r});

この評価関数の利点は、鬼を落としていなくても、盤面の改善を評価できること。

また、同じ行や列に複数の鬼が並んでいる場合、1回の操作で複数の鬼を端へ近づけられるため、自然とまとめて動かす操作も評価されやすい。

評価関数の割り切り

福が途中に存在する場合のペナルティはわずか +1 であり、実際にその方向へ鬼を落とせるかを厳密には評価していない。

また、複数の鬼を同時に落とせる効果も正確な操作回数として計算しているわけではない。

あくまで、ビームサーチで有望な盤面を高速に比較するための近似評価である。

ビームサーチで有望な盤面だけを残す ​

各ターンで現在のビームにある盤面から、上下左右のすべての操作を試す。

操作は4方向×20行・列なので、最大80種類となる。

cpp
for (const State& s : beam) {
    rep(dir, 4) rep(p, N) {
        Action a(dir, p);
        if (!s.can_move(a)) continue;

        State ns = s;
        ns.advance(a, hasher);

        if (ns.hash == s.hash ||
            !used.insert(ns.hash).second) continue;

        trace.push_back({s.trace_id, a});
        ns.trace_id = (int)trace.size() - 1;

        if (ns.rest == 0) return restore(ns.trace_id);

        ns.calc_score();
        next.push_back(ns);
    }
}

候補生成時には、次のように処理する。

  • 福が落ちる操作は除外する。
  • 盤面が変化しない操作は除外する。
  • 同じ盤面になる候補は重複除去する。
  • すべての鬼が落ちたら即座に操作列を返す。
  • それ以外は評価値を計算する。

候補の評価には、わずかなタイブレークを加えている。

cpp
auto better = [](const State& a, const State& b) {
    int sa = 32 * a.score + (a.hash & 31);
    int sb = 32 * b.score + (b.hash & 31);
    return sa < sb;
};

評価値が同じ盤面については、ハッシュの下位5ビットを利用して順序を変える。

同点の場合に毎回決まった位置の候補ばかり選ばれることを避け、探索に多少の多様性を持たせる狙いがある。

候補がビーム幅を超えた場合は、nth_element() で上位だけを残す。

cpp
if ((int)next.size() > width) {
    nth_element(next.begin(),
                next.begin() + width,
                next.end(), better);
    next.resize(width);
}
beam = move(next);

全候補を完全にソートする必要はないため、sort() より軽い処理で上位候補を選べる。

Zobrist Hashで盤面の重複を除去する ​

異なる操作列でも、同じ盤面に到達することがある。

同じターンで同じ盤面を何度も探索するとビーム幅を無駄に消費するため、Zobrist Hashを使って重複を除去する。

各マスと駒の種類にランダムな64bit値を割り当てる。

cpp
ull z[N][N][2];
  • z[i][j][0]:(i,j) に鬼が存在する場合の値
  • z[i][j][1]:(i,j) に福が存在する場合の値

盤面のハッシュは、存在するすべての駒に対応する値のXORで表す。

H=⨁(i,j)∈Xz[i][j][0]⊕⨁(i,j)∈Oz[i][j][1]

ここで O は福が存在するマスの集合。

駒の配置が変わった場合、該当する値をXORするだけでハッシュを更新できる。

cpp
hash ^= hasher.z[r][c][0];

XORは同じ値を2回適用すると元に戻るため、駒の追加・削除の両方を同じ処理で扱える。

探索中は、

cpp
unordered_set<ull> used;

で盤面のハッシュを管理し、同じハッシュを持つ候補を除外する。

ハッシュの注意点

64bitハッシュには衝突の可能性がある。今回の実装では衝突時の厳密な盤面比較はしていない。

操作列を親ポインタで復元する ​

各盤面に操作列全体を保持すると、状態をコピーするたびに長い配列もコピーする必要がある。

そこで、各状態には trace_id のみを持たせ、操作履歴は別の配列に保存する。

cpp
struct Trace {
    int parent;
    Action action;
};

新しい状態を生成するときは、親のIDと今回の操作だけを記録する。

cpp
trace.push_back({s.trace_id, a});
ns.trace_id = (int)trace.size() - 1;

完成した状態が見つかったら、親をたどって操作列を復元する。

cpp
vector<Action> restore(int id) {
    vector<Action> res;
    while (id != 0) {
        res.push_back(trace[id].action);
        id = trace[id].parent;
    }
    reverse(all(res));
    return res;
}

これにより、盤面のコピーに操作列全体を含める必要がなくなる。

ビーム幅を変えて2回探索する ​

探索はビーム幅を変えて2回実行する。

cpp
auto backup = fallback(state);
auto ans = beam_search(state, 200, backup);
ans = beam_search(state, BEAM_WIDTH, ans);

1回目はビーム幅200で探索し、比較的軽い探索で改善を試みる。

2回目はビーム幅900で、より多くの状態を残して探索する。

どちらも、鬼をすべて落とす解が見つからなければ、引数として渡した退避解を返す。

また、現在の最良解の手数より長い探索を行う必要はないため、探索の最大深さは次のように制限する。

cpp
int best_turns = (int)default_ans.size();

for (int turn = 0;
     turn < best_turns && turn < LIMIT;
     turn++) {
    // ビームサーチ
}

一度短い解が見つかれば、その手数を上界として次の探索を行える。

なお、探索時間の 1.75 秒は各探索に対してではなく、Solver 開始時からの共通の時間制限である。

最後に不要な操作を削除する ​

ビームサーチで見つかった操作列に、削除しても結果に影響しない操作が含まれていることがある。

そこで、操作列の末尾から1手ずつ削除を試す。

cpp
void remove_waste(vector<Action>& ans) {
    for (int i = (int)ans.size() - 1; i >= 0; i--) {
        auto b = ans;
        b.erase(b.begin() + i);
        if (is_complete(b)) ans = move(b);
    }
}

is_complete() は、削除後の操作列を最初からシミュレーションし、福を落とさずにすべての鬼を取り除けるか判定する。

cpp
bool is_complete(const vector<Action>& actions) {
    State s(input, hasher);
    for (Action a : actions) {
        if (!s.can_move(a)) return false;
        s.advance(a, hasher);
    }
    return s.rest == 0;
}

削除できれば、その分だけ最終得点が上がる。

これは1手削除を逆順に1回試す簡単な後処理であり、すべての不要操作を除去できるとは限らない。それでも、完成済みの解を壊さずに改善できるのが利点である。