動画解説： https://www.youtube.com/watch?v=9zGsw2qkYw0

公式解説の writer 解（逆向きビームサーチ）とほぼ同じ枠組みです。以下では、writer 解と違う点を中心に書きます。

writer 解との違い

1. 魔法陣の初期配置を決めずに始める

writer 解では、逆向きの初期状態として目的地から 3 個を選ぶ組合せを列挙しています。私の解では、最初は 3 個とも「未使用」のまま始めます。

• 未使用の魔法陣は、初めてワープ先に使うときに「目的地のそば（偶奇を合わせた最寄りの点）に置いてあった」ことにして、そこへワープします。
• 未使用の魔法陣は互いに区別がないので、遷移では 1 つだけ試します。
• 最後まで使わなかった魔法陣は、適当な位置に出力します。

こうすると、どこに置くかを決めるのを「実際に必要になったとき」まで遅らせられます。初期状態の候補を列挙する必要もありません。

2. 評価値は手数だけにして、代わりに重複除去を粗くする

評価値は「ここまでの手数」だけで、見込み手数は入れられませんでした。

その代わりに効いたのが、重複除去の粗さです。3 個の魔法陣の位置を 8 × 8 マスのブロック単位に丸め 、ソートしたものをキーにして、同じキーの状態は手数が最小のものだけ残します。writer 解は座標を 2 で割っているので、それよりかなり粗い丸めです。

位置をそのまま使う場合と比べると、4 × 4 ブロックにして +33 点、さらに 8 × 8 ブロックにして +32 点ほど伸びました。16 × 16 ブロックまで粗くすると悪化しました。

writer 解では重複除去の効果は小さいようです（除かないと 150 ケースで約 3,400 点減）。一方、私の解では丸めを粗くするだけで 1 ケースあたり 60 点ほど伸びました。見込み手数を入れていない分、似た配置の状態がビームを食い合いやすく、多様性の確保が効いたのかもしれません。

3. 遷移の枝刈り

遷移は writer 解と同じく、ワープを最大 3 回続ける操作列を DFS で列挙します。ただし、40 通りすべては試さず、次の 2 つの枝刈りを入れています。

• 目的地までの距離が 8 以下になったら、それ以上ワープを試さない。
• その時点の最良候補の手数 + 50 を超えた枝は打ち切る。

ワープの上限を 2 回や 4 回に変えると、いずれもスコアが下がりました。ビーム幅は 2200 で、ビームサーチは手元で 0.8 秒ほどです。

4. 山登りによる後処理

残り時間で、得られた解を山登りで改善します。コンテスト中に実装が間に合わなかったため、近傍は 1 種類です。

• 順向きで見た転移 \(J\)（出発点 \(p\)、中心 \(m\)、着地点 \(q = 2m - p\)）を 1 つ選びます。
• \(m\) を保ったまま、出発点を \(p + d\)、着地点を \(q - d\) にずらします（\(d\) は 8 近傍）。
• \(J\) の出発点に残る魔法陣も \(p + d\) にずれるので、同じ魔法陣を次に使う転移は、出発点はそのままで着地点が \(2d\) ずれます。
• 移動量 0 になった転移は削除します。

手数が真に減るなら採用します（なおこれは良くないです。詳細は後述）。ビームサーチでは偶奇合わせの歩き方などを決め打ちしているので、それを局所的に直す形になります。平均約 40 手（≒ 40 点）減りました。

コンテスト中の進め方

時刻	内容	手元平均
15:47	逆向きビームサーチの骨格（ワープは未使用の魔法陣のみ）	467
16:29	使用済みの魔法陣へのワープも使う（1 区間 1 回まで）	7,089
17:08	1 区間でワープを最大 3 回続ける（DFS）	7,786
18:04	重複除去の丸め・パラメータ調整	7,885
18:22	山登りを追加	7,927
18:58	実行時間の調整（最終版）	7,919

• 逆向きに見てビームサーチする方針は、開始 10 分ほどで決めました。ワープをほとんど使わない低スコアの状態でも、まず出力まで一通り動く骨格を作りました。以降の改善は、ほぼ遷移の列挙・重複除去・パラメータの変更だけで済んでいます。
• 全ての変更を pahcer で同じ 100 ケースで評価し、コメント付きで記録しました（コンテスト中に 59 回）。

コンテスト後の改善

最終提出をベースに、手元の 100 ケースで比較しました。

変更	1 ケースあたりの平均の伸び
山登りで、手数が同じ遷移も受理する。あわせて、試す方向の順番をランダムにする	+31.8
評価値に、1 個先の目的地への見込み手数（writer 解の見込み手数を 1 個先だけにした簡易版）を足す	+9.5
ハッシュマップの容量を \(2^{24}\) から \(2^{19}\) に減らし、速くなった分ビーム幅を 2200 から 3200 に増やす	+9.0
上記をすべて組み合わせる	+44.8（+0.57 %、平均 7,964 点）

• 手数は整数なので、山登りでは同点の近傍が多くあります。同点の遷移も受理するようにすると、全 100 ケースで改善しました。
• 見込み手数は 1 個先しか見ていません。writer 解のように 8 個先まで見れば、さらに伸びる余地がありそうです。

一方、次の変更はほとんど効果がありませんでした。

• 山登りを焼きなましにする（同点の遷移を受理するだけの方が伸びが大きい）
• 転移を削除する近傍を加える（変化なし）
• 同じ魔法陣を使う連続した転移をまとめてずらす近傍を加える（同点の遷移の受理と組み合わせると上積みなし）