目次

AtCoder Heuristic Contest 072「Somersault Slimes」に参加した。最終結果は 41 位で、提出は 27 回であった。

解法は、1 手ビームサーチか配送計画焼きなましで初期解を作り、入れ直し LNS で縮めるというものである。入れ直し LNS は、操作列そのものを解として持ち、スライムを数匹抜いて、1 匹ずつ最適な経路で入れ直す局所探索で、スコアのほとんどはここから来ている。

この記事では、問題の性質と解法に加えて、AI との取り組み方と、入れ直し LNS に辿り着くまでに時間がかかった理由を書く。

なお、この記事は、Claude Code が作業ログとソースコードから起草したものを、私が推敲している。数字は全て測定記録から引いた。

問題

問題の詳細は、公式ページへ。

• 盤面: $N \times N$ のマス目（$12 \le N \le 20$）で、各マスは床か壁。床の上に $K$ 色（$4 \le K \le 12$）のスライムが合わせて $M$ 匹いる（手元の入力では 13〜217 匹）。色ごとに巣が 1 マスある。
• 塔: スライムは同じマスに 8 匹まで重なれる。色が違っても重なれる。
• 操作: 高さ $h$ の塔の上側 $m$ 匹（一団）が、上下左右のどれかへ $\ell$ マス跳び、上下の順を反転して着地点の塔の上に重なる。途中の塔は飛び越えて良い。着地後の高さは 8 以下でなければならない。
• 飛距離: 下に残す $k = h - m$ 匹を、この記事では土台と呼ぶ。跳べるのは $\ell \le k + 1$ マスまで。飛距離の上限を決めるのは、跳ぶ一団の大きさではなく、足元に残す匹数である。
• 帰巣: 自分の色の巣のマスで塔の一番上に来たスライムは、自動で盤面から取り除かれる。操作回数には数えない。一番上に別の色が乗っていると、その下の同色は帰れない。
• スコア: 操作回数を $T$、最後に盤面に残った匹数を $E$ として、絶対スコアは $T + 100000 \times E$（小さいほど良い）。順位は相対評価で、各ケースの「全参加者の最小の絶対スコア / 自分の絶対スコア」の和で決まる。全員を帰すのは前提で、その上で $T$ を減らすゲームになる。
• 実行時間とテスト: 制限は 2 秒。暫定テストは 50 ケース、システムテストは 2000 ケース。

良い問題だったと思う。長期の AHC というと、問題が複雑で、最適化する箇所が複数あるという印象がある。しかしこの問題はルールがシンプルで、高さの限られた塔と跳躍、反転という要素だけで、問題をずっと奥深いものにしている。

問題の性質の分析

解法を考える上で重要だった性質は、次の 4 つである。

1. 相乗りするほど得になる。 一団は何匹いても 1 手で運べるので、同じ方向へ行くスライムを重ねて一緒に運ぶ（以下相乗り）ほど操作回数が減る。色が違っても重なれるので、相乗りの相手は同色に限らない。
2. 土台があると遠くへ跳べる。 飛距離は足元に残す匹数で決まるので、1 手で運べる量は $m \cdot \ell \le m(9 - m) \le 20$ となり、「1 匹を 8 マス」から「8 匹を 1 マス」までの幅がある。他のスライムの上に乗ることは、相乗りだけでなく跳躍の準備にもなる。
3. 良い手順は、一時的な悪化を含む。 相乗りや跳躍のためには、いったん巣から遠ざかって別の塔に合流したり、仲間が来るのを待ったりする必要があり、その得は数手後にまとめて返ってくる。そのため、目の前の 1 手の良し悪しを評価するのが難しい。
4. 塔の中の順序が干渉する。 塔は後入れ先出しで、しかも跳ぶたびに上下が反転する。相乗りさせたい 2 匹の間に行き先の違うスライムが挟まると一緒に跳べず、巣の上に別の色が乗ると下のスライムが帰れない。誰と誰を一緒に運ぶかは、道だけでなく、いつ・どの順で重なるかまで決めないと実現しない。

長期間取り組む中で、解法クラスを 1 手ビームサーチ → 配送計画焼きなまし → 入れ直し LNS と、大きく変えてきた。その度に、それまで扱えていなかった性質を扱えるようになった。それぞれが 4 つの性質を扱えるかどうかをまとめると、次のようになる。

性質	1 手ビームサーチ	配送計画焼きなまし	入れ直し LNS
1. 相乗り
2. 土台と跳躍
3. 一時的な悪化
4. 塔の中の順序

1 手ビームサーチは、相乗りを評価できるのが同じ色だけで、一時的な悪化は評価できない。配送計画焼きなましは、土台の確保と塔の中の順序を実行器の規則に任せている。入れ直し LNS だけが 4 つ全てを近似なしで扱える。最終的には、これら 3 つを組み合わせたものが最良となった（詳しくは次の章）。

暫定テスト（50 ケース）の絶対スコアの合計で比べると、次のようになる。

解法	絶対スコア
1 手ビームサーチ	12888
配送計画焼きなまし	12220
入れ直し LNS（初期解は貪欲）	10243
3 つの組み合わせ（最終提出）	9947

上の 2 行は、それぞれを単独で使っていた時期の最良の提出である。「入れ直し LNS（初期解は貪欲）」の行は、最終提出の初期解を、スライムを 1 匹ずつ巣まで歩かせるだけの貪欲に差し替えたもので、コンテストの終了後に提出した。

1 手ビームサーチも配送計画焼きなましも使わなくても、最終提出との差は 3% に収まるので、スコアのほとんどは入れ直し LNS が出していることになる。ただ、この 3% は小さくない。入れ直し LNS を一通り調整した後は、色々試してもはっきり効く改善がほとんど見つからなかったので、その中で、初期解でスコアが 3% 向上するというのは大きかった。

それぞれのクラスが最終的に活かしあって最良の解を生んだことは偶然だが、取り組みが報われたという意味では印象深いものになった。

解法

0. 全体の形

制限 2.0 秒のうち 1.9 秒を使って、最初の 25% までで全員が帰巣する初期解を作成し、残り時間で入れ直し LNS で縮める。

初期解の作り方は $M$ の大きさで 1 手ビームサーチと配送計画焼きなましに分けている。1 手ビームサーチは大きな盤面でもそれなりに良い解を速く出すことができた。配送計画焼きなましは 1 手ビームサーチよりも良い解が出せるが、$M$ が大きいと探索に時間がかかってしまっていた。

最終提出の解は、例えば次のようになる。seed 4 のケースで、操作回数は 239 手である。1 位の解法の動画で使われているケースなので、同じものを選んだ。

1・2 節で初期解の作り方を、3 節で入れ直し LNS を説明する。

1. 1 手ビームサーチ

大きな $M$（$> 60$）に対して短い時間でそこそこ良い初期解を出す。状態は盤面、遷移は合法な 1 手とし、同じ盤面は除いている。工夫のほとんどは評価関数にある。

評価関数

塔の中で同じ色が連続している部分を run と呼ぶ。評価関数は、同じ色の巣までの距離 $d$ をもとに、残りの操作回数を見積もる。

合流と跳躍という要素があるので、1 手ずつ評価するビームサーチには限界がある。いったん評価が悪くなり、その後大きく良くなる手順を、今の盤面から評価するのは難しい。そのため粗い評価にはなってしまうが、次のような性質を満たしているとまずまず上手くいく。

1. 同じ色を重ねると、評価が良くなる。 重なって 1 つの run になった同色は、何匹いても 1 手で運べる。
2. 色ごとに、遠い run ほど重く数える。 1 色だけなら、いちばん遠い run が途中の同色を取り込みながら帰るのが最適で、操作回数はほぼその run の距離になる。近い run の距離は、遠い run ほどは操作回数に効かない。
3. どの run を進めても、評価が動く。 いちばん遠い run しか見ないと、他を進める手が全部同点になり、探索が詰まる。
4. 跳ぶための準備が、進んだ手に見える。 他色の塔に乗って土台を得た run は、距離は縮んでいないが、次の 1 手で遠くへ跳べる。
5. 高速に計算できる。 速く計算できる分、幅を確保することができて、一時的に悪化した盤面を拾うことができる。

色々試して最終的にたどり着いたのが次の評価関数である。小さいほど良い。

$$\mathrm{eval} = \sum_{c} 3 \ln \sum_{\mathrm{run} \,\in\, c} \exp\!\left(\frac{d'}{3}\right) \;+\; \frac{1}{16} \sum_{\mathrm{slime}} d$$

ここで $d'$ は、今の塔からの跳躍を考慮した距離である。

$$d' = d - \min(b,\ r - 1)$$

$b$ は run の下にいる匹数、$r$ は巣へ向かって一直線に進める長さ。土台が $b$ 匹あれば次の 1 手で $\min(b + 1,\ r)$ マス進めるので、1 マスずつ進むのに比べた得を先に引いている。

5 つの性質は、式では次のように実現している。

性質	式での実現
1. 重ねると良くなる	匹数ではなく run について和を取る
2. 遠いほど重く数える	最大を滑らかにしたもの LSE（LogSumExp）を色ごとに取る
3. どれを進めても動く	LSE なので、距離の小さい run にも勾配が残る。また、第 2 項で $d$ を小さな重みで足す
4. 跳ぶ準備が進歩に見える	$d$ の代わりに $d'$ を使う
5. 高速に計算できる	1 手で変わるのは出発と着地の 2 マスだけ。色ごとの $\sum \exp$ と第 2 項を持っておき、その 2 マスの分だけ足し引きする

ビーム幅の決定

前述の通り幅は広いほど良いが、そもそも盤面から手数を予想するのが困難なので、幅をどれほど広げれば良いか分からない。序盤から終盤にかけて広い範囲で悪化を許す盤面を拾う必要があり、序盤だけ広げたり調節したりすることも上手くいかない。chokudai サーチは幅を決めずに時間いっぱい回すことができるが、良い評価の子で埋め尽くされてしまって下位の評価が拾えない。

しかし、このビームは本命ではなく、入れ直し LNS にそこそこ良い初期解を与えられれば良い。解に到達するまで探索を続けるとき、その時間はだいたい $M^2$ に比例するので、幅を次の式で $M$ によって決めてしまう（下限 3）。

$$w = \mathrm{round}\left(\frac{405000}{M^2}\right)$$

探索時間が結果的に短くなったとき、ビームが本命なら探索不足の損が生まれたということになるが、初期解を与えるだけの場合はむしろ、入れ直し LNS の探索時間が増えるということなので許容できる。

解が出なかったときの保険

ビームサーチが全員を帰す解に届かないケースが、手元の 8500 ケースの 0.46% にある。そのときは、その場で配送計画焼きなまし（2 節）へ回す。

原因は時間切れではなく、評価関数の谷だった。幅 1 の通路で、高さ 8 の塔（空きマスにしか降りられない）と隣のスライムが向かい合って動けなくなる。ほどく手（塔を割る・隣が退く）は評価をはっきり悪くするので選ばれず、関係のない数匹を行き来させる手だけが選ばれ続けて、深さの上限まで歩いていた。

回った先の配送計画焼きなましには、初期解に割り当てた時間の残りしか渡らない（その 1〜6 割で、中央値は 4 割）。それでも、該当の 39 ケース全てで全員を帰す解が出た。初期解は粗いが、その後の入れ直し LNS で大きく縮む。

2. 配送計画焼きなまし

小さな $M$（$\le 60$）に対して、1 手ビームサーチよりも良い初期解を出す。

計画の表現

前述の通り、1 手ビームサーチでは、いったん遠ざかって別の塔に合流するような手順を拾うのが難しい。そこで、誰と誰がどの区間を一緒に行くかを先に決めてしまうことにして、解を操作列ではなく計画として持つ。

計画は、各スライムについての跳び $(q, v, \ell, p)$ の連続した列である（$q$: 出発マス、$v$: 向き、$\ell$: 長さ、$p$: 優先度）。同じ $(q, v, \ell)$ の跳びは同じ $p$ を共有する。以下、この列を道と呼ぶ。

例えば下の盤面で、同じ色の a と b を巣へ帰す計画は次のようになる。

	道（跳びを「$q$ $v$ $\ell$」で書き、$p$ は省いた）
a	(1, 0) 右 1 → (1, 1) 右 1 → (1, 2) 右 1 → (1, 3) 右 1
b	(0, 1) 下 1 → (1, 1) 右 1 → (1, 2) 右 1 → (1, 3) 右 1

太字の 3 つの跳びが a と b の道に共通しているので、ここで相乗りすることになる。

計画には「いつ動くか」が入っていないので、操作列に直すための規則が別に必要で、これを実行器と呼ぶ。実行器は毎手、各塔の一番上にいる「次の跳びが同じスライムの連なり」を一団の候補として、「同じ跳びを通る仲間が揃っているか → 優先度 → 匹数」の順で 1 つ選んで動かす。土台が足りないときは跳びを短くするので、どんな計画からでも合法な操作列を作ることができる。

上の例だと、(1, 1) に着いた a は b を待ち、b が上に乗ってから 2 匹で 3 回跳ぶので、別々に帰ると 8 手かかるところが 5 手で済む。

焼きなましのコストには、実行器が出した操作列の長さ $T$ をそのまま使う。

近傍

初期の計画は各スライムの最短路とし、次の 4 種類の近傍で焼きなます。

近傍	動かす単位
道を引き直す	1 匹
優先度を ±1 する	跳び 1 つ
同じ向きに続く 1 マスの手を 1 回の跳びにまとめる（とその逆）	その区間を一緒に通る全員
ある区間を別の道へ付け替える	その区間を一緒に通る全員

色々試したが、効いたのは下の 2 つのように、一緒に動いているスライムをまとめて動かす近傍であった。1 匹の道だけを変えると相乗りの相手を置いていってしまい、さらに実行器の選ぶ手が全体でずれてしまうので、ほとんど改善しなかった。

小さい $M$ でしか使わない理由

計画を評価するたびに実行器で操作列を作り直すので、$M$ が大きいほど探索に時間がかかってしまう。

$M$ が 61〜110 のケースで比べると、初期解だけを見れば配送計画焼きなましの方が良い。しかし、入れ直し LNS を始められるのが、締切までの時間の 25% が過ぎた時点と 9% が過ぎた時点と大きく違うので、入れ直し LNS まで掛けた後は 1 手ビームサーチの方が良くなった。この差は $M$ が小さいほど縮んでいき、46〜60 では差が無かったので、境目を 60 とした。

3. 入れ直し LNS

1 手ビームサーチまたは配送計画焼きなましで作った初期解を、残り時間いっぱいまで縮める。この解法の本命である。

問題の性質の分析でまとめた通り、4 つの性質を全て近似なしで扱えるのが強みである。

全体の流れ

ここからは計画も実行器も使わず、操作列そのものを解として持つ。コストは操作列の長さである。次の試行を、時間いっぱいまで繰り返す。

1. スライムを $R$ 匹選び、操作列から抜く。
2. 抜いたスライムを無作為な順に 1 匹ずつ、追加の操作回数が最小になるように入れ直す。
3. 全員を入れ終えた操作列の長さによって、受理するかどうかを決める。

抜き方

操作列を「どのマスから何匹跳ぶか」ではなく「どのスライムが跳ぶか」で読み替えておくと、スライム $x$ を操作列から抜くことができる。$x$ だけが跳んでいた手は消え、$x$ が相乗りしていた手は $x$ 抜きでそのまま残る。これを残りの操作列と呼ぶ。

1 匹だけを抜いて入れ直すことを繰り返すと、すぐに止まってしまう。相乗りしている 2 匹の片方だけを抜いても、残った方がその手を使い続けるので、手が消えないためである。そこで $R$ 匹をまとめて抜く。

抜く相手は、無作為に選んだ 1 匹と、その 1 匹と同じ手で一緒に跳んだことのあるスライムから選んだ $R - 1$ 匹とする。無作為に選ぶよりも初期位置が近いスライムを選ぶ方が良く、それよりも一緒に跳んだことのあるスライムを選ぶ方が良かった。配送計画焼きなましの近傍と同じで、まとめて動かすべきなのは、近くにいるスライムではなく相互作用したスライムである。

$R$ は、入れ直し LNS の時間を 3 等分して 7 → 6 → 5 と下げていく。$R$ が大きいほど 1 回の受理で大きく縮むが、1 回の試行が重く、受理されないことも多いので、後半は小さい $R$ で回数を稼ぐ方が良かった。

入れ直し方

残りの操作列は固定したまま、$x$ を初期位置から巣まで運ぶ経路のうち、追加の操作回数が最小のものを動的計画法で求める。$x$ の状態は「どのマスにいて、自分の上に何匹乗っているか」だけで足りるので、残りの操作列を前から 1 手ずつ進めながら、各状態に着くまでの最小の追加回数を更新していけば良い。

$x$ のいる塔から一団が跳ぶとき、$x$ に起きることは $x$ の位置で決まる。

• 一団より下にいれば、その場に残る（上の匹数が減る）。
• 一団のすぐ下にいれば、残っても良いし、一団の最下段として一緒に跳んでも良い。跳べば反転するので、着地後は一番上になる。
• 一団の中にいれば、そのまま運ばれる。
• 一番上にいれば、いつでも自分だけで跳ぶことができる。足元の全員が土台になるので、遠くまで跳べる。

既にある手に乗るのは無料で、追加の 1 手になるのは $x$ が自分で跳ぶ手だけである。そのため、相乗りできる手があれば、それに乗る経路が自然に選ばれる。

合法な操作列になるように、次の 3 つを入れている。

• 土台の確保: $x$ を抜くと土台が足りなくなる跳躍が残りの操作列にあるとき、その時刻に $x$ がその土台にいることを経路の必須条件にする。何匹も抜いた途中では、土台が足りない跳躍をいったん許して不足を記録しておき、後から入れるスライムで埋めていく。埋めきれなければその試行は捨てる。
• 巣を塞ぐ形の制限: $x$ が巣のマスで、そこで帰巣するはずのスライムの上に乗る形は、すぐに自分で出ていく場合だけ許す。このとき、塞がれて下に残っているスライムも土台に数えて跳ぶことができる。
• 最後の検査: 出力する操作列は公式と同じ規則で 1 手ずつ再生して作り、1 手でも不正であればその試行は捨てる。

受理の条件

操作列の長さが元と同じ場合も受理する。長さが変わらなくても、誰がどの手に乗っているかは変わるので、それが別のスライムにとっての乗れる手を作るためである。

さらに $M \le 110$ では、元より 1 手多い結果も受理する。小さいケースでは、同点の受理だけでは局所解に辿り着いて出られなくなってしまうためである。ただし、1 回の受理で縮むのはほとんどが 1 手なので、悪化をたくさん許してしまうと、良い方向にも進んでいかなくなる。そこで、悪化の許し方を次の 2 つで絞っている。

• 確率: 悪化を許すのは試行の 40% だけで、残りの 60% は元以下の場合だけ受理する。
• 深さ: 今の操作列がこれまでの最良より 1 手多いときは、悪化を許さない。つまり「最良」と「最良 + 1 手」の間だけを歩く。

確率は 40% まで上げるほど良くなり、それ以上は変わらなかった。深さを「最良 + 2 手」まで広げても良くはならず、全ての試行で悪化を許した上で広げると少し悪化した。

悪化の受理は $M$ が 60 以下でははっきり良くなり、61〜110 でも少し良くなったが、111 以上では逆に悪化した。大きいケースは試行の回数がそもそも足りておらず、悪化を受理すると、その足りない試行をさらに寄り道に使ってしまうためである。

操作列の並べ替え

操作列には、解としては同じなのに順番だけが違う書き方がたくさんある。触るマスが重ならない 2 手は、どちらを先に書いても盤面の進み方が変わらないためである。

一方で、入れ直しの動的計画法は残りの操作列を書かれた順に進めるので、$x$ が乗れるのは、$x$ がそのマスに着いた時点よりも後ろに書かれている手だけである。関係のない遠くの手がたまたま先に書かれているだけで、「相手が少し待ってくれれば乗れる」相乗りが見えなくなってしまっていた。

そこで、試行 100 回ごとに操作列を並べ替える。同じマスに触る手どうしの前後は保ったまま、他の順番を無作為に入れ替えるので、操作回数も各マスで起きることの順序も変わらず、動的計画法から見える「乗れる手」だけが変わる。同点の受理と同じで、操作回数を変えずに解の見え方だけを動かす手段が 1 つ増えたことになる。

取り組み方

生成 AI の利用規約

このコンテストでは生成 AI の利用規約（20250616 版）が定められており、要点は次の通りである（問題文が指定していた指示文を、こちらで訳して 3 点に絞ったもの）。

• 解答プログラムを実行した後、その実行結果に基づいて解答・方針・コードを改変したり改善したりしてはならない ── 利用者が新しく明示的に指示した場合を除く。
• 実行結果・ログ・スコアなどを報告することはできる。ただし報告したらそこで停止し、利用者の新しい指示を待たなければならない。
• ここでいう「解答プログラム」は、この問題を解く目的で作られた（作りかけの）プログラム全てを指す。人が書いたか生成 AI が書いたかは問わない。

そのため、エージェントに「回して勝手に良くしておいて」と任せることはできず、「走らせる → スコアを見る → 次の一手を決める」というループを、毎回人間が閉じる必要がある。

使った AI

使った AI は次の 3 つである。

• Claude Code（Opus 5.5）: 実装・測定・集計など、普段の作業は全てこれに任せた。性能が良く、トークンの消費も少ない。Max の 5 倍プランで、5 時間ごとの制限も週の制限も全く気にする必要がなかった。測定の待ち時間が長く、並列にも回せず、規約上 AI を回しっぱなしにもできないので、そもそも使う量がそれほど増えないという事情もある。
• Claude Code（Fable 5.1）: アイデア出しにたまに使った。トークンの消費が大きいので、作業はさせていない。
• ChatGPT（GPT-5.6 Sol）: これもアイデア出しに使った。敢えてエージェント型ではなくチャット型の AI を使い、作業の文脈から離すことで、別の視点のアイデアをもらうことができる。

AI との進め方

AI と取り組む上で、決まりとして実践していることは次の 6 つである。

1. 実装と測定は AI に任せ、採否は自分で決める。 AI が出した案であっても、試すかどうか、採るかどうかは必ず自分で判断する。
2. 測る前に、設計と判定の線を書いて固定する。 何を測り、どうなったら採用するのかを先に決めておくと、結果を見てから都合よく解釈することがなくなる。測定の段取りが固定されていれば、寝ている間に実装から測定までを任せることもできる。
3. 現在地の 1 枚と、追記だけの測定記録を分けて持つ。 AI は会話が長くなると前の文脈を失ってしまうので、今どこにいて次に何をするのかを 1 枚にまとめておき、毎回そこから始める。測定の結果は別のファイルに追記していき、書き換えない。
4. 効かなかった案は、何が無い状態で効かなかったのかまで残す。 今回の入れ直しは、以前のコンテストで「後処理として載せたら悪化した」と記録していた手法である。前提が変われば結果も変わるので、否定は前提と一緒に残しておく。
5. 定期的に、可否の判定の式を問題文と並べて読む。 問題文よりも狭い条件を課してしまう失敗は、全ての版に共通しているので、版どうしの比較には現れない。
6. AI の解釈は疑って読む。 過去の記録や手法を引いてきたり、選択肢を広く並べたりするのは AI の方が得意で、そこには大いに助けられている。一方で、AI は一度立てた解釈や設計を前提にして、次の測定を積んでしまうことがある。測定の数字は合っていても、その読み方が合っているとは限らない。今回も、「それは変ではないか」という違和感から指摘して、分析や設計が直ったことが何度もあった。

作業の土台

上の決まりは、自作のテンプレート WaTeR-7/ahc-template（CC0）に、AI エージェント向けの作業規約としてまとめてある。他に、掃引・同一ケースどうしの比較・出力の一致照合のスクリプト一式と、過去回の知見置き場が入っている。

振り返り

入れ直しに着手したのは 10/2 で、10 日間のうち 6 日あまりが過ぎていた。前述の通り、その 6 日間で作り込んだものは、初期解として最終的なスコアを 3% 向上させている。この 3% は小さくないのだが、かけた時間には見合っていない。ここでは、なぜそこまで時間がかかったのかを振り返る。

日付	出来事
9/26 未明	最短路で相乗りさせる貪欲を作ったが、計画した相乗りの 44% しか実現しなかった。原因は、到着のずれと塔の中の順序であった
9/26	小さな盤面を厳密に解いて調べると、距離をもとにした評価のビームサーチがほぼ最適であった。これを見て 1 手ビームサーチへ進んだ
9/28 朝	計算量を 16 倍にしても上位に届かないことを確かめた。しかし、その後の 2 日間も評価関数の改良を続けた
9/30 朝	配送計画焼きなましへ方針を変えた
10/1 夜	配送計画焼きなましも、時間を 256 倍にしても上位に届かないことを確かめた
10/2 未明	次の解法クラスの候補を並べ、入れ直しに着手した

最初の診断の読み方

9/26 未明の「到着のずれと塔の中の順序で、相乗りが実現しない」という診断は、問題の性質 4 そのものである。入れ直し LNS が解いたのも、この問題であった。しかし当時は、これを「貪欲では足りないので探索にする」と読んでしまい、順序を正確に扱える表現を探す方向には進まなかった。

小さな盤面での検証

1 手ビームサーチへ進む根拠になったのは、小さな盤面でほぼ最適な解が出たことである。しかし小さな盤面では、一時的な悪化を含む長い手順（性質 3）がほとんど必要にならない。そのため、1 手ビームサーチの弱点が検証に現れていなかった。

届かないと分かった後の 2 日間

9/28 に上位へ届かないことを確かめた後も、評価関数の改良を 2 日間続けた。この間もスコアは伸びていたので、やめる理由が見えにくかった。

もう 1 つの理由は、1 手ビームサーチが原理上は全ての手を検討していることである。そのため、評価さえ上手くできれば上手くいきそうに感じてしまう。下位の盤面を拾うために、幅を 2 つに分けて別々の基準で残す、複数の手をまとめて評価の谷を飛び越える、といった案を次々に試したが、どれも同じ時間では差が出なかった。

一方で、配送計画焼きなましから入れ直しへの乗り換えは早かった。10/1 の夜に届かないことを確かめ、その数時間後には次の解法クラスの候補を並べている。入れ直しはその中の本命であった。

学び

• 上位に届かないと確かめたら、その日のうちに次の解法クラスの候補を並べる。 同じクラスの中の改良は、候補を並べた後に回す。スコアが伸びている間は、今のクラスに留まる理由がいくらでも見つかってしまう。
• 解法クラスの候補は、問題の性質をどこまで近似なしで扱えるかで比べる。 「問題の性質の分析」の表を書いたのは、コンテストが終わった後であった。最初の 2〜3 日で書いていれば、操作列をそのまま持つ表現に、もっと早く目が向いたはずである。
• 小さな盤面で確かめた結論には、「小さな盤面では」という前提を付けて残す。 大きな盤面でしか現れない性質は、小さな盤面の検証には写らない。
• AI の提案が理解できないときは、小さな具体例を出させてから採否を決める。 配送計画焼きなましは早い段階から何度も提案されていたが、何が起きるのかがよく分からなかったので避けてしまい、他の案を潰し終えて、最後に残ってから着手した。理解できない案は、良し悪しに関係なく採られない。2 匹だけの盤面で実際の操作列まで出させていれば、数分で判断できたはずである。

おわりに

素朴な感想としては、AI のおかげで勝てた、ということに尽きる。自力で挑んだ短期の AHC071 は散々な結果だったので、今回の順位は AI と組んだからこそのものである。

私の場合、実装や測定の地力が足りないので、自力では時間の大部分をそこに割くことになってしまい、解法の改善という本質的な部分に取り組めない。今回は実装と測定を AI が引き受けてくれたので、問題の性質や次の一手を考えることに時間を使うことができた。

AHC での AI の使用が今後どうなるのかという話で持ちきりだが、私としては、AI と組めば勝てるので、AI 部門は残してほしいと思っている。

追記（2026/10/13）

10/13 ALGO ARTIS 様より、順位抽選賞として、¥5,000 をいただきました。競技プログラミングにおいて賞金を獲得するのは初めてのことであり、大変光栄に思います。ありがとうございました。