AtCoder Heuristic Contest 003 参加記

AtCoder Heuristic Contest 003に結構時間を溶かして参加し、96.7Bで暫定29位でした。
https://atcoder.jp/contests/ahc003

解法

• ベースはRidge回帰＋ダイクストラで最短路を選択
  • M=2を意識して行／列ごとに2個パラメータを持たせるようにした
• 最初の90ターンは探索、「いい感じ」に未探索のパスを選択
  • 「いい感じ」のパスが見つからない場合は最短路を選択
• その後は最短路を選択しつづける
  • あまり探索していない行／列は長さがちょっと短いように補正する

感想

早めに回帰の解法を思いつけて、土日に94Bまでには比較的良いペースで辿りつけた。 いろいろ分析を重ねたものの、上位との3Bの差を埋められるような大きさの知見が得られずにずっと苦しんでいた。 回帰に正則化を入れて更新頻度も多くしたところ96Bまで一気に上がり、そこから細かい工夫とパラメータチューニングで96.7B。

GCPのCloud RunでOptunaで自動パラメータチューニングする仕組みを立てていて、これはかなり便利。 20ケース x 100試行が1-2分で帰ってくるので、ちょっと迷ったときにパラメータ化して良さげなところに設定することができる。

プログラムはC#だけど、分析には結構Pythonを使っていて、地味にPythonのタスクランナーであるpython-invokeも便利でした。設定次第でカレントディレクトリに依存せずにいろんな処理をできるので、ターミナルがぐちゃぐちゃにならずにすむ。