Skip to content

AHC060 - Ice Cream Collection ​

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

使用した主な手法:BFS / シミュレーション / 時刻の閾値による状態表現 / 焼きなまし法

問題概要 ​

N 頂点 M 辺の連結な無向グラフ上で、アイスクリームを集めてショップに納品する問題。頂点には2種類ある。

  • ショップ(頂点 0,…,K−1):手元のアイスを納品する。
  • アイスの木(頂点 K,…,N−1):訪問すると、木の味に応じて W(バニラ)または R(ストロベリー)を1つ収穫する。

開始位置はショップ 0、手元のアイスは空。ショップを訪れると、これまでに集めた味の並びを納品して手元を空にする。例えば WWR と WRW は別のアイスとして扱われる。同じショップへの同じ味の並びの再納品は得点にならない。なお、空の状態での納品も1種類として数えられる。

木は最初すべて W だが、訪問中に1手を使って R に変更できる。変更は不可逆で、R から W には戻せない。

各行動には次の制約がある。

  • 隣接する頂点へ移動すると1手消費する。
  • W の木を R に変更する場合も1手消費する。
  • 直前の移動元へのUターンは禁止。色変更を挟んでも、この制約は変わらない。
  • 行動回数は最大 T 手。

ショップ i に納品した味の並びの集合を Si とすると、得点は次のとおり。

score=∑i=0K−1|Si|

本問題では N=100、K=10、T=10000。頂点の座標も入力されるが、今回のコードでは使用しない。

ポイントは、アイスをたくさん運ぶことではなく、ショップごとに異なる並びを増やすこと。 そのため、どの経路を通るかと、どの木をいつ R に変えるかが重要になる。

解法の概要 ​

この解法は、1万手の行動列を直接最適化しない。代わりに、各木を W から R に変更する時刻を決め、その設定に対する行動列をBFSで構築する。

  1. 木ごとに変更時刻を設定する:各木に threshold[v] を割り当てる。その時刻以降に訪問したら R に変更する。極端に大きい値は「変更しない」を表す。
  2. BFSで配送ルートを作る:現在位置から探索し、まだそのショップへ納品していない味の並びを作れる経路を最初に見つけたら実行する。見つからない場合は別のショップへ移動して仕切り直す。
  3. シミュレーションで評価する:閾値配置を固定して最大 T 手実行し、各ショップの異なる納品数の合計を得点とする。
  4. 焼きなましで閾値を更新する:よく訪問する木を優先して変更時刻を動かし、シミュレーション結果で採用・棄却する。
  5. 最良状態を再実行して出力する:探索中の最高得点の閾値配置から、行動列をもう一度生成する。

変更時刻の最適化とBFSによる行動列生成の関係

項目この実装での設定
探索時間1.92 秒(問題の実行時間制限は2秒)
最適化する変数各木の変更時刻 threshold[v](90個)
ルート構築BFSで新しい納品ができるショップを探す
1回のBFSの上限MAX_BFS = 4500 ノード
近傍時刻の前後移動・再設定・変更なし・2木の時刻交換
採用判定通常の確率受理を用いる焼きなまし法
温度5.0 から 0.15 へ指数的に減少
構造体・関数役割
Inputグラフ、手数制限、座標の読み込み
State木ごとの変更時刻、得点、訪問回数を保持
Solver::NodeBFS中の位置・直前の位置・コーン・仮の変更状態などを管理
simulate()閾値に従って実際の行動列を生成し、得点を計算
mutate()木の変更時刻を変更して近傍を作る
solve()焼きなましによる最適化と最終出力

解法のエッセンス ​

1万手を直接探索せず、木の変更時刻を探索する ​

木ごとの色変更は W → R の1回だけなので、**「何手目以降の訪問で色変更するか」**を決めれば、その木の変更方針をコンパクトに表現できる。

cpp
struct State {
    vi threshold;  // この時刻以降に訪問したら木をRへ変更
    int score = 0;
    array<int, 100> visit_count = {};
};

例えば threshold[v] = 4000 なら、その木がまだ W の状態で時刻4000以降に訪れたときに R に変更する。訪問した瞬間の収穫は変更前の W であり、そのあとで1手使って変更する。

閾値と味の変更タイミングの例

cpp
// Solver::simulate() 内の execute() より抜粋
cone = cone * BASE + (red[v] ? 2 : 1);
if (!red[v] && turn >= s.threshold[v] && turn < in.t) {
    red[v] = true;
    if (answer) answer->push_back(-1);
    ++turn;
}

threshold[v] = T + 100 とすれば、制限手数内では変更が起こらない。こうして約1万手の出力を、90個の整数値の最適化に置き換える。

初期状態では、各木をおおむね次の割合で設定する。

  • 15%:変更しない(T + 100)。
  • 15%:比較的早めに変更する(0..T/5)。
  • 70%:全期間からランダムに変更時刻を選ぶ(0..T)。

この「時刻を決め、訪問時に実行する」という表現のおかげで、変更対象となる木だけを探索変数にできる。

BFSで「新しい味の並びを納品できる経路」を探す ​

時刻の設定が決まっても、得点を得るには実際に移動して納品しなければならない。simulate() では、現在位置からBFSを行い、未納品の味の並びを届けられるショップを探す。

各ショップの在庫を stock[v] に保持する。BFSでショップ v に到達したとき、手元の味の並び h がまだ stock[v] に無ければ、そこを目標にする。

cpp
// Solver::simulate() のBFSより抜粋
if (v == cur.prev) continue;  // Uターン禁止
int cost = cur.cost + 1;
if (turn + cost > in.t) continue;

ull h = cur.hash, m0 = cur.mask0, m1 = cur.mask1;
if (v < in.k) {
    if (!stock[v].count(h)) {
        q[tail] = {0, m0, m1, v, cur.pos, head, cost, cur.depth + 1};
        goal = tail++;
        break;
    }
    h = 0;  // 納品するとコーンは空になる
}

探索では各頂点を一度しか訪れない通常のBFSと異なり、同じ頂点へ何度も到達する経路を探索できる。直前の頂点・コーンの中身・仮の色変更状態によって、同じ位置でも結果が変わるからだ。訪問済み状態の重複排除はしていないため、探索数を 4500 に制限している。

Node::depth は移動回数、Node::cost は移動と色変更を合わせた消費手数。キューは移動回数に沿って広がるため、色変更の手数まで含めた厳密な最短時間経路を探索しているわけではない。

コーンの味の並びを64bitのハッシュで表現する ​

BFSの各ノードで文字列を持つとコピーが重い。そのため、味を W=1, R=2 として次の式でコーンの中身を更新する。

hnext=h⋅B+c(mod264),B=1000000007,c∈{1,2}
cpp
static constexpr ull BASE = 1000000007ULL;
// 木に到達した場合
h = h * BASE + (is_red ? 2 : 1);
// ショップに到達した場合
h = 0;

この方法なら、味を1つ追加する処理と、納品済みかどうかの比較が定数時間でできる。ショップごとの在庫は vector<unordered_set<ull>> stock(in.k) で管理している。

ハッシュの注意点

uint64_t のオーバーフローを利用したハッシュであり、異なる文字列が同じ値になる可能性はある。今回のコードでは衝突を厳密には判定していない。また、空文字列はハッシュ 0 で表現する。

BFSの中でも将来の色変更を正しく扱う ​

実際の盤面で R に変更したかどうかは red[v] で管理する。しかしBFSは、まだ実行していない将来の経路を探索するため、「この経路を通ったら途中でどの木が R になるか」も考慮しなければならない。

そこでBFSノードに2個のビットマスクを持ち、探索中だけの変更を記録する。

cpp
struct Node {
    ull hash, mask0, mask1;
    int pos, prev, parent, cost, depth;
};
  • mask0:頂点 0..63 に対応する変更済みビット。
  • mask1:頂点 64..99 に対応する変更済みビット。
  • red[v]:すでに実行済みの経路で R になったかどうか。

木 v の収穫時には、red[v] と仮の変更ビットを合わせて現在の味を決める。

cpp
bool is_red = red[v];
if (v < 64) is_red |= (m0 >> v) & 1;
else is_red |= (m1 >> (v - 64)) & 1;

h = h * BASE + (is_red ? 2 : 1);
if (!is_red && turn + cost >= s.threshold[v] && turn + cost < in.t) {
    ++cost;  // この木をRにする操作を1手分計上
    if (v < 64) m0 |= 1ULL << v;
    else m1 |= 1ULL << (v - 64);
}

ここで重要なのは、色変更がコーンへの収穫より後に起こること。今回は W を収穫し、その後の訪問で初めて R を収穫する。仮の変更状態は、BFSの別分岐には伝わらない。

BFSで有望な経路が見つかったら、parent をたどって移動先の列を復元し、execute() で実行する。このとき色変更が必要なら -1 が自動的に出力列に挿入される。

未納品の経路が見つからないときはショップへ移動する ​

MAX_BFS = 4500 ノードまでに新しい納品を見つけられない場合もある。そこで、重複納品でもいったん別のショップへ向かうことで探索位置を変える。

cpp
// Solver::simulate() のフォールバック候補選択より抜粋
if (v < in.k && v != pos &&
    cur.depth + 1 >= 3 && cur.depth + 1 <= 10) {
    ++fallback_count;
    if (fallback_rng.randint(1, fallback_count) == 1)
        fallback = tail;
}

移動距離が3〜10辺の別ショップを候補とし、リザーバーサンプリングでほぼ一様に1つを選ぶ。該当候補がない場合は、BFS中で見つかった現在位置とは異なるショップを先頭から選ぶ。それも無ければ生成を終了する。

この移動自体では得点が増えないこともあるが、停滞している場所から抜け、別の配送ルートを探すことが狙い。

同じ閾値配置なら同じ結果になるようにする ​

焼きなましでは、変更前後の状態を公平に比べたい。ところが、シミュレーションのたびにBFSの探索順やフォールバックが変わると、得点の差が閾値変更によるものなのか、単なる乱数によるものなのか分かりにくい。

そこで、このコードでは乱数を次のように扱っている。

  • Solver の構築時に隣接リストを一度シャッフルし、その後は固定する。
  • フォールバック選択用の Random fallback_rng(11939) を simulate() のたびに同じ種で初期化する。
  • 焼きなましで使う乱数 rng は、閾値の変更などに使う。

これにより、同じ入力・同じ閾値配置なら、同じ行動列と得点を再現できる。

実際によく訪れる木を優先して変更する ​

閾値を変更しても、訪問しない木なら行動列に影響しない。そこで simulate() で記録した visit_count を使い、訪問回数が多い木ほど選ばれやすいようにしている。

cpp
// Solver::mutate() より抜粋
int total = 0;
for (int j = in.k; j < in.n; j++) total += s.visit_count[j];
if (total > 0) {
    int ticket = rng.randint(0, total - 1);
    for (int j = in.k; j < in.n; j++) {
        ticket -= s.visit_count[j];
        if (ticket < 0) {
            v = j;
            break;
        }
    }
}

この木の選び方は、無作為に木を選ぶよりも、現在の行動列に影響する変更を試しやすくする工夫。変更内容は次の4種類。

確率近傍操作内容
45%時刻をずらす±100..2500 手だけ移動し、0..T+100 に収める
40%時刻を再設定0..T+100 からランダムに選ぶ
10%変更を無効化T+100 にする
5%時刻を交換別の木と threshold を交換する

再設定することで大きな変更も試せる一方、時刻を少しずらす近傍では、良い変更タイミングを微調整できる。

焼きなましで閾値配置を最適化する ​

候補状態 nxt を作ったら、simulate(nxt) で 最大1万手の行動を最初から構築し直し、得点を求める。

cpp
State nxt = cur;
mutate(nxt);
nxt.score = simulate(nxt);
if (nxt.score > best.score) best = nxt;

double progress = min(1.0, timer.time() / TIME_LIMIT);
double temp = 5.0 * pow(0.03, progress);
int delta = nxt.score - cur.score;
if (delta >= 0 || rng.rand01() < exp(delta / temp))
    cur = move(nxt);

温度は経過時間に応じて指数的に下がる。

temp(p)=5.0×0.03p,p=min(1,elapsed1.92)

得点差を Δ=score(nxt)−score(cur) とすると、採用確率は次のとおり。

P(accept)={1(Δ≥0)exp⁡(Δ/temp)(Δ<0)

初期はある程度の悪化も受理し、終了に近づくほど改善を優先する。AHC014で使った固定閾値受理とは異なり、こちらは実際に乱数で受理を判定する、通常の焼きなまし法である。

探索中の最良状態は best に保存しておき、最後に simulate(best, &answer) を呼んで出力する。評価と出力で同じシミュレーションを使うため、別々のロジックを実装する必要がない。

この解法で押さえておきたいこと ​

この解法の核は、行動列を直接焼きなますのではなく、行動列を作る「方針」を焼きなますことにある。

  1. 変更時刻の閾値で探索空間を小さくする:各木の切り替え方針を90個の整数で表す。
  2. BFSでその方針を行動列へ変換する:未納品の味の並びを作れる経路を優先し、見つからなければ移動して仕切り直す。
  3. シミュレーションを決定的にする:同じ方針なら同じ得点になるようにし、焼きなましの比較を安定させる。
  4. 訪問頻度を近傍生成に使う:得点に影響しやすい変数を優先して変更する。

**「小さなパラメータ集合を最適化し、決定的な貪欲・探索で実際の解を構築する」**という形は、行動数が多いAHCの問題にも応用しやすい。