AHC004に参加しました。66.2億点で622人中16位です。
パフォーマンス（β）は2829、レーティング（β）は2293 (+232)です。β版ではありますが、アルゴ含めて赤パフォを取れたのは人生初めてなのでめちゃくちゃ嬉しいです。
問題概要
宇宙人の遺伝子の断片をいっぱい読み取ったから頑張って復元してね。
考えたこと
焼きなまししづらそうな問題に見えたので、貪欲ベースが良いかなあと思いました。ちょうど最近長方形詰め込み問題をBottom-Left法*1＋焼きなましで解いて遊んでたりしてたので、似たようなノリで解けないかなと考えました。
また、文字列を繋げられそうな点は天下一 Game Battle Contest 2021 Springっぽさを感じました。繋げるやつの実装、めんどくさそうだけどやっといた方が良いんだろうなあと思ってたんですが、これがかなり本質だったっぽいです。
やったこと
文字列の順番と向きを決め打って、一番被りの多い場所に置いていく貪欲をしました。順番・向きの初期値は文字列長の長い順・全て横方向として、これを山登りで改善する方針としています。*2
個の文字列について置く場所の候補が
箇所、それぞれについて置けるかどうか・置ける場合は被りがいくつかを調べるのに
かかるので、1回の試行に
かかります。*3 スコア計算も愚直に全部調べて
です。当然処理が激重で山登りも高々
回くらいしか回らなかったんですが、短期コンだしもっと優先順位の高い項目があるのでまあいいかな……と高速化はサボりました。山登りの近傍としては、順番のswapと縦横の変更の2種類を採用しています。
加えて、前処理として部分文字列が4文字以上一致しているペアをマージする処理も入れました。効率の良い実装が分からなかったので、「種類のペアについて、最も被っている部分の長いペアを1つにマージする。マージしたらもう一回最初から」というような処理を行っています。計算量をちゃんと見積もっていないのですが、実際走らせたら思ったより速いのでヨシ！をしました。
一番スコアの良かった提出はこれです。もしかしたら上で書いたことと微妙に違うかも。
日記
ここだけ常体で。見出し名は開始からの経過時間です。
こういうときAtCoder Marathon Replayを使うといつ何をやったか思い出すのが楽で良いですね。ありがたく使わせて頂いています。
～開始0:45
問題文を読む。一瞬AHC003みたいな推定問題か？と思ったが、普通に最適化問題。ボーナス点なんて取れるんだろうか……。
焼きなますのは難しそうなので、とりあえず文字列の被りが一番多い場所・向き（ 通りを全探索）に置いていく貪欲を書く。文字列の順番はとりあえず受け取った順番のまま。提出すると36.5億点で10位。ひとまず筋は悪くなさそう。
～開始1:00
改善を入れたときにその良し悪しをサクッと確認できるようにしたいので、以前書いたものを流用してローカルで512ケース回すプログラムを書いた。提出間隔5分って意外と長いのよね。
さっきは文字列を置く順番を受け取った順にしたけど、直感的には長さか何かでソートした方が良さそう。色々試すと長い順に並べ替えた方が良さそうだったのでそれで提出。41.1億点で13位。
～開始2:00
貪欲が書けたのでビームサーチに発展させたくなる。評価関数を「置けた文字列の数」「残りの空きマスの数」から適当に作ってみたところ、ほとんどのケースで貪欲より悪くなる。一応貪欲と両方試して良い方を投げるようにしたが、41.5億点で誤差の範囲。うーん。
貪欲で左上詰め・横向き優先で置いていたのがビームサーチ化でバラバラになり、置ける場所が少なくなってしまったのが原因と思われる。例えば6マス中2マスが埋まっているケースとして、「AB....」であれば被りがなくとも任意の4文字以下の文字列を置くことが出来るが、「.A.B..」だと選択肢がかなり減ってしまう。これは確かにマズい。
1時間溶かしてしまったが、6時間コンテストなのでまだ挽回は効きそう。これが4時間だったらと思うとゾッとする……。
～開始3:00
ビームサーチを投げ捨て、文字列の順番と向きを改善する山登りを書くことにする。1試行が重すぎるけどしょうがない。多分局所解にもたどり着けないので焼きなましへの発展は望み薄。
初期解は文字列の長さ順でソート、向きはランダムとして投げると44.7億点で45位。ちょっと微妙かなあと思ったけど、初期解の向きを横方向に統一すると48.1億点くらいまで伸びる。原因はおそらくビームサーチと同じ。とはいえ順位はほぼ変わらず。
～開始5:00
この時点で上位陣は60億点台を当然のように出していたので、何か大きく変えないとダメだなあという気持ちになる。盤面を直接焼きなます方針も考えたけど、おそらくかなり試行回数を稼がないとまともな解が得られなさそうで、高速化出来る気がしなかったので却下。やるべきなんだろうなあと思いつつ実装が大変そうで避けていた文字列のマージに取り組むことにする。これをやってなくて負けた天下一コンのこともあるし……。
マージの厳密解の求め方が分からなかった*4ので、適当に貪欲をすることに。貪欲も貪欲でどうすればいいのかよく分からないので、効率悪いだろうなと思いつつも全ペアを舐めつつ、被りが一定以上だったらマージすることにする。*5
バグらせつつも実装すると手元ケースで10%近くスコアが伸びてテンションが上がる。これを投げると58.2億点で45位。マージするペアを被りが長い順に変更するとさらに伸びて63.3億点で20位。短期AHCは苦手意識があったけど、これは1ページ目行けるか……？と希望が湧いてくる。
～開始6:00
時間もないし本質的な改善案も思い付かないので、あとは微改善とパラメータ調整をしつつ投げまくる。Optuna使うことも考えていたけど、やっぱり短期コンだと時間ないしコードもちょこちょこ書き換えたいので、結局人の手による温かみのあるパラメータチューニングになってしまう。人力ベイズ推定最高。
なんやかんやで66.2億点、16位でフィニッシュ。
感想
やっぱりAHCは楽しいですね。勝てるとなおのこと楽しいです。同じ短期コンテストであるAHC002は217位でボロ負けだったんですが、今回雪辱を果たせたのでとても嬉しいです。過去4回のAHCは15位→217位→20位→16位と順位表1ページ目常連になれつつあるので、ちょっと自信を持ってもいいのかもしれません。
ところで手元で回した512ケース中満点が取れたケースは0個で、ありもしない遺伝子をひたすら捏造するだけになっていたのは内緒です。平均1/3も矛盾が生じてちゃ、だめだろ。
