RECRUIT 日本橋ハーフマラソン 2023夏（AtCoder Heuristic Contest 022）12位解法
はじめに
RECRUIT 日本橋ハーフマラソン 2023夏（AtCoder Heuristic Contest 022）に参加し、最終12位でした。私の解法をここに記載します。細かい部分の説明は省略し、概要を示します。
問題
最終提出
真の温度と計測された温度の確率
1個のテストケースにおいてSを固定したとき、真の温度がμであるときに温度tが計測される確率は、正規分布の累積分布関数から求めることができます。例えばその確率を P(μ, t) と表すことにします。
真の温度と計測された温度の組み合わせは1001×1001通りありますが、全組み合わせの確率を最初に計算して確率テーブルを作っておきます。
ワームホールと出口セルの尤度計算
あるワームホールwhから1回以上計測を行ったとき、ワームホールwhと出口セルecが対応している尤度を、先ほどの確率テーブルから求めることができます。 [1]
1つの計測 (ワームホールwh, 移動d, 計測温度t) を行ったときの尤度について考えます。
移動dは二次元のベクトルとして d=(d.y, d.x)とし、出口セルecのy座標をec.y、x座標をec.xとしたとき、もし出口セルecから出ているならば計測する座標は (ec.y+d.y, ec.x+d.x) になります。 [2]
計測時にはその座標における真の温度は既に決まっています。その真の温度を temp(ec.y+d.y, ec.x+d.x) とします。
以上の前提から、1つの計測についての尤度は次のように表されます。
Likelihood(ec,wh) = P(temp(ec.y+d.y, ec.x+d.x), t)
whについて複数の計測を行っている場合、各計測の尤度の累積積が(ec,wh)ペアの全体の尤度になります。
温度配置
山の頂上に1マスだけ極端に温度の高い点（旗）がある、お子様ランチ型の配置にしました。[3]
この配置には以下のようなメリットがあります。
-
旗以外は温度差がゆるやかであるため配置コストが抑えられている
-
旗を計測すると出口セルをほとんど確定できる
-
旗でない位置を計測した場合も、ある程度出口セルの絞り込みに役立つ
計測戦略
上に挙げた配置のメリットの2番目と3番目の性質を組み合わせた計測を行います。
ワームホールを固定したうえで何度か計測すると、旗を直接計測せずともある程度尤度の高い出口セルが絞られてきます。その尤度が高くなった出口セルを優先して旗を計測しにいくことで、ワームホールに対応する出口セルを素早く確定できます。
具体的には以下のように計測を行っています。
ワームホールを1個ずつ固定し、出口セルとの対応を確定させていきます。対応が確定済みであるワームホールと出口セルは、以降は候補から外すことにします。
先ほど説明したお子様ランチ型の性質を用いて、尤度（から計算した確信度）が高い出口セルを優先して確認することにより、少ない回数で旗に到達ができます。
確信度の計算や対応の確定には、ワームホールを固定したときの出口セルの尤度比を利用することにします。[4]
例えば Likelihood(ec1, wh) / Likelihood(ec2, wh) = 1000 のような関係が成り立つとき、直感的には「出口セルec1がワームホールwhと対応する尤度は、出口セルec2の1000倍ある」という意味になります。
尤度比の比較対象としては特に「そのワームホールに対して2番目に尤度の大きい出口セル」を利用します。
優先度付きキューを用いて、以下のような疑似コードにより計測と対応関係の確定を行います。
while (計測が10000回未満 and 未確定のワームホールが残っている):
未確定のうち最も確信度が大きい(出口セルec, ワームホールwh)のペアを priority_queue から取り出す;
whから入り ec→旗 の向きの移動をして計測;
for ec' in 1..N:
計測値から Likelihood(ec', wh) を更新;
if ( Likelihood(最も尤度が大きいec, wh) / Likelihood(2番目に尤度が大きいec, wh) > 1500) :
(最も可能性の高いec, wh) の対応関係を確定;
else:
for ec' in 1..N:
確信度:= Likelihood(ec',wh) / Likelihood(2番目に尤度が大きいec, wh);
(確信度,ec',wh) を priority_queueに入れる;
ちなみに、このままでは初期状態での尤度はすべて等しい値をとって確信度は全て1になり、優先度付きキューからは無作為なものが得られることになります。そこを少しだけ調整して、確信度の初期値は旗に近いecほど高い適当な値にしておきます。
以上です。
Discussion