AtCoder Heuristic Contest 030

　暫定64位。

考えたこと

ソフトマックス分布を使いたい

　 $M$ 個ある各油田について、それぞれ左上のマス位置が $i, j$ である確率を保持してみたい。これは $i, j$ についてlogitを持つSoftmax分布として表現したくなった。

　この分布を持って、マップ全域について期待値を取っていけばどのマスにどの程度の量の油田がありそうかを予測することができる。

微分で分布を改善できそう

　この分布をクエリの結果から改善したい。各マスについて、予測した値と1マスクエリ結果の値の自乗誤差を損失関数として誤差を微分すれば良さそう。損失の式を考えて連鎖率を追っていくとそれっぽい値は出てくる。

　（しかし、結局Softmax関数の正しそうな勾配の式は遅いし精度も悪化するしで、謎の嘘勾配を使った。この式じゃ間違っているっけ？うーん）

0マスを確定すると大きい

　1マスクエリで0が確定すると、そこに油田の量が発生するような置き方をするのは不可能ということがわかり、かなり分布を削ることができる。それを狙っていく。

　どのマスで1マスクエリをかけるか。確定することで得られる情報が多いのは、0か1以上か不確かなところとなる。つまり、期待値が0.5くらいのマスを優先的に調べていく。この調べ方でかなりスコアが改善された。

おまけ程度に複数マスクエリの使いみちを探す

　各油田から配置パターンをサンプリングしてきて、その配置パターンでクエリをかける。やはり自乗誤差を考えるが、各マスではなくクエリマス全体の和を取ってから損失計算ということになるので精度はそこまで出ないようだった。一応最初の方にフィールドサイズの $N$ 回だけ入れた方がちょっとだけマシになったので入れた。