参加しながら考えたこと試したことの源泉かけ流し。バッドエンドです。

問題概要

1 日目

問題を読む。こ、これは......マジで勝てるビジョンが見えない...！！！
風邪ひき始めみたいな体調だからか？まぁやるんだが...。

集合に対するクエリ投げたときの結果のブレ具合だけ先に確認しておきたいな。AHC022 では仰天したからな。
ん、分散はまぁなんかいいとして、平均が v(S) ではない？ (k - v(S)) と v(S) の間の特定の比率の点が平均になると。
あまりお気持ちがまだ理解できてないが...例えば v(S)=k/2 だと（つまり均せば選択したセルの半分を石油が占めてると）すると、分布の平均は v(S) になる。
ここから離れていくと、(k - v(S)) が真の v(S) と真逆みたいな項なので、なんか半数を石油が占めてる寄りに平均が偏りますよってことかな。合ってる？
どのくらい偏るんだろう。ブレ最大の ε=0.2 だと、k=10, v(S)=0 で平均 2？いやキツいな...。こうなると 1 マスに対する確定クエリを活用する必要がありそう。
まぁでも、ブレでかいときにコスト 1 未満で 1 セルの情報を推定できる気はあまりしないし、あくまで集合クエリは補助目的の使用になるのかなぁ。

1 マスクエリで確定したマスを含めて集合クエリを投げることで、少ない調査対象に対して低コストで情報収集できたりする？
ただこれも k が大きくなるとブレがデカくなるルールがあるから塩梅が難しそうなんだよな...。

クエリブレ具合の分散はまぁいいとしてって言っちゃったけど良くないな。
えーと、ϵ(1−ϵ) の部分はこれくらいで...

まぁ概算は ϵ(1−ϵ)≒ϵ で良さそう。
あとはこれがクエリ対象のセル数に比例。分散が x 倍になるとブレ方は sqrt(x) 倍くらいになる。
±3σ くらいに概ね収まると思って良くて、3σ=1 だとすると分散は 0.11。ほぼブレないみたいな状況はほぼないと考えて良いか。

例えば ε=0.01 で k=4 だと、μ≒v(S), σ≒0.2 なので、4 セル中 3 セル埋蔵量が確定しているみたいな状況だと残りの 1 マスをコスト 0.5 かつ 98.5% くらいの精度で推定できる。うーん、それでもちょっと精度が微妙か。

あと特定のマスの推定方法考える他にやんないといけないのが、入力で与えられる油田の形状の情報をどう活かすか。
やっぱり埋蔵量が確定したセルとパターンマッチングとかして、残りの未調査セルは調査せずに確定させるみたいなことをするのかな。
だとするとすごい細かい話だけど、特徴的なパターンが存在する方角から調査を進めていくのが良さそうな気がする。細かい話だけどね。
いやそんなに細かくもないか...？結局確定は 1 マスクエリでやっていくことになるはずだから、1 マスクエリの回数を減らすのはかなり本質なはず。
特徴的なパターンを如何に早く見つけるか。

そうなるとやっぱりブレでかいときの集合クエリの使い方がよくわからんな。使い道ある？

進め方としては

1マスクエリのみで上手に特徴的な部分を見つけて油田の形状で確定させていく
ε が小さい場合は集合クエリを索敵に活かす

の順でやっていくか？

今とあるセルが埋蔵量 1 であることが分かったとして、次何をするべきか。
そのセルがある油田のこの部分だとすると相対位置でここは埋蔵量 0 になるはずだよね、というのはあるはずで。
実際その相対位置の埋蔵量が 0 であれば情報を絞っていける。埋蔵量が 1 以上なら、ある油田のその部分ではないのかもしれないし、相対位置のとこに他の油田が被っていたのかもしれない。分からない。
みたいな調べ方になるのかなぁ。

2 日目

風邪気味なので何もせずに寝た。

3 日目

そういえば油田の数の最大値って何個なんだっけ...。20！？
解の候補（=油田の配置方法）って O(N^2M) 個くらいだから 3~4 個くらいまでなら候補を全部列挙して、埋蔵量明らかにすることで一番候補を絞れるセルに対して調査を行っていく方法が取れるな〜と思っていたが、これは油田の数の大小で方針切り替えないと厳しそうだなぁ。

初手の方針としては、以下の 2 つの方針を解の候補の数により切り替える感じにしたい。

油田数が少ない → 解の候補を列挙して一番候補を絞れるセルを掘っていく
油田数が多い → 埋蔵量が 1 以上のセルを適当に見つけたあと、右手法っぽい感じで埋蔵されてる/されてないの境界線を見つける

う〜ん、油田数多い方についてはもう少し詰めておきたいな。

解の候補、厳密にやると O(N^2M) なのだが、なんかうまいこと油田を独立に扱って O(MN²) くらいで良い感じのことをやれると良いんだけどな。
例えば埋蔵量 1 のセルが見つかったとき、これはどの油田のどこの部分なのか？の候補は O(MN²) とかな気がする。
ただまぁ、他の油田の重なりとかを考えつつそれ特定するのはかなり難しい気もする。うーん。

あと範囲クエリの使い方がまだ分かってない。
ε=0.01 のケースで k=2 で確定したセルの隣を調査するくらいしか思いつかない。これならさすがに 99.9% くらいの精度は保証されそうだし。
...まぁ、確定した情報しか扱おうとしてない時点で若干負け感があるのだが。
多分強い人たちはなんかこう、不確定な情報を低コストでかき集めてうまいこと推定するんだろう。なんたって強い人だから。

そろそろコードを書いていきますよ。僕が解を洗練させるのに必要なのは上位とのスコア差だからね...。

seed=0~999 での油田の数の分布を調べたので貼っておこう。

油田数 5 以下のケースと 6 以上のケースで半々くらい。
まぁ油田数少ないケースだけ詰めてりゃ良いって感じではない。

こっちは解の候補の数（の log10 を取ったもの）のヒストグラム。

厳密に候補を絞れそうな数に見えるのは良くて 3 割くらいかな。

こう見ると油田数が少ないケース向けの解から取り掛かるの悪手っぽいけど、でも方針固まってるのこれだけだから...。そのうちどうせ書くやつだから...。

とりあえず厳密に解の候補を絞っていくやつを書いた。
seed=0 で動かしてみると 12 手で回答していた。早くも人力じゃ勝てなくなってて面白いな。

メモ: ε=0.01 なら採掘済みのセルの隣をコスト 1/sqrt(2) でほぼ確推定できる。というかこれだけ少数手で答え出るなら推定ミスったときのリカバーもしやすいしもう少し冒険しても良いかもしれない。
メモ: 解の候補が 1 つ以上残っていても、すべての候補で埋蔵量が正のセルの形が同じであればそこで打ち切って良い。

やっぱり油田数多いケースでもこんな感じに確定すると嬉しいセルから掘っていく感じになるんじゃないかなあ。

ん、範囲クエリの使い方を理解した。
これブレ大きいんだから 0 か 1 かみたいなのを推測しようとしているのが間違いで、油田はこのあたりかな...？の推測に使うべきなんだな。
0 か 10 か、ならブレ大きくても高精度で推定可能なため。

これはまともに活用しなきゃ、油田が疎なケースでは勝ち目がなさそうだなぁ...。
そんで油田数が多くて密なケースの方針もまだ固まってないんだなぁ。勝てるのかこれ？

さっき実装した方針にもとりあえずこのアイデアは活用することができて、初手で範囲クエリを使って盤面をざっくりスキャンする。
で、その結果とかけ離れた解の候補はあらかじめ除外した上で絞り込みに入っていく。
これくらいなら実装もそこまで複雑じゃないし、それなりに効果もありそうに思える。
どうスキャンするかが効果的かは後で考えを練ったほうが良いかな。