4/20 土曜日に開催された 第一回マスターズ選手権 -決勝- に参加してきました。
参加まで
まあまあ波乱怒涛だった 23 年も末、趣味と趣味と仕事と推し活と趣味と順番に復旧させていた最中、競技プログラミングのスイッチが入り切っていなかった頃合いに tsukammo さんから社の slack で DM が飛んできました。
「これ、もしよければ何だけど出ません？ （中略）https://atcoder.jp/contests/masters-qual」
1分で「出ます」と返答して出場が決まりました。持つべきは頼るべき先達。 もう一人のチームメンバーはHTTF入社枠の先輩である tanzaku さんでした。
予選
tsukammo さんがビジュアライザに専念。私とtanzakuさんで別々に方針を決めることに。
移動一手読みから n 手読みに発展させていけばいいかな、あわよくば焼こうか ← 最後まで無理でした
バグらせている間に一手読みの方針を聞いた tanzaku さんがうまく読みターン数を増やす方法を思いつき、見た目の順位41位で無事突破。椅子を温める結果で情けなかったものの tanzaku さんに初期方針を褒めていただき自尊心++;
本戦
都民ではないので都内への移動が結構しんどい、という理由で前日の部署飲み会を1次会で切り上げ、翌日無事起床成功。
今日は部署の飲み会で、二次会行こうか迷ってたんですが、明日のマスターズ決勝に一緒に出るチームメイトが帰るとのことで、大人しく帰ります。
— ツカモ (@tsukammo) 2024年4月19日
ライバルチームを潰すか自分が潰れるかと思っていたが、二次会に行ったのが自分だけで、おしまい
— りあん (@rian_tkb) 2024年4月19日
かわいそう
— omi🪸🌸 (@omi_UT) 2024年4月19日
問題はまた面倒くさそうな幾何問題に tsukammo さんがビジュアライザに専念。私と tanzaku さんで別々に方針を決めることに。
とはいえ計測が面倒くさすぎて、速度調整も面倒くさすぎて、推定位置をログに吐いてみても全然違うところを表示する始末。
一旦誤差の小さい B 問題をこなすために、複数 agent を最も近そうな経路に向かって同時に走らせて、壁にぶつかった・ぶつかってない、ゴールした・してない、で矛盾した奴らを順番に kill する、という方針で進めていくことにしました。 最も近そうな経路というのも、直線移動ができないなら進路を遮る壁の右回り or 左回りで迂回、というのを再帰的に考えると一応各ゴールまで通れるはずのルートが計算できるので、あとは誤差が小さいことを 信じて 進みます。面倒なので計測はしません。面倒なので加速度は 499 固定で制御はしません。
ちょっと壁に挟まれると agent が壁にぶつかったぶつからないで矛盾を起こして一瞬で全滅し、あとは 5000T 風にたゆたうだけの儚い存在になります。もしくは通れないくらいの狭い壁に挟まれて一生抜け出せずスコアのマイナスを掘り下げることになります。 スコア平均が 5000 くらいしかない……あと1時間切ってる……何処がバグっているのかな……
ここで放置していた順位表を見ると B で 300k (=5k*60) 出せば良い方でした。みんなバグってるな？ 提出。
そのあと経路計算の打ち切りをしてみたり agent 数を増やしたりして B を40 万まで伸ばし、あとは乱数 seed ガチャをしたり（本当に何もしていないのに 1 万くらいブレるので結構本質）B から何も改善していないコードを C に出したりしてタイムアップ。 Aにも出したんですが、壁にぶつかるかゴールするかしないと位置に関する情報が取れないアホな仕様上壁がないと悲惨なスコアになってました。
その間 A を詰めていた tanzaku さんと合わせて総合 5 位でした。
懇親会
朝昼ともにほぼ無みたいな食事をしたせいで腹が大変減っており、大飯喰らいに。見ず知らずの大飯喰らいメイツと感想戦をしたり、（数は少ないですが）旧知の方々と久しぶりにお話をしたり。
スポンサー企業ブースが複数並んでおり、その上複数回らないとアルコール摂取がアンロックされないという バグ 仕様 のせいでとても盛況でした。いつもなら人混み凸はしないのですが、酒を人質に取られていては……。
翌日IPA試験がある、という理由で1次会で切り上げ、翌日。知恵熱を出し無事ダウン。 近所なら受験しに行ったんですが片道一時間と交通費そこそこを掛けてまで落ちに行く気にもなれず蟄居しました。😿
その後
あとはパーティクルフィルタというらしい今回の手法を真面目に復習のために写経したら一瞬で 8 割でてびっくりしました。
今回の問題で計測した値をごにょごにょすれば各 agent の「有り得そうな確率」が出るのはわかったのですが、その活かし方を知らなかった。その確率に応じて重み付きで random pick すれば結果的に正しい確率分布に沿った状態に更新できるのは目からウロコでした。
AHCサボりまくっていますが、典型知識部分の不足を痛感したので成績云々抜きにちゃんと問題と手法を見ていかないとな……と思いました。今後頑張ります。
