Skip to content

AHC046 - Skating with Blocks ​

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

使用した主な手法:0-1 BFS / 経路復元 / ランダム化

問題概要 ​

N×N のスケートリンク上で、指定された M 個の目的地を順番に訪問する問題。

プレイヤーは以下の3種類の操作を行える。

操作内容コスト
M隣接するマスに1マス移動1
S壁またはブロックにぶつかるまで滑走1
A隣接するマスのブロックを設置・撤去1

滑走は何マス進んでも1手で済むため、積極的に利用したい。

ただし、滑走中に目的地を通過しても訪問したことにはならない。目的地にちょうど停止する必要がある。

そのため、目的地の直後にブロックを設置して、滑走を止めることが重要になる。

text
          滑走方向 →

    現在地      目的地 ブロック
      P    .   .   G   #
      └───────────→┘

    S R:1手で目的地Gに到達

一方、ブロックがなければ、滑走は盤面の端まで続いてしまう。

ブロックはいつでも設置できるわけではなく、現在地の隣接マスにしか設置できない。

したがって、効率のよい経路を作るためには、移動経路とブロックの配置を同時に考える必要がある。

制約は N=20, M=40 で固定されており、操作回数の上限は 2NM=1600 手。

すべての目的地を訪問できた場合、操作回数を T とすると得点は、

score=M+2NM−T

となる。

よって、まず全目的地を順番に訪問する解を作り、その操作回数を最小化することが目標となる。

解法の概要 ​

この解法では、目的地間の移動を0-1 BFSで探索し、ブロックの設置・撤去をあとから操作列に復元する。

通常の最短経路探索と異なり、ブロック配置によって滑走の停止位置を増やせることを利用する。

全体の流れは次のとおり。

  1. ブロックを使わず、1マス移動のみで全目的地を訪れる初期解を作る。
  2. 現在のブロック配置を保持し、次の目的地まで0-1 BFSを実行する。
  3. 過去にブロックを設置できた場所を、滑走の停止位置として探索に組み込む。
  4. 探索結果をもとに、必要なブロックの設置・撤去を含めた操作列を復元する。
  5. 解の合法性を検証し、操作回数が短くなれば最良解を更新する。
  6. 制限時間まで探索を繰り返す。
項目この実装での設定
探索手法0-1 BFS
探索単位隣り合う目的地間
探索状態数N2×5=2000
ブロック配置bitset<400>
ランダム化同コストの経路からランダム選択
制限時間約1.85秒
初期解ブロックを使わないマンハッタン経路
解の管理合法な最良解を保持

実装の役割は以下のように分かれている。

構造体・関数役割
Input目的地の読み込み
Stateブロック配置と累積コスト
advance()0-1 BFSによる次の目的地への移動
reconstruct()停止位置の列から操作列を復元
valid()復元した解の合法性検証
initial_stops()初期解の構築
solve()制限時間内での繰り返し探索

解法のエッセンス ​

滑走中か停止中かを状態として持つ ​

通常のBFSなら、プレイヤーの位置だけを状態にすればよい。

しかし、この問題では滑走によって複数マスを1手で移動できる。

そこで、各マスについて「停止中」と「4方向に滑走中」の5種類の状態を持つ。

v=5p+s
  • p:現在のマス(0≤p<N2)
  • s=0,1,2,3:それぞれ上・左・下・右に滑走中
  • s=4:停止中
cpp
static constexpr int SZ = 400 * 5;

停止中の状態からは、移動と滑走開始の2種類の遷移ができる。

cpp
if (s == 4) {
    rep(d, 4) {
        int q = adj[p][d];
        if (q < 0 || st.block[q]) continue;

        push(v, q * 5 + 4, 1); // 1マス移動
        push(v, q * 5 + d, 1); // 滑走開始
    }
}

いずれも操作を1回使うため、コストは1となる。

一方、滑走中は次のマスへ進んでも追加の操作を消費しない。

cpp
if (q < 0 || st.block[q]) {
    push(v, p * 5 + 4, 0); // 壁で停止
} else {
    push(v, q * 5 + s, 0); // 滑走継続
}

つまり、遷移コストは0または1だけになる。

そのため、通常のBFSではなく0-1 BFSを使用できる。

0-1 BFSでは、コスト0の遷移をdequeの先頭、コスト1の遷移を末尾へ追加する。

cpp
if (cost == 0) que.push_front(to);
else que.push_back(to);

これによって、何マス滑走しても1手として扱う最短経路探索を実現できる。

過去にブロックを置けた場所を記録する ​

この解法の特に重要なアイデアが、ブロックをあとから設置することを前提に経路を探索することである。

普通にBFSを実行するだけでは、現在あるブロックと盤面の端でしか滑走を停止できない。

しかし、以前に訪問した地点の隣なら、そこでブロックを置いておくことができたはずである。

そこで、State に2種類のbitsetを持たせる。

cpp
struct State {
    bitset<400> block, can_build;
    int cost = 0;
};
  • block:現在設置されているとみなすブロック
  • can_build:過去の停止位置からブロックを設置できたマス

例えば、以前に地点Aを訪れていた場合、その隣接マスBにブロックを設置できる。

text
    過去の停止位置A
          |
          v
    . . A B . . .
          ↑
       ブロックを
       設置できる

その後、別方向からBへ向かって滑走すると、Bの手前で停止できる可能性がある。

このように、ブロックの設置可能性を記録すれば、現在はブロックがない場所も将来の停止位置として利用できる。

実装では、停止したマスの隣接位置を can_build に登録する。

cpp
if (s == 4) {
    rep(d, 4) {
        int q = adj[p][d];

        if (q >= 0 &&
            !next.block[q] &&
            target_id[q] <= step) {
            next.can_build[q] = true;
        }
    }
}

ここで、target_id[q] <= step は、将来訪れる目的地へのブロック設置を避けるための条件である。

目的地ではないマスの target_id は -1 なので、設置対象となる。

また、実際に通過したマスについては、

cpp
next.can_build[p] = false;

として、その時点でブロックが置かれていないことを反映している。

can_build は単なる設置可能性の記録であり、実際にいつ設置するかは後段の復元処理に任せる。

ブロックを仮に設置して滑走を停止する ​

0-1 BFSの滑走中には、通常の滑走継続に加えて、もう1つの遷移を用意する。

cpp
if (st.can_build[q] && !avoid[q]) {
    push(v, p * 5 + 4, 1);
}

これは、次のマス q にブロックを設置しておけば、現在地 p で停止できる、という仮の遷移である。

text
    滑走方向 →

    . . . P Q . .
          ↑ ↑
          | 仮のブロック
          停止位置

ここでのコスト1は、ブロックを設置する操作に対応する。

重要なのは、滑走している途中でブロックを設置するわけではないこと。

実際のルールでは、滑走中にブロックを置くことはできない。

この遷移は、過去の停止位置で事前にブロックを設置しておくことを仮定したものである。

この工夫により、ブロック配置自体をBFSの状態に含めずに、配置変更による効果を探索できる。

ただし、仮の配置が必ず実現可能とは限らないため、後述する確認処理が必要になる。

仮のブロック配置を検証し、失敗したら探索し直す ​

BFSの経路が見つかった後、その経路をたどりながらブロック配置を更新する。

仮のブロックを使用する場合、そのマスが本当に設置可能か確認する。

cpp
if (!next.can_build[q]) {
    bad = q;
    break;
}

next.block[q] = true;
next.can_build[q] = false;

もし実際には設置できないマスだった場合、そのマスを bad として記録する。

そして、avoid に登録して再び0-1 BFSを実行する。

cpp
if (avoid[bad]) return false;
avoid[bad] = true;

次回の探索では、そのマスを新たな仮ブロックとして利用しない。

cpp
if (st.can_build[q] && !avoid[q]) {
    push(v, p * 5 + 4, 1);
}

この処理を最大401回繰り返す。

つまり、次のような探索になっている。

  1. 仮のブロックを許して短い経路を探す。
  2. 見つかった経路が実現可能か確認する。
  3. 実現できなかったブロック位置を禁止する。
  4. 別の経路を探し直す。

探索中は制約を一部緩和し、あとから実現可能性を確認するという考え方である。

これにより、ブロック配置をすべて状態に含める巨大な探索を避けている。

停止位置だけを記録して操作列を復元する ​

advance() が直接返すのは、最終的な M・S・A の操作列ではない。

代わりに、プレイヤーが停止した位置の列 stops を記録する。

例えば、

text
stops = [A, B, C, D]

という経路が得られたとする。

隣り合う停止位置が1マス離れていれば通常の移動 M、2マス以上離れていれば滑走 S として復元する。

cpp
ans.push_back({len == 1 ? 'M' : 'S', d});

ただし、滑走を途中で停止させる場合、停止位置の直後にブロックが必要となる。

そこで、ブロックがまだ設置されていなければ、過去の停止位置の中から、そのブロックに隣接していた地点を探す。

cpp
int at = -1, dir = -1;

for (int j = i; j >= 0 && at < 0; --j) {
    rep(dd, 4) {
        if (adj[stops[j]][dd] == wall) {
            at = j;
            dir = dd;
            break;
        }
    }
}

見つかった場合、そこにブロック設置操作 A を挿入する予約を行う。

cpp
alter[at][dir] = true;
built[wall] = true;

最終的な操作列では、各停止位置に到着した際に、必要な A 操作を先に行ってから移動する。

cpp
rep(i, k - 1) {
    rep(d, 4) {
        if (alter[i][d]) ans.push_back({'A', d});
    }

    int p = stops[i], q = stops[i + 1];
    if (p == q) continue;

    int d = direction(p, q);
    int len = abs(p / n - q / n)
            + abs(p % n - q % n);

    ans.push_back({len == 1 ? 'M' : 'S', d});
}

これが、停止位置の列から具体的な操作列を復元する仕組みである。

不要になったブロックは撤去する ​

ブロックは、滑走を停止するためには役立つが、その後の移動を妨げることもある。

例えば、一度ブロックを設置して滑走を止めたあと、次の目的地に向かうにはそのブロックを通過しなければならない場合がある。

このような場合は、ブロックを撤去する必要がある。

実装では、ブロックを利用して停止した際に、そのブロックをあとで撤去できる位置を記録しておく。

cpp
remove_at[wall] = i + 1;
remove_dir[wall] = d;

そのブロックを後続の経路が通過する際、保存した停止位置に撤去操作を追加する。

cpp
if (built[t]) {
    int at = remove_at[t];
    if (at < 0) return {};

    alter[at][remove_dir[t]] = true;
    built[t] = false;
}

このように、ブロックの設置だけでなく撤去も操作列の復元時に決定する。

経路探索と具体的なブロック操作のタイミングを分離しているのが、この解法の特徴である。

同じ距離の経路からランダムに選ぶ ​

0-1 BFSでは、同じ最短コストの経路が複数見つかることがある。

通常の最短経路探索なら、どれを選んでも距離は同じである。

しかし、この問題では、どの経路を通ったかによって次の目的地以降で利用できるブロック配置が変わる。

そのため、同じコストでも異なる経路を試す価値がある。

実装では、同じ距離で到達できた場合に、親をランダムに更新する。

cpp
} else if (nd == dist[to]) {
    if (randint(++count[to]) == 0)
        prev[to] = from;
}

これにより、同コストの候補の中から異なる経路が選ばれるようになる。

このランダム化を利用して、目的地を訪れる順番は固定したまま、経路やブロック配置の異なる解を生成している。

ブロックを使わない初期解を用意する ​

探索が途中で失敗しても、必ず出力できる解を持っておく。

そのため、最初にブロックを一切使用せず、目的地間をマンハッタン経路で移動する初期解を構築する。

cpp
vi initial_stops() {
    vi stops{target[0]};

    rep(i, m - 1) {
        int p = target[i], q = target[i + 1];

        while (p != q) {
            int d = p / n > q / n ? 0 :
                    p / n < q / n ? 2 :
                    p % n > q % n ? 1 : 3;

            p = adj[p][d];
            stops.push_back(p);
        }
    }
    return stops;
}

初期状態では盤面にブロックが存在しないので、隣接マスへの移動だけで確実にすべての目的地を訪問できる。

この初期解を best_ans に設定しておく。

cpp
best_ans = reconstruct(initial_stops());

以降の探索で短い解が見つからなくても、この解を出力できる。

解の合法性を最後に検証する ​

0-1 BFSでは、ブロックの設置可能性を近似的に扱っている。

そのため、復元された操作列が本当に合法であるとは限らない。

そこで、valid() で最初からすべての操作を実行し、以下を確認する。

  • 移動先にブロックがないか
  • 滑走が正しく停止するか
  • ブロックの設置・撤去が合法か
  • 目的地を指定された順番で訪問したか
  • 操作回数が上限以内か

すべての条件を満たし、最良解より短い場合だけ更新する。

cpp
if (!ans.empty() &&
    (int)ans.size() < (int)best_ans.size() &&
    valid(ans)) {

    best_ans = move(ans);
}

このように、探索ではある程度大胆な近似を使い、最終的な出力は厳密なシミュレーションで保証する構成になっている。

制限時間まで繰り返し探索する ​

最後に、制限時間まで0-1 BFSを繰り返す。

cpp
while (elapsed() < 1.85) {
    State st;
    vi stops{target[0]};
    bool ok = true;

    rep(i, m - 1) {
        if (elapsed() > 1.87 ||
            !advance(st, i, stops)) {
            ok = false;
            break;
        }

        if (st.cost >= (int)best_ans.size()) {
            ok = false;
            break;
        }
    }

    if (ok) {
        auto ans = reconstruct(stops);

        if (!ans.empty() &&
            (int)ans.size() < (int)best_ans.size() &&
            valid(ans)) {
            best_ans = move(ans);
        }
    }
}

途中までの推定コスト st.cost が現在の最良解以上になった場合は、改善の見込みが低いとして探索を打ち切る。

ランダム化された同コスト経路の選択により、繰り返すたびに異なる解が得られる可能性がある。

焼きなまし法のような近傍探索ではなく、ランダム化した経路構築を繰り返し、最良の完成解を保持する方法である。

まとめ ​

この解法の最も重要なアイデアは、0-1 BFSでブロックの設置を仮定した経路を探索し、実際の設置・撤去操作を後から復元することである。

特に以下の点が応用しやすい。

  • 停止中と滑走中を分けることで、0-1 BFSによる効率的な探索を実現する。
  • 過去の停止位置から設置可能なブロックを記録し、探索の自由度を増やす。
  • 仮のブロックが実現できなければ、その候補を禁止して再探索する。
  • 停止位置だけを保持し、実際の操作列は後から復元する。
  • 同コストの経路をランダムに選択して、異なる解を繰り返し生成する。
  • 最後に合法性を厳密に確認し、最良解だけを保存する。

通常の最短経路探索では、盤面が固定されていることが多い。

一方、この問題ではブロック配置によって移動経路そのものを変えられる。

盤面を変更する操作を探索に組み込みつつ、状態数を増やしすぎないための工夫が詰まった解法となっている。