AHC030復習 - 水たまり

　やったこと

解説ページにあるものを読んだ
特にwriter解を参考にして（細かい高速化などは省いて）自分なりにRustからC++に書き直し、自分の本番時より良いスコアを得る提出を実装した

理解内容

　解説ページが充実しているのであえて繰り返すまでもないが、自分の理解をもう一度書いておくと

(1) 複数の占いが所与のとき、事前分布が一様であるという情報から、事後分布は尤度に比例する。尤度は問題で定義されている通りのものを、正規分布の累積分布関数を使って計算できる。ここまではよくあるベイズの定理使用法。

(1') ただ、ありえる配置を全て列挙するのは $M$ が大きい場合には難しいので、焼き鈍し法で有力な配置をサンプリングする。これはMCMC（の特にメトロポリス法）と近いものと見なせる。

　（AHCラジオでの言及としては、温度1にすれば遷移ルールが同じになり、MCMCだと出現頻度を分布として見たサンプリングとして使うが、今回尤度が求めるので尤度を正規化すれば良い）

(2) 次の占い範囲の決定は、「占い結果がyになる」という事象と「真の配置が x である」という事象の相互情報量を求めて、相互情報量/コストが高いものとしたい。厳密に求めるのは計算量的に難しいので各マスの相互情報量を計算して山登り法で範囲を作る。

　一般に、「複数の選択肢から一つ選んで行動が可能なときに、得られる情報量が一番大きい行動を選択したい」ということはそれなりにありそうで、条件によってどこまで使えるのかはわからないが、考える一つの方針にはなりそう。

　(1), (2)両方とも、今までは「上位陣はなにかよくわからないことをやっているなぁ」という感じだったのが一歩理屈が見えてきて取っ掛かりが掴めてきた、かもしれない。それを実際に使えるレベルとなるとまた遠いのだろうが。

実装面

　手法自体を大まかに理解しても、実装してみると躓くところがいくつかあった。しょうもないパートとしては

累積分布関数と確率密度関数を勘違いして意味不明な値が出る
対数尤度から確率に直すときに、最大の対数尤度をベースラインとして引くことを忘れてnanが多発する
何と何の相互情報量を求めるのか混乱する
各クラスがどの情報を管理しているのかという関係がハチャメチャになる

などのことが起きる。今回はwriter解という指針があったので細かい実装のテクニックやクラスの切り方なども困ったらそこに立ち返ればよかったが、自分で考えて実装しているとまとめきるのは相当大変なことになりそう。

焼き鈍しパートがとても難しい

　最終的にはwriter解の遷移をそのまま真似することになったが、それでも精度が出きらなかった。seed 0019などでちゃんと収束していかない。また、処理の高速化もとても難しいのでかなり妥協して、制限時間を超えそうだったら諦めて[tex: N²]を全部掘るという処理にした。それでも間に合うケースでは自分の本番時よりとてもスコアが良いので総合的にも本番時超えには十分だった。

　操作回数が少なくなってきた場合に、できれば滑らかに1マス掘りへ移行させたかったのだが、焼き鈍しの最中で1マス掘りの確定情報と整合しない候補でトラップされて抜けられない、有効な遷移を作れないということになってそれも挫折した。

　何も考えずにやると遷移 $O(1)$ で、評価関数 $O(QK)$ （ $K$ はクエリの面積）になってしまうが、遷移 $O(Q)$ 、評価関数 $O(Q)$ とした方が良いというのは当たり前なんだけどそう。