解法

大筋

上図のように盤面を均等に4分割し、温度は２値だけ使って、右下のエリアの温度だけを高くした配置をしました。
こうすることで、x軸y軸が0の部分の切れ目までの距離を二分探索っぽく特定できるようにして、計測回数をある程度少なく抑えるようにしました。

次の節からもう少し詳しく書いていきます。

配置

盤面を均等に4分割し、右下のエリアの温度だけを高くした配置をします。
奇数長盤面の場合は、赤側の一辺の長さを l/2 + 1 としています。

温度差は S の大きさと見合わせながら決めています。後ほどもう少し詳しく記載します。

推定手順

軸それぞれで独立に、0までの距離を求める方針になります。

最初に移動無しで計測して、出口位置が赤か白かを特定します。

出口位置が赤だった場合の、x=0までの距離を求める手順が以下になります。

(0, -l/2) *1を計測する。基本的には白になるので、その場合２に進みます。特殊ケースである赤の場合の対応は右の注釈に書きました*2。
(-l, -l/2] の区間のどこかが x=0 であることが確定しており、かつ単調非増加であるので、二分探索の要領で x=0 の位置を割り出す。

y軸についても同様の手順を行えば、出口の座標が割り出せます。

初期位置が白だった場合は、まず (+l/2, 0) と (0, +l/2) の計測結果を見ることで、出口がx軸y軸それぞれで l/2 以下の位置にあるかどうかを確認します。
l/2 以下に居ないなら上記の手順１から、居るなら手順２から操作を行い、座標を特定する。その際、探索範囲に赤エリアを含めるために、確認対象でない方の軸を l/2 ずらす必要があります。

温度差と計測確度の設定

信頼区間4.1σにして、計測が間に合う範囲でできるだけ白と赤の温度差を小さくしました。
配置コストが計測コストを下回れる場合は、配置コストと計測コストが近い値になるラインを狙って設定しました。
逆に白をP=0、赤をP=1,000としても計測が間に合わない場合は、信頼区間を最悪3.8σまで落としました。

精度はどうか

実測して見てみました。seed 0~199 の実行結果を確認したところ、

誤回答数０が175ケース
最大誤回答数が３で２ケース

といった感じでした*3。
概ね正解できるし、外してもまともに点数が取れるラインには収まる、くらいな感じといったところでしょうか。

その他工夫

計測回数を抑えるために、計測で端値*4を引いたら標準偏差分はみ出るように値を加えた*5。
二分探索チックな操作をするパートで、絞り込んだ範囲に出口が１つしかない場合は、その時点で確定して計測を打ち切った。

提出コード

Submission #44799051 - RECRUIT Nihonbashi Half Marathon 2023 Summer（AtCoder Heuristic Contest 022）

感想

期間後半くらいに入るまで、Sが大きいケースで１点しか取れない状態が続いていて、中々苦しいコンテストでした。一方である程度点数が取れるようになってからは、追加で色々と試したいことが思い浮かんで、かなり楽しめました。

知見のほとんど無い推論系問題*6でこの順位取れたのはまあ頑張った方ではないかな、と思っている一方で、そんなこと言ってないでちゃんと推論系の知識身につけないと不味いよなって気持ちになりました。コンテスト後のTLを眺めていても、知識不足で何を言っているのか分からないことが多かったですし。。インタラクティブ問題は概ね推論とセットみたいなところがあるはずなので、AHCを戦っていくなら避けられないだろうなとかを思っています。

とりあえず上位の解法を見つつ、今回の復習を頑張ろうと思います。