基本マラソンはあまり真剣にやらないんですが、今回はできそうなことがありそうなのでちょっと時間をかけてみました。

暫定200位よりちょっと悪いくらいらしいので、私の実力にしてはよくやったほうだと思います。
私は焼きなましだとかビームサーチだとか、マラソン界隈でよく耳にするアルゴリズムは一切書けないし、統計に関する知識もほぼゼロなので、そういう知識を使わない解法になります。

提出順に書いていますが、改善がないやつとかパラメータ調整程度の提出は省略します。
スコアは絶対スコアです。また、N投目のNは間違えてる可能性あります。WAやTLEは除いています。

1投目、12696000000点

サンプルプログラムを投げるだけ。私はPythonアンチなので、Rustに書き直して提出した。（というのは半分嘘で、サンプル見る前に書いてたプログラムがたまたまサンプルと同じアルゴリズムだっただけ）

3投目、10554000000点

明らかにどの油田も来ないような位置は全探索で容易にわかるので、それを調べないようにする。

端っこから順に掘るのはなんか無駄そうなので、順番を工夫する。
この後何回かパラメータは調整したが、この時点では、配置されうる油田の数が多いマスを優先し、あとはなるべく隣り合うマスを連続で調べないようにした。

探索順の調整を頑張る。

油田があるマスもないマスも割と集約して位置するような気がするので、周囲の油田がないことが確定しているマスの数に合わせて適当なペナルティを振ることにする。油田があるマスの周りに油田があることは多いと思うので、周囲に油田があるならその分はペナルティを減らしてあげる。

ペナルティの振り方はよくわからなかったが、周囲の油田がないマスの数の5倍から油田があるマスの数を引いた数の平均が良さそうだったので、これでソートしてペナルティの少ないほうから探索した。

また、配置が確定した油田は最初に掘るように工夫したのもこの時点。

正直コードを見直しただけでは9投目との違いが何か判らなかったが、バグフィックスをしたら点数が上がったらしい。

よく考えると、M=2なら配置をすべてメモできるので、ダメな配置をより細かく把握できる。
なので、M=2のときだけやりかたを変える。

やりかたは単純で、全配置をメモして、1点掘るごとに現時点で可能な配置を全探索してダメな配置をリストから排除する、をひたすら繰り返す。

M=3のときも、頑張って高速化すれば全状態列挙ができるので、7投目のときと同じように全探索ベースで頑張る。

これも11投目と何が違うのかよくわからないが、同様にバグフィックスや高速化で点数が上がったらしい。

M>3のときでも、状態数が十分小さいことがわかっていれば全探索ベースでいけるので、あり得る状態数が一定の閾値を下回った時点で全探索ベースに切り替えるようにする。

たまに、掘っても掘っても状態数が小さくならないような場合があり、このときは下手するとTLEするので、タイマーで一定の時間を上回った時点で元のルーチンに戻ってくるようにしている。

基本的にはパラメータ調整しかしていない。

最後の方は、M>3の場合にいかに状態数を効率よく減らして全探索ベースのルーチンに持ち込めるかを考えていたが、あまり良い手は浮かばなかった。

全探索ベースのルーチンを高速化して閾値を上げられるようにすればスコアは上がるだろうが、具体的な高速化の方法はわからなかった。

結局、eの使い方は最後までわからなかったので、読み捨てて何にも使いませんでした。
複数掘削で油田がない位置を効率的に探し当てられないかとか考えましたが、eが相当小さくないと探し当てるのは無理だなという結論になりました。

全探索ベースの解法の高速化の方法がわからなかったのも痛かったです。フローとか使えるんかなーとか、ビット演算で頑張れないかなーとか、雑なことは考えていましたが、効果的なものはわかりませんでした。