京セラプログラミングコンテスト (AtCoder Heuristic Contest 006) 参加記

はじめに

2021/11/14の16:00-20:00に行われた 京セラプログラミングコンテスト (AtCoder Heuristic Contest 006) に参加しました。結果は1953482点で、19位でした。



解法

全ての点と (400,400) との角度を求める。
(a,b)の角度 < (c,d)の角度 を満たす配達先のみを反時計回りで巡回するルートを、「ランダムに選んだ1つを削除し、ランダムに選んだ1つを適切な角度に追加する操作」を近傍にした焼きなまし法で最適化する。
これを逆向き(時計回りの場合) でも同様に行い、2つの解の中で良い解に対し、「ランダムに選んだ1つを削除し、ランダムに選んだ1つを改善量が最大となる位置に追加する操作」を近傍にして山登り法で最適化した解を出力する。


コンテスト中の流れ

概要の理解, 初手 (~20分)

まず問題を読んだ。集合を選ぶパートと巡回セールスマン問題を解くパートの2つに分かれている事が分かって、どちらも焼きなまし法が使えそうなので安心した。
2つパートがある問題は解法を2ステップに分けずにうまく一体化する事が大事という話が昔のマラソンコンテストであったはずなので、どうにか両方をまとめて最適化する事を考えたい。
巡回セールスマン問題を含むのでどう転んでも2-optは実装する事になるのかなぁと思ったけど、2-optの実装経験がない+午前中に予定が入っていて集中力が十分残っていなかったので、ひたすら高速化して焼きなますだけの勝負になると勝てなそうで少し不安。
とりあえず配送先1-50を順番に辿るvalidな解を書いてビジュアライザで答えを見たんだけど、それすら少し時間がかかってしまったので反省。

アイデア探し (~100分)

とりあえず2-optは実装して損がなさそうだから後で書くとして、その前にビジュアライズした時に分かりやすい+焼きなましに移行しやすそうな見た目の初期解を貪欲法で作る事を考える事にした。
とりあえず近い点対をまとめて扱えると嬉しいのかなと思って近い点対を探したり(a1,b1)と(a2,b2)が近く(a3,b3)と(a4,b4)も近い配送先のペアを出力してみたりしたんだけど、方針が全然思いつかない。
100*100ぐらいのブロックを考えてそこをまとめるみたいな事も考えたんだけど、そうしてもいい解が出せる気がしなくて、困った。
一時間以上考えても何も分からず布団で考えたりしたんだけど、全く分からない。

初回提出 (~120分)

中心との角度でソートして並べれば適切な挿入位置が求まって高速に焼きなましの近傍が出せそうな事に気づいた。 この時点ではすごい良い解法っぽい感覚はなかったんだけど、性能が微妙だったとしてもとりあえず見た目の良い初期解が出せそうなので実装してみる事にした。
頭を使うコードを書くのがつらい+仮実装の段階 なので毎回ソートし直す O(mlogm) の近傍操作を書き、10000iterの山登り法を実装した。出力の見た目もseed=0に対する距離も思っていたより良くてウキウキで提出するとREが出て、悲しい気持ちになってしまった。(テストケースをファイルから読み込むコードのままだった事が原因だった)

2回目の提出 (~127分)

提出間隔が5分あるのでその間に自明な改善を考える。現時点では反時計回りのケースしか考慮していないが、それだと1000個あるタスクのうち約半分しか見ない事になって困るので、時計回りのケースに対しても試行を行って良い方を取るようにした。また、実行時間に余裕があったのでiter数を2e5に増やした。
提出を行った結果175万が取れて、この時点での10位になれた。

焼きなましの実装 (~160分)

現時点の実装は雑に山登り法を適用したのみなので、これを焼きなましに置き換える。実装してもスコアが上がらず困ったが、原因のバグ (焼きなましの遷移判定の直後に if(now_score > nex_score) が入っており、山登りの完全な劣化になっていた) を発見して解決した。178万点で21位。

焼きなましの調整, 二段階目の実装 (~215分)

iter数とスコアの関係を見た所、iter数が1e5になった辺りでスコアがほぼ改善しなくなる事が分かった。この方法だけだと限界がありそうなため、別の方針を考える。
今の手法は偏角によって配送タイミングに制約をかけているためそこに問題がありそうで、そうなると偏角に依存しない操作をしたくなる。そのため、偏角ベースの焼きなましで得られた解に対して一点挿入一転削除の山登りを実装する事にした。 挿入時にスコアが最も改善するような挿入位置の組を求める操作は累積minを使うと O(m) でできて、流石にここの O(m2) は許容できなさそうなので頑張って書いた。
集中力が切れてきた事もあって実装に時間がかかるため、5分に一度焼きなましのハイパラ調整を行って提出していた。186万点で17位。

終盤 (215分～)

二段階目の山登りが実装でき、194万で17位に戻ってきた。
残りは安定して点を稼ぎたかったため、一段階目と二段階目の実行時間のバランス調整や焼きなましの温度最適化を行い、5分に一回提出するようにした。
残り140秒で投げた最終提出がHighestで、最終的には195万点で19位となった。

反省

序盤の1時間半ぐらい全くアイデアが出なかったので反省。ただこの時にハズレ方針に手を付けて逃げられないみたいな事にならなかったのは悪くないし、結局当たりを引けたからOKかな・・・という気分。
2-optの高速化で勝負すると厳しいという事を判断して簡単な焼きなましに逃げられたのは良い判断じゃないかなぁと思う。焼きなましパートの必要以上の高速化を切って他部分の変更に時間を割けたのも良かった。
終盤の動きは適切っぽくて、自明な改善がなくなったタイミングで、可能な提出回数が少なくなるラスト数十分を手元でのスコア測定+ハイパラ調整での得点アップに割くムーブは正解そう？
あと記事を書いている時に気づいたんだけど、kick操作を全くしていないので局所最適から全然抜けられてなさそう。今回は雑にやって問題なかったけど、今後に備えてちゃんと設計ができるようになっておくべきかもしれない。