2023/08/11(金)12:00 ~ 08/20(日)19:00 の約1週間，RECRUIT 日本橋ハーフマラソン 2023夏(AtCoder Heuristic Contest 022) が行われました．
AHC参加5回目，Heuristic緑色の私は暫定427位/最終421位というまずまずの結果でしたが，取り組む中でいろいろ勉強になったので参加記を書きます．
前回の参加記は参加3回目のときで，人によっては1回飛んでるように感じられるかもしれません．気のせいです．
目次
問題概要
N個のワームホールがあり，入口と出口の対応を当てるゲーム．入口と出口は1対1に対応しており，異なる入口から入って同じ出口に出ることはない．
手がかりになるのは，温度．
あらかじめグリッド上の全てのマスに温度を設定しておき，任意のワームホールから入って，対応する出口から好きなだけ動いた位置で計測した温度を頼りにする．
難しいポイントは，
- 計測段階ではどの出口が対応しているのかは分からない
- 計測値は「真の温度+ノイズ」．ノイズはめっちゃ大きいケースもある
考察
とりあえずサンプルコードを提出して出席点をいただく．
絶対得点3,467,623点．
サンプルコードでは，各出口に10刻みで温度を設定して目印を付け，出口の計測値と最も近いものを推定結果としていた．
正直，これより良い解法がパッと思いつかなかったので，今回もダメかなーと半ば諦めモード．
せめて温度変化をなだらかにした方がコストが減ってマシになりそう．
それならグリッドの中心を0にして縁のほうへ離れるほど高温にしたほうが全体的によさそう．
じゃあ中心に近い出口から順に10刻みで温度をつけて，全体を均せばよさそう．
中心に近い出口から温度を設定する：各出口について中心からのマンハッタン距離を計算し，昇順ソートしたものに10刻みで温度設定．
全体的に均す：出口以外は周囲4マスの平均をとる．これを10,000回繰り返すと全体的にいい感じになった．(多分安定するまで10,000回もいらない)
75,704,338点．1ケタ伸びた！
温度分布はマシになったが，出口は10刻みなのでちょっとノイズが大きくなるだけで精度が悪化する．
ノイズの影響をもろに受ける1点計測だから良くないのかな．
周囲4方向にちょっと離れたマスの温度も計測して，計5点の平均を推定値にしてみたけど，あんまり良くならなかった．
さて，何も思いつきません．助けて～．
どうにもならないので，過去の類似のAHCを探して，その上位解法をパクる参考にすることにする．
そういえば，「ノイズ付きのoutputからinputを推定する」という構造がAHC016 Graphoreanに似ている．
公式解説やユーザ解説を見ていく．
上位解法は解説を読んでもよく分からない．公式解説を見てみると，何やら確率を使ってる．いかにも推定って感じ．
ふむふむ，各inputから計測値(output)が生まれる確率を計算し，最も高いものを推定結果としているのか．
これなら今回もできそう．
今回は入力で与えられるSを使って，平均0，標準偏差Sの正規分布からサンプリングした値がノイズとなっている．
これより，ある計測値に対し，各出口で真の温度とSの値を元にz得点を計算し，正規分布で±z得点以上の範囲の面積(確率)を算出．確率が最も高いものを推定結果とする．
z得点の計算は良いとして，面積の算出はどうやるの？積分するプログラム書けるの？？
知らん知らん！そんなもんは知らん！！
標準正規分布表からベタ書きじゃい！！！
はい提出提出～！！
211,911,324点！！！
うぇ～～～い(また1ケタ伸びた)
そしてこのまま，ちょっとだけパラメータ調整して最終提出を迎えました．
最終提出
- 配置
- 各出口に，中心からマンハッタン距離で近い順に10刻みで温度を設定．
- その後，配置時コストを減らすために全体を均す．
- 計測
- S=1の場合
- 出口を1点計測．
- 各出口についてその計測値以上に誤差のある値が計測される確率(の半分)を算出．最も確率の大きいものを推定結果とする．
- S>1の場合
- 出口1点と周囲4方向に7マス離れた地点の，計5点計測．
- 計測した5点それぞれでS=1と同様に確率を算出．それらを掛け合わせた確率が最も大きいものを推定結果とする．
- S=1の場合
結果
次に生かせそうな知識・テク
- output(計測値)が得られる確率から推定する
- 推定の基本的な考え方だと思う．
- 詰まったら過去の類似回を参考にする
- 今回に応用できるかな？などと考えるので記憶に残りやすい．
- 簡単なケースでは着実に点を取る
- AHC016公式解説でwataさんが「今回の点数計算式を見ると，ノイズが大きいときに1個でも多く当てるよりも，ノイズが小さいときに確実に当てるのが大事」というようなことを仰っていた．
- 今回もそうなのかは分からないが，小さいノイズのケースで確実に当てるのは，同様のアルゴリズムを採用した集団の中でも高い順位を狙うという点で重要だと思う．今回はS=1だけ低コストで確実に当てるようにした．
- 小数の積はlogを使う
