京セラプログラミングコンテスト（AtCoder Heuristic Contest 006）参戦記
AtCoder Heuristic Contest 006に参加して、13位 performance 2831、人生初の赤パフォでした。
レーティングも2174と黄色入りして、ランキングは73位でなかなかの順位です。
自社の応募要件に「ヒューリスティック最適化に強いこと（threecourseと同レベル以上、平均してAHC100位程度を目安）」とか書いているので良い成績をとらなきゃ、でも精進する時間ないしみんな強いしどうすんだ、と思っていましたが一発当てることができてほっとしています。
考察
開始5分での考察はこんな感じ。
- 変なTSP（巡回セールスマン問題）っぽい
- ぱっと見、注文を取り替えて焼きなましするしかなさそう
- 入れ替えるときにベストなところに挿入すれば大体良さそう
- 理想的な解は pick1 -> pick2 -> pick3 -> deli2 -> pick4 -> deli3 -> deli1 -> deli4 のように、多少入り乱れつつも前半にpick多め、後半にdeli多めになりそう。
ほぼベストな考察ができていましたが、これくらいみんな考えてくるだろう、wataさんがwriterだからもう一工夫必要かとか思って1時間くらい考察しました。 「ルートを決め打ちしてその回りの注文を取っていく」みたいな解を考えるも、元の案の方がましそうだったので却下し、おとなしく実装。
わりと軽めの実装ながら、なんだかんだマラソンの実装はバグり散らかすため、2時間半経過時に実装を終えて投げると1.99Mでなんと4位！
以下のような改善案が思いついたのですが、結局高速化をバグらせて何もできず、ダメ元で温度変えていくつか投げて1時間半改善せず終了。
- 高速化
- TSPで有効とされているキックを導入する
- 入れ替えるときにベストなところに挿入するを真面目にやる
- 注文を取り替えずに順序を変える
解法
焼きなましで、近傍はランダムに注文を削除し、ランダムに注文を追加。このとき、「ベストな」ところに挿入する。
「ベストな」ところに挿入は、
- ルートの間のいずれかに最も短くなるようにpickを挿入（選択肢は注文の数 x 2）
- そのあとpickの後という制限のもとで同様にdeliを挿入
まぁまぁ賢い解が出ているように思います。
#AHC006 アニメーションできた pic.twitter.com/154aakCUkt
— threecourse (@threecourse) 2021年11月14日
解法の反省点
- あとから議論して気づいたのですが、pickとdeliでそれぞれ各地点に入れたときの距離のゲインを保持しておき、累積Maxのような構造を使うと計算量がO（注文）のままに真に「ベストな」挿入ができますね。
- 焼きなましの遷移時に無駄に配列をコピーしているのですが、グローバル領域に配列を保持しておいてそこに入れればオブジェクト生成コストを減らせそう。
