はじめまして、notkamonohasiと申します。
AHC022お疲れさまでした。システス後46位でした。
Twitterを見る限りでは、自分の解法がかなりレアだったため、人生で初めてブログを書いてみようと思った次第です。
軽実装かつ難解な統計知識なしで高順位を取れるというのが自分の解法のメリットです。
紹介した手法の強さを計測するために、各手法毎にPythonの実装例と延長戦順位表を掲載しています。
解法概要
1点だけ温度を超高温とし、他の点を0とします。各ワームホールについて、出口セルからどの位置に超高温セルがあるかを特定することで、どの出口セルにつながっているかを特定することができます。
結果としてはσ=900, N=75程度までの難易度ならノーミスを実現できます。
前提知識
正規分布が何か分かっていれば十分だと思います。
数式ないです。アルゴリズム使いません。
解法詳細
1. そのセルが0か超高温かの判定方法
一点高温解法の肝であり、判定精度が悪いと何もできないので、ここを詰めるのは非常に重要です。
あるセルの温度を適当な回数測定したときに、そのセルが0度なのか超高温（以下分かりにくいので1000度と言ってしまいます）なのかを知りたいです。
直感的には測定結果の平均値が閾値を超えていればokだと思います。しかし、この閾値が小さすぎると上振れ・下振れに弱くなってしまいますし、逆に大きすぎると同じ場所を無駄に何度も測定する必要が出てきてしまいます。また、この閾値はσによって変える必要があり、各σについて適切な閾値を求めるのは面倒です。
そこで自分は1回の測定に対する評価値xに対する評価値を「実際の温度が1000度の時に測定値がx度になる確率」÷「実際の温度が0度の時に測定値がx度になる確率」としました。この評価値は数学的には「測定値がx度の時に、そのセルの実際の温度が1000度である確率は0度である確率の何倍か」ということを意味しています。例えば、この評価値が1万倍であれば1000度で一発で確定だし、10倍程度であれば「不安だからもう一度計測しておこう」という気持ちになります。
この評価を各ワームホールについて、全ての出口に対して行っていけば、各ワームホールに対応する出口を見つけることができます。しかし、「全ての出口に対して3回ずつ計測する」などの方法は非常に無駄が多いです。計測しているうちに、明らかに温度が高い点・低い点が見つかるからです。そこで、Dijkstra法の様に「今最も評価値が高いセル」を見ていき、この評価値が閾値を超えたら終わりにすれば良いです。
一点高温解法で点数が出なかったとおっしゃっていた方達との差は恐らく、上記2つの評価値の計算方法と、計測の順番だと思います。
評価値の実装方法については、Pythonであればscipyを使うことで楽に実装できます。C++には多分ないので、累積和を使って確率累積分布を前計算して、高速に計算できるようにしておきます。
ここまでのアイデアを実装すると、最終68位相当の点数が取れました。実装量は大量のコメントアウトを含めて200行弱です。この実装量で長期コンテストの68位を取れるのはヤバいですね...
2. 計測コストを下げる工夫①
更に順位を上げるためには設置コストか計測コストを減らすことが必要です。ここでは、計測コストを下げることを考えます。
1.の段階だと、出力は下図のようになっています。
見て分かる通り、出口から離れた場所を何度も計測してしまっています。計測コストは出口から離れるごとに大きくなるので、なるべく出口から近い場所を探索したいです。
評価値が同じ場合は、1.の段階ではindexが小さい順に計測していますが、出口から近い順に測定すれば良いです。このアイデアを実装すると出力は下図のようになります。
測定コストを小さくできました！
提出すると最終58位相当の点数が取れました。実装量は200行です。
3. 計測コストを下げる工夫②
（かなり細かいので、初心者の方は見なくて良いです！）
2.ができていれば十分ですが、実はまだ計測コストを下げることができます。
σが大きい場合、測定結果が下振れてしまうことにより、1周目の測定で正しい出口を見つけられないことが少なくないです。その場合は、1週目の測定で比較的マシだった出口を順にみていくことになりますが、出力は下図のようになります。
(5, 9, -10)までが1周目の測定で(5, 1, -2)以降が2周目の測定です。2周目で出口から離れたセルを何度も計測しているため、計測コストが跳ね上がっていることが分かります。1周目で正解を見つけられなかった場合でも、計測コストを小さくしたい気持ちになります。
これを実現させるためには「入口を固定して出口を見つける」のではなく、「出口を固定して入口を見つける」という発想の逆転が必要です。例えば、1000度のセルから(-2, -2)の位置にある出口に対応する入口を見つけたい場合は、(0, 2, 2)→(1, 2, 2)→(2, 2, 2)→...を出力することになります。具体例から分かる通り、何度計測しても計測コストは変わらないので計測コストが増加するのを防ぐことができます。
入口を特定する出口の順番は、2.と同じように計測コストが小さい順とします。
上記のアイデアを実装して最終51位相当の点数が取れました。実装量は相変わらずです。
自分の解法の評価
siman様が出してくださった結果を見ると（siman様ありがとうございます！）、σ=784で最高の15位を取れているにもかかわらず、σ=25で最低の155位となっています。自分はσ<=16で解法を変えているので、かなりσが小さなケースで弱かったようです。
自分の解法での計測回数の期待値は、(N^2)/4となっています（全組合せがN^2、「すでに結果が確定した入口・出口を見ない」で÷2、「途中で見つける」で÷2）。主流の解法では、σが小さなケースでNに比例した測定回数で正解を見つけられそうです。そのため、σが小さいケースが弱かったと思われます。
更に点数を上げるには？
Twitter上の議論を見て、「温度が高い点の四方を、0.25倍の温度とすることで設置コストを3/4にできる」ということを知りました。温度1000を置く関係上、設置コストが膨大となっていたので、これに気づけなかったのは非常に悔しいです。
最後に
AtCoderの皆様、そして日本橋ハーフマラソン事務局の皆様、コンテストを開催してくださり、ありがとうございました！
おまけ
救済ありがとうございますm(-_-)m
