解説
最終解法の概要
(基本)1マスずつ掘って、油田の位置を絞り込んでいく解法です
ざっくり埋蔵量把握
Mが6以上 かつ 埋蔵総量がエリア(N^2)の4割以下の時、(N//5+1)^2分割の正方形でエリアを占って、ざっくりとした埋蔵量を把握します
後述しますが、0を狙って掘りたい時と、1以上を狙って掘りたい時があります
全く埋蔵量の期待ができない箇所を掘っても意味がないため、その優先度を決める際に使います
埋蔵量0位置による油田配置箇所絞り込み
埋蔵量が0の位置によっては、油田を置くことの出来ない場所を判定することができます
実装上は左上を基点として、最大N^2の要素をSortedSetで持って管理しました
ただ、未探索エリアが広いと中々絞り込みが進みません
埋蔵量1以上位置による油田配置箇所絞り込み
埋蔵量が1以上の位置について、その場所に置かれ得る油田の種類数が同じ時、その油田については必ずそのマスを使うことが確定します(説明画像略)
実装上は各マスごとに、置かれ得る油田の種類をsetで持って管理しました
油田の配置を必ずしも1つに確定する絞り込みではありませんが、かなりの量を絞れるため他の絞り込みと複合して大きな効果を発揮してくれました
埋蔵量オーバーを加味した油田配置箇所絞り込み
埋蔵量が1以上の位置と、既に確定した油田の位置がある場合、他の油田を置くことができないことを判定できます
実装上は各マスごとに、確定した油田の種類をsetで持って管理しました
油田配置可能箇所による埋蔵量0位置の確定
ここまでで絞り込んだ、油田配置可能位置を全探索して一度も触れられなかったマスは、必ず埋蔵量が0なことが確定します
いずれかの絞り込みで変化が発生した場合は、絞り込みをやり直しています
1マス掘り場所取得・実行
未調査マスについて、評価値の一番高いマスを調べます
評価値の基本は、油田配置可能位置を全探索してマス位置に値を加算していきます
より多くの選択肢に影響を与える位置を調べたい気持ちがあります
油田サイズ(マスの量)の最小が9以下の時、1以上の埋蔵量位置を含む油田配置にボーナス点を付与しています
その理由としては、油田サイズが小さいと埋蔵量0マスを埋めていくことによる、油田配置の絞り込みが機能しにくいためです
また、埋蔵総量がエリア(N^2)の3割以下の時、その傾向を強くしました
ε=0.01の場合、2マス占ってもほぼ100%真値が得られるため、埋蔵量0が確定したマスと一緒に2マス占うことで、コストを抑えました
その他の工夫
油田の置き方の絞り込みが進んで10^5パターン以下になった場合、現状の配置に矛盾しない配置を一つ探し、そのマスの評価値を下げました
直接掘るより、他を掘って絞り込みを進めた方が良いスコアが出た気がします
提出コード
pypy3で書いています
参加記
はじめに
久々の長期AHCということで、かなり楽しみに待っていました
それなりに時間は取れそうなので、納得するまでやり切りたいです
意識すること
・評価関数は指標(単位)を揃えて考える
・説明できるレベルまで考察してから実装する
・差分計算を頑張る
・推定から逃げない
1.問題
N×Nマスの島に、M個の油田がありその形状は示されている
少ないコストで、油田を含むマスを特定せよ
島の大きさ 10≦N≦0
油田の個数 2≦M≦20
エラーパラメータ 0.01≦ε≦0.2
2.開始直後の考察
苦手意識のあるインタラクティブ形式だ...
v(i, j)>0であるマスを特定する=全油田の場所を特定する(とは少し違う？)
1マスを掘ると確定するなら、N^2のコストが下界になる
複数マス掘る場合の分散を含んだ値をどう扱うかがキモになりそう
低コストで大量に掘る方が高得点になる場合があるかも
全てv=0の集合を掘った場合に、全て0であると確定できるkの範囲がありそう
バラツキのある情報は、ベイズ推定でやれそう（使ったことない
各マスについて石油埋蔵量v=xである確率とか？
ポリオミノをそこに置いた時の確からしさが見れそう！
ビジュアライザを見て、思ったより空の区画が多い
形状によってはv=0の区画を最初に確定できる
3.貪欲解
Pythonのサンプルプログラムが用意されていたので読みます
全てのマスを掘って実際に石油が出たマスを出力するだけなので、これよりマシな貪欲解法を考えてみます
既に得た情報(特に石油量0のマス)から、各油田がどこに置けそうかは全探索で試せば見つけることができます
出来るだけ石油量0のマスを掘らずに～ということを考えていたら、石油が掘れそうなマスから掘っていけば良いのでは。と思いました
0で初期化したN*Nの変数に対して、各油田が置ける場所を全探索しマスに加算していきます
最も大きい数字となったマスが、期待値が高くなるはず。という算段です
また、石油量が0だった場合でも、そのマスを含む油田の置き方はできないことがわかるため、探索位置の絞り込みに使えます
以上の解法でseed=0を解いた時の出力が以下になります
見るからにサンプルより強い解法にすることが出来ました
現在、コンテスト開始初日の25時で、9位につけることが出来ました
筋は悪くない。という感じだと思いますが、1マス掘りだけではこれ以上は厳しいかもしれません
複数マス掘るやり方を頑張って考えてみます
4.複数マスの考察
複数マスを占った際、埋蔵量の総和にバラツキを含めた値を得ることが出来ます
以下は、エラー率εと総和v(S)を固定してマス数kを振った時のデータになります
正規分布の累積分布関数を用いることで、ある値xが得られたとき元になった総和の値についての確率を得ることができます
例えばk=2の時、v(S)=1は24%、v(S)=2は71%であることがわかります
問題は、各マスの情報をどう更新するかですが
2マス調査して総和が2である確率が71%だとして、2マスの埋蔵量の組み合わせは(0,2) (2,0) (1,1)の3パターンあることになります
71%を3分割して、この調査について各マスがその埋蔵量である確率に累積して、最後に各マスの情報を更新していけば良い気がします
今わかっている問題点としては、エラー率が高い場合は4マス調査をしても埋蔵量の判定をしきれない→1マス掘ったほうがマシということです
ここで、埋蔵量が0のマスを効率的に調べていけば油田の場所が一意に定まり、調査回数を減らせそう。と気付きました
調査する対象は貪欲に決めたいですが、焼きなましやシミュレーションで期待値を求めるやり方もありそうです
5.エラー率調査
複数マス計測時のエラー率について、どれくらいまで使えそうか確認しました
seed=0について、計測値を1に固定した上で4マス計測し、エラー率を振った際に得られる値になります
エラー率0.05あたりから、結構外れた値が返ってくるように見えます
エラー率0.2までいくと、平均値も上がっている影響でほとんどの場合で真値とは違う値が取得されてしまうようです
ちなみに、2マス計測時は以下のようになります
これくらいなら使えそうですが、今はどう使うか思いつかないので後回しにします
6.1マス掘り戦略再検討
1マス掘り戦略に立ち戻って、別の戦略を考えます
油田mが(i, j)を基点としたマスに配置される確率を考えると、
全マスについて、埋蔵量の期待値を出すことができます
1マス掘った際の実際の値と期待値の誤差を修正するように確率を補正していけば、正解の配置に近づくような気がします
計測した結果と期待値の差diffに学習率θを掛けた値を、そのマスに影響している箇所に引き算をして補正します
4,5時間かけてなんとか実装しましたが、N,Mが大きいパターンだとTLEしてしまう上に制約が小さいパターンでも優位な結果にはなりませんでした...
ただ、期待値という考え方はアリに思えます
7.ボツになった戦略たち
- 各油田の基点(i, j)確率を推定
- 各マスの埋蔵量期待値を推定
- 各マスの埋蔵量が0~5である確率をそれぞれ推定
- 埋蔵量1以上のマスからBFSで埋めていく
- 判明しているマスに矛盾しない油田配置を探索（検討中
埋蔵量期待値を求めるアニメーションはいい感じだったので、ここに貼りつけて供養とします...
8.1マス掘り戦略再々検討
最後の週末まで、推定で頑張れないか色々トライしていましたがいよいよ諦めて、1マスずつ掘っていく方針を詰めていくことにします
自分のやり方としては、手元で100ケース回して苦手そうなケースやまだ伸ばせそうなケースについて、随時対策していく感じで改善してきます
今回は、相対得点なのでスコアのlogをとった値の総和を評価しています
(cost100→99より、cost10→9になるほうが大事)
詳細は最終解法の方に書くことにしますが、以下のような改善をしました
- ε=0.01の時、埋蔵量0のマスと一緒に2マスで占うことでコスト低減
- 埋蔵量0のマス配置的に、油田の配置を確定できるときは確定する
- 掘り済みマス目線で、ある油田しか配置しない場合は、そのマスを使用しない油田の配置箇所を探索しないようにする
- マップに対して埋蔵量が少ない時、広めにサーチしてざっくり埋蔵量の分布を見る
- 油田の最小サイズによって、0を埋めるor埋蔵位置を埋めるかを切り替える
- 判明している埋蔵量に矛盾しない配置を一つ決めて、それ以外を優先して調査
9.おわりに
バラツキを考慮した方針をなんとか使いたいと頑張りましたが、結局扱いきれずに終わってしまいました
ベイズ推定について、自分なりにコードに落とすことまでは出来たので、延長戦までしっかりやって理解を深めたいです
