AtCoder Heuristic Contest 072

Somersault Slimes 解説

作問裏話: Astra 強すぎる…

ALE-Bench Leaderboard「Benchmark Results by Release Date」(sakanaai.github.io/ALE-Bench-Leaderboard、2026-10-05 時点)。右上の ★ が gpt-6-astra-max

作問裏話

8月に行った参加部門分けアンケート結果

8月に行った参加部門分けアンケート結果

問題

  • 下に k 匹残し、上の一団が反転して跳ぶ (l ≤ k+1)
  • 巣では一番上から帰巣 (出発点・着地点の両方)
  • 操作回数を最小化

011 匹ずつ巣に返す

  • 1 匹だけの塔は k = 0 → l ≤ 1
    • 1 マスずつしか動けない
  • 巣までの BFS 最短路で 1 匹ずつ運ぶ
    • 途中の塔には上に乗って通過すればよい
    • 他の色の巣に乗っても帰巣しない
  • 操作回数 = 巣までの距離の総和

ビジュアライザの入力はすべて seed=10

点

021 色ずつまとめて返す

  • 同じ色だけの一団は、反転しても色の並びが同じ
    → 塔ごとまとめて運べる
  • 色ごとに、巣を根とする BFS 木を作る
    • 遠いマスから順に、塔の上の同色部分を親へ 1 マス動かす
    • 合流しながら雪だるま式に大きくなる
  • 操作回数 ≈ 経路の和集合 (シュタイナー木) の辺数
  • 高さ 8 を超える分は次の周回で運ぶ
点

02b土台を使って 2 マス跳ぶ

  • 色 c を運んでいる間、他の色は元の位置に 1 匹ずつ残っている
  • その上に乗った一団は k ≥ 1 → 2 マス跳べる
  • 「土台のあるマスからは 2 マス」を含めた最短手数で木を作る
  • 数の少ない色から運ぶ (土台が長く残る)

ここまでは手順を人間が設計している
→ 足場・相乗りをもっと自由に使う手順を探索したい

点

03相乗り挿入: 1 匹ずつ「後から追加」する

  • 他のスライムの操作列を固定して、そこにスライム x を 1 匹追加する
  • 既存の跳躍の一団に乗れば 0 手 で移動 (相乗り)
  • x 自身の跳躍は 1 手
    他のスライムを土台にすれば遠くへ
  • 追加の手数が最小になる挿入を最短路で求める

03時空間で見る

挿入前 (x は単独で 5 手)
挿入後 (x は 3 手)

赤: x の新しい跳躍 (+1 手)

緑: 既存の跳躍に相乗り (0 手)

灰: 既存の跳躍

縦が時刻 (操作)、横が盤面の 1 行。
x は青を土台に 2 マス跳び、最後は青の一団と一緒に跳んで巣で帰巣

03状態と遷移

時刻 t の操作 e (k, 高さ h) で

  • 待つ: e がマス c に触れない 0 手
  • 残る: z ≤ k → e の k が 1 増える 0 手
  • 一緒に跳ぶ: z ≥ k → 反転して着地点の塔の z' = g + (h − z) へ 0 手
  • 上に一団が着地: z はそのまま 0 手

x が塔の一番上 (z = h) なら

  • 新しい跳躍: x だけで l ≤ h+1 跳ぶ 1 手
  • 下の h 匹 (他のスライム) が土台になる
  • 着地点の塔の一番上に乗る

注意

  • 帰巣を妨げない: 操作後に帰巣するはずのスライムより上に x (巣と違う色) が来るなら不可
  • ゴール: x が自分の色の巣の塔で一番上に出たら帰巣
  • 高さ 8: x がいる塔は元より 1 匹高い

03Tips

区間ごとにまとめると高速になる

  • 各マスの塔は、そのマスに触れない操作が続く間は変わらない → この時間帯を「区間」とする
  • 同じ (マス, 区間, z) には最も早く着いたものだけ残す (同じ区間なら待てば後の時刻と同じになる)
  • 新しい跳躍: x がいるマスの区間内ならいつでも跳べるが、着地点の塔はその間に変わりうる
    • 着地点の区間ごとに状態が決まるので、試す時刻は「今」と「着地点の塔が変わった直後」だけでよい

同色の連続部分をまとめる (正規化)

  • 同色のスライムは区別できない → x が同色の連続部分のどこにいても、色の並びは同じで以降の動きも同じ
  • 連続部分の一番上を代表にして 1 つの状態にまとめる
  • 遷移は連続部分のどこかでできればよい: 一番下 ≤ k なら残れる、一番上 ≥ k なら一緒に跳べる
  • 状態が減るだけでなく選択肢が広がり、手数が約 4% 減る (次ページ)

03Tips: 正規化が効く例

03初期解: 巣に近い順に挿入

  • 空の操作列から始め、巣に近いスライムから 1 匹ずつ挿入
    • 遠くのスライムほど、先に決まった経路に相乗りしやすい
  • 土台・相乗りの使い方を人間が設計しなくても、最短路が自動で見つける
  • 1 ケース 0.1 秒以下
点

04相乗り挿入による山登り

「相乗り挿入」は 1 匹ずつ足して完成形を作るだけでなく、完成形を崩して修復するのにも使える

現在の操作列
→
1 匹 y を取り除く他の動きは保ち k を詰める
→
y を挿し直す03 の最短路
→
手数が増えなければ採用同じ手数の付け替えも採用
  • 取り除くのはランダムな 1 匹 y
  • 同じコストの経路はランダムに選ぶ → 付け替えの行き先が広がる

例: 赤は青より先に挿入されたので、そのときの青の塔は低く 3 マスしか跳べなかった。後から青が加わり塔が 4 匹に → 挿し直すと 5 マス跳んで巣へ

04y が土台だったら

04山登りの結果

点

05破壊再構築 (LNS) + 焼きなまし

  • 04 の問題点: 同じ色は塊になって動く
    • 1 匹だけ取り除いても、同じ塊に乗り直すだけで解がほとんど変わらない
    • 挿し直しの約 6 割は元とまったく同じ操作列に戻る
  • → 1〜6 匹をまとめて取り除いて、1 匹ずつ挿し直す (破壊再構築)
    • 匹数は毎回ランダム
    • ランダムな起点から、初期位置が近い / 同色 / 連続する数手で跳ぶ のどれかで選ぶ
  • 複数匹だと手数が増える挿し直しもよく起きる → 焼きなましで受理
    • 山登りより約 1% 手数が減る

Tips: 採用の閾値を先に決めると高速になる

  • 許容値 = 現在の手数 − 温度 × log(乱数) を、挿し直す前に決める
  • 挿し直しの 0-1 BFS は、手数が許容値を超えた時点で打ち切れる
  • 判定結果は通常の焼きなましと同じ

05足場の予約

  • 数匹を取り除くと、足りなくなった土台を誰が埋めるか決まらない
    • 04 では取り除くのが y だけなので、y が埋めればよかった
  • → 土台が足りない操作ごとに、埋めるスライムを指定しておく (足場の予約)
  • 予約したスライムは、04 の y と同じ制約で挿し直す

05予約付きの挿入

取り除くとき: 予約を作る

  • 土台が足りなくなった操作 e もそのまま残す
    • 不足 = その跳躍で足りない土台の匹数 l − (k+1)
  • 不足の匹数だけ、予約するスライムを指定する
    • 取り除いたスライムのうち、e で切れ目より下にいたもの (上から順に)
    • 元はそこにいたので、挿し直しで同じ位置に入れる見込みが高い
  • 予約したスライムがその不足を埋めると決めておけば、04 と同じ方法で挿し直せる

挿し直すとき: 予約を守る

  • 予約を持つ x は、時刻 e に e の出発点の切れ目より下にいなければならない
    • e をまたいで他のマスで待てない、e で一緒に跳べない
    • 最後の予約が済むまで帰巣できない
    • 状態に「何個目の予約まで済んだか」を加える
  • 他のスライムが代わりに切れ目の下に入って不足が埋まれば、予約は消える
  • 全員を挿し直しても埋まらない予約が残れば不採用
点

05 から writer解までの細かい要素

要素ひとことで手数の減少
取り除き方を増やす合流点・経路の交差・一緒に跳ぶ仲間でも選び、手数を食っているスライムを優先0.9%
同コスト経路の取り出し順0-1 BFS の同じコストの段を、ランダム / 早い時刻 / 遅い時刻 優先で取り出す0.3%
実装の改善高速化と、初期解を複数回作ること2.8%
同色の入れ替え取り除くときに同色の仲間と役割を交換し、土台不足を作らない0.2%
帰巣保留巣の上に別の色が乗って帰巣を止め、巣の色のスライムを一時的な土台にする0.7%
接尾辞の再計画途中の盤面から、同色の塊を 1 つの荷として後半だけ運び直す1.0%
writer解: 点

取り除き方と経路の選び方

取り除き方を増やす (0.9%)

  • 05 の「近い / 同色 / 連続する数手」に加えて
    • 同じマスに触れる操作で跳ぶスライム: 合流・分岐の拠点を通る一団をまとめて組み替える
    • 跳躍の経路が交わる操作で跳ぶスライム
    • 起点と同じ塔で一緒に跳ぶ仲間
  • 起点は半分の確率で負担の大きいスライム
    • 負担 = 各操作の 1 手を一緒に跳ぶ匹数で割り、跳んだスライムに配った合計
    • 単独で動きがちな「手数を食っている」スライムを優先して組み替える

同コスト経路の取り出し順 (0.3%)

  • 最短の挿し方はたくさんあり、どれを返すかで次の解が変わる
    • 受理の大半は手数が変わらない付け替え
  • 0-1 BFS の同じコストの段から取り出す順を、挿入ごとに選ぶ
    • ランダム (2/3)
    • 早い時刻優先 (1/6): 早めに動く経路が出やすい
    • 遅い時刻優先 (1/6): 待ってから動く経路が出やすい
  • 経路の傾向がばらつき、付け替えの行き先が広がる

実装の改善と同色の入れ替え

実装の改善 (2.8%)

  • 反復回数がそのまま効く: 本解説の実装 (上 2 行まで) に 2 倍の時間を与えると 1.8% 減る
  • writer解の高速化
    • 新しい跳躍なし (追加 0 手) で挿し直せるかを、先に専用の高速な判定で調べる
    • 探索の作業領域を使い回し、毎回の初期化を省く
    • 塔の色を 4bit ずつ詰めて 1 つの整数で持つ
  • 挿入の順序を変えて初期解を複数回作り、最良から始める

同色の入れ替え (0.2%)

  • 取り除くスライム y が切れ目より下にいて、同じ色が切れ目の上まで続いているとき
  • y と、一緒に跳ぶ同色の仲間の役割を入れ替えて取り除く
    • 色の並びは変わらない (同色は区別できない)
    • y は跳ぶ側として抜けるので、土台不足 (予約) を作らずに済む

帰巣保留 (0.7%)

接尾辞の再計画 (1.0%)

スコアの推移

動きの比較