(今後編集される可能性があります)

割かし高順位になったので、私の解法を軽くまとめておきます。

すべてを解説はしにくいため、重要な点に限ってまとめておきます。

また、理論的な面はすっとばしています。あくまで「こうすればなんかうまくいくよ」みたいな感じの解説だと思ってください。

最終的なコードはこちらです。

たぶんというか絶対わかりづらい部分があると思いますが、ご容赦ください。

温度設定フェーズ

後述しますが、出口セルがある地点は温度を固定します。これ以降は、温度を固定するセルのことを固定セルと呼ぶことにします。

また、重要な点として以下の点が挙げられます。

• 固定セル以外のマスはコストを最低にするため隣の温度の平均をとるべき

「すべてのマスに対して隣の温度の平均をとる」ことを100回ほど繰り返すと、コストを低く抑えることができます。以降、固定セル以外の温度の設定は本質的ではないため考えないことにします。

ここで、私が使用した固定セルの温度設定の方法を以下に記します。

• \(\sqrt{S}*L<=7500\) のときは、温度の下限 \(left=\max(0,500-\frac{N\sqrt{S}}{2})\) 、上限 \(right=\min(1000,500+\frac{N\sqrt{S}}{2})\) とし、座標 \((L/2,L/2)\) とのマンハッタン距離が近いほうから \(i\) 番目の出口セルの温度を \(left+\frac{i(right-left)}{N-1}\) 度とする(要するに等間隔、実際のコードは少し異なるが本質的には同じ)

• それ以外のときは、温度の下限 \(left=\max(0,500-S)\) 、上限 \(right=\min(1000,500+S)\) とし、座標 \((L/2,L/2)\) とのマンハッタン距離が近いほうから \(\frac{N}{10-8(S*S/810000)}\) 番目の出口セルまでは \(left\) 度、それ以外の出口セルは \(right\) 度に設定する。

ただ、ここに関してはよりよい設定方法があると思うので、その方法はもっと上位の方の解説に任せます。

計測フェーズ

大まかに対応関係を特定する仮質問フェーズと、細かく対応関係を詰める本質問フェーズに分けます。

どちらも本質的な差はあまりなく、ワームホール \(i\) と対応する出口セルを特定するため以下のアルゴリズムを適用します。

• \(A_j\) がワームホール \(i\) に対応する出口セルが \(j\) である確率をもつ配列 \(A=(A_1,A_2,...A_N)\) を作成する。はじめ、\(A\) の要素はすべて \(\frac{1}{N}\) である。

• 以下の行動を質問回数が上限 \(lim\) 回になるまで繰り返す

  • 確率が高い( \(A\) の上位二つ) 二つの出口セルの周りの中で、温度の差が最も大きい移動方法を選択する (ただし、最初の質問では移動せず、その場で質問する)

  • 質問し、受け取った温度を \(temp\) とする。

  • \(j=1,2,...,N\) のそれぞれに対して、\(A_j\) に出口セル \(j\) から出て移動したマスで、温度 \(temp\) が観測される確率を掛ける。

  • \(A\) の比率を保ったまま、総和が \(1\) になるようにする。

  • \(A\) の最大値が \(border\) を超えたら、繰り返しを抜け出す。

このアルゴリズムをベースに、二つの質問フェーズでは以下のようにします。

仮質問フェーズ

\(lim=30\) 、\(border=0.95\) として、ワームホール \(1\) から順番にアルゴリズムを適用する。

ここで、\(A\) の最大値を基準に降順に並べ替える。

本質問フェーズ

並べ替えて得られた順番に、\(lim=\frac{(残りの質問回数)}{(特定できていないワームホールの個数)}\) 、\(border=0.997\) としてアルゴリズムを適用する。

ただし、\(A\) は仮質問フェーズで得られたものの総和を \(1\) にしたものを流用する。

ここで、最も確率が高いものを対応する出口セルとする。確率が \(0.68\) を超えた場合、これ以降、この出口セルに対応する \(A\) の値を \(0\) にする。

---

\(0.95\) とか \(0.997\) とか \(0.68\) の基準がわからないという声が聞こえてきますが、試してよかったものを選んだとかではなく半ば適当です。68–95–99.7則を知っている人はピンときたかもしれません。

追記:58位に上昇しました。うれしい。