※ ほぼAIに書かせました
Bondo416さんのAtCoder Heuristic Contest 059での成績：96位
— ボンド@競プロ (@bond_cmprog) January 10, 2026
パフォーマンス：2049相当
レーティング：1772→1822 (+50) :)#AtCoder #AtCoderHeuristicContest059 https://t.co/KHRWmSRAdH
概要
20x20 のグリッド上にペアのカード（0〜199、各番号2枚ずつ）が配置されている。(0,0) から出発し、山札（スタック）を使ってカードを回収する。山札の上2枚が同じ番号なら自動的に消える仕組みを利用して、全カードを消すことを目指す。移動回数をできるだけ少なくしたい。
方針
問題を TSP（巡回セールスマン問題）として定式化し、反復局所探索法（ILS）＋焼きなまし法（SA）で解いた。
2フェーズ戦略
スタックの LIFO 性質を利用して、以下の2フェーズで全カードを消す。
- 往路（収集フェーズ）: カード番号の順列
order[0..199]に従い、各番号のペアのうち片方を拾う。2枚のうち近い方を貪欲に選ぶ - 復路（回収フェーズ）: 往路の逆順で、もう片方を拾う。逆順で拾うことでスタックの上から順にペアが揃い、自動的にすべて消える
この構造により、問題は「どの順番でカードを集めるか」という順列の最適化に帰着される。
初期解：最近傍法（Nearest Neighbor）
(0,0) から出発して、未訪問のカードのうち最も近いものを貪欲に選ぶ。TSP の定番手法。
局所探索：2-opt
順列に対して 2-opt（区間反転）を適用。改善が見つかるまで全ペアを試す。
高速化のために O(1) の差分評価 を実装した。2-opt で変化するのは反転区間の両端の辺だけなので、往路・復路それぞれで変化する4辺分のみ計算し、改善が見込まれる場合のみフル評価で検証する。ただし、差分評価は pick_choice（2枚のうちどちらを先に拾うか）が変わらない前提の近似なので、デルタが負の場合にフル評価で正確なスコアを確認している。
ILS + SA
2-opt の局所最適に陥るのを防ぐため、ILS（反復局所探索）で摂動→局所探索を繰り返す。
- 摂動: 約98%の確率で Double-bridge（4箇所で切断して再接続する TSP 定番の強い摂動）、残りはランダムスワップ
- 受理判定: SA 方式。温度は線形に冷却（初期温度 ≈ 1.1）
- 適応的な摂動強度: 進捗に応じてスワップ数を 2〜5 で変化
ハイパーパラメータ調整
最後に Optuna で SA の初期温度と Double-bridge の確率を探索した。30 試行で以下の値に落ち着いた。
| パラメータ | 値 |
|---|---|
| SA 初期温度 | 1.099 |
| Double-bridge 確率 | 0.979 |
ビジュアライザ
96位？
— ボンド@競プロ (@bond_cmprog) January 10, 2026
seed: 0
Score = 15153, K = 1247 pic.twitter.com/ubMgsTF7oZ
やらなかったこと / 試さなかったこと
- バッチ分割（Chunking）: 全収集→全回収ではなく、一定サイズごとに収集・回収を繰り返す方式。実装計画は立てたが最終的には採用しなかった
- Or-opt: 1〜3個の連続ノードを別の場所に挿入する近傍。実装する時間がなかった
- 近傍リスト: 2-opt の相手候補を近い地点に限定する枝刈り。効果はありそうだったが未実装
- ペア選択のビット探索: 「どちらのカードを先に拾うか」を近傍操作として明示的に最適化すること
