RECRUIT 日本橋ハーフマラソン 2023夏(AtCoder Heuristic Contest 022)参加記

2023/8/11〜2023/8/20に開催されたRECRUIT 日本橋ハーフマラソン 2023夏(AtCoder Heuristic Contest 022)に参加しました。

最近のヒューリスティックコンテストでは、かなり良い結果が出つづけており、気がつけばもう少しで青色という所まできました。

今回、青パフォの上位ぐらいが出せれば、入青できるはず。まずは青パフォレベルが出せるように頑張ろう、という感じで臨みました。

参加します。
ヒューリスティックの方はもうちょいで入青できそうな感じなので、今回で決めれるように頑張ります✊

RECRUIT 日本橋ハーフマラソン 2023夏（AtCoder Heuristic Contest 022） | AtCoder https://t.co/VBOskTsPXA #AHC022 #rcl_procon
— devgenjin77 (@devgenjin77) 2023年8月11日

今回の結果

確定340位。。。なかなか今回はスコアが伸びなかったなあという印象です。

結局、パフォーマンスは水色の中ぐらい。現レートより低い結果でしたが、レートの方はそこそこ上がってくれました。

今回むずかったです。次回に向けて精進します。

devgenjin77さんのRECRUIT 日本橋ハーフマラソン 2023夏（AHC022）での成績：340位
パフォーマンス：1472相当
レーティング：1544→1564 (+20) :)
Highestを更新しました！#AtCoder #RECRUIT日本橋ハーフマラソン2023夏 https://t.co/DPgyGEVZCX
— devgenjin77 (@devgenjin77) 2023年8月21日

振り返り

ちょっと今回は、ハズレ方針に固執しすぎた感じがあります。

A問題

A - Exploring Another Space

$L \times L$ のマップ上に、別世界にある入口と１対１で対応している $N$ 個の出口がある。どの入り口がどの出口に対応しているかが知りたい。

調査は、最初にマップ上の各セルに温度を設定しておき、出口から予め決めておいた距離分移動した場所の温度を計測することで実施する。

ただし、計測された温度は誤差を含み、最大の標準偏差が900にもなる。というのが問題の概要。

これ、当初誤差の最大が900度かと思ってましたが、なんとローカル用のテストデータを見てみると、最悪±3000度以上の誤差を出してしまう可能性があるとのこと。。

こんなもん、どうやって計測するんだと思いましたが、とりあえず開始から数日は、アイデア出しに勤しんでおりました。

方針１：原点探索法

んで、数日かけて考えたアイデアの１つが、こんな感じ。

とりあえず、原点の１セルだけ温度を極端に低くして、残りは最高温度に設定。

計測は、それぞれ入り口より、各出口の座標から原点に移動する動きをして温度を計測していけば、入り口と出口の対応が取れるだろうという算段。

これを名付けて、原点探索法。配置コストがそれなりに抑えられるのがメリットですが、探索コストが結構かかりそうな感じがします。

とりあえず初提出！ここから上げていければ。。#AHC022 #rcl_procon pic.twitter.com/0UY6nphpxB
— devgenjin77 (@devgenjin77) 2023年8月16日

とりあえず、この方針で初回提出。この時はパラメータ調整はほとんどしてない状態でしたが、まあまあいい順位につけたなあという印象でした。

方針２：出口を２、３グループに分けてから１点探索

原点探索法をさらに改善しようと色々検討したところ、出口を温度でグルーピング化してから探索する方法にすれば、各出口から原点を探す回数が減らせるので、トータルでコストが抑えられるのでは無いかと思いました。

上図のように、出口を丁度２つのグループに分けて、それぞれのエリアに１つの温度を設定します。この塗り方だと、とりあえず配置コストが抑えられるかなあという感じです。

ちなみに、適当に決めた出口を最低温度の点にしています。

計測パートでは、最初に各出口の温度を計測して、どのグループに属するかを決めてから、それぞれのグループについて、最低温度の出口を探索していくという感じです。

$S$ が低い場合は、もっとグループを増やした方が良いかなということで、３グループに分けるバージョンも作成。何グループに分けるかは、 $S$ で調整してみることにしました。

で、、この方針で実装した後、パラメータを色々調整し、ある程度限界が見えてきたのが土曜の夜中。

どれぐらい順位が上がるかなあと思いながら提出してみたら、なんと300位ぐらい。。。

これ以上点数を伸ばすには、イチから見直さないといけないという感じになり、ちょっと心が折れてしまいました。以降は、検討すらできておりません。

最終提出コード

https://atcoder.jp/contests/ahc022/submissions/44798818

振り返り

今回については、最初に出した原点探索法をもう少し突き詰めるのが正解だったかと。改善案は配置コストも計測コストもそれなりにかかるので、ちょっと中途半端なアイデアだったかもしれない。
改善案が正しいはずという考えに固執しすぎたため、色々なアイデアを実際に比較検討するのを怠っていたという感じ。
上位解法を見ると、確率論の考え方を使って推定しているものが多そう。もう少し数学の勉強もしておかないとなあ。