AHC030 感想

はじめに

はじめまして。AtCoder緑レートの自分が初めてヒューリスティックコンテストに参加しました。

まずは参加してみようとのことで、まったく理論にもとづかず、雰囲気で実装したため、たいした情報はないですが、自己鍛錬としてアウトプットの量を増やしたいのと、ヒューリスティック面白いよ、というのをお伝えしたく、書き連ねます。(文字ばかりになってしまいました)

自分のスペック

今年の春で社会人14年目になるエンジニアです(特にアルゴリズム/ヒューリスティックを強く要求されるような現場ではないです)。
2019年くらいから競技プログラミングをやりだしました。AtCoderのアルゴリズム部門のレーティングは1000前後です(途中Unratedが続いて萎え落ちして2年くらい空白期間あり)。
ヒューリスティックは前から興味があったので参加しました。参加時点では山登りとか焼きなましとかは知識として知っていましたが、特に実装などしたことはないです。モンテカルロで円周率を求めたことだけありました。

問題

https://atcoder.jp/contests/ahc030/tasks/ahc030_a

ポリノミノ上の油田の形が与えられるので島の中のどこに油田があるか、実際に掘ったり占ったりして場所を当てる。

提出した解法たち

1日目(2/9)

とりあえず最初はサンプルプログラムの同様、島を全部実際に掘って油田の位置を特定し、結果を出力するプログラムを提出しました。これでヒューリスティック経験者です。

次に、油田の形があらかじめ与えられ合計数も確定しているため、
採掘した油田数が合計数に達したら、それ以降は掘らずに結果を出力するプログラムを提出しました。
ちょっとだけ順位が上がりました(得点:11411000000)。

2日目(2/10)

気づいたらずっとテストを作っていました。何度もプログラムの修正/実行を繰り返すので、サンプルを手でコピペするのは大変辛いです。公式のビジュアライザからテストケースが大量にダウンロードでき、300個くらいローカルに落として自動で各テストに対してコスト算出する仕組みを作りました。だいぶ時短になったと思います。ほとんどchatGPTさんに聞いて作ってます。

解法についてですが、占いを使っていなかったので、なんとかこいつを使ってコストを下げたいなと考えました。ビジュアライザ見ながら考察したところ、０がたくさんあるところを掘っていくのが無駄そうです。占いで０ではない箇所を推測して、そこから優先的に探索していけば良さそうです。
また、油田の制約上大きさが4以上かつ上下に繋がっていることから、0に囲まれたマスは掘らなくても良さそうなので余計な採掘を減らせそうです。

その日の最終提出したコードは、次のような処理を行いました(得点:6570340141)。

1. 行列でそれぞれ占いを行う。
2. 各マスごとに行列の結果を掛け合わせた値を求める（この値を自分の中ではワクワク度と勝手に名づけました）
3. 掘った油田数が合計数に達するまで以下の処理を行う
   1. まだ掘っていないマス目のうち値の高いマス目を掘る(A)
   2. 油田のマス目ならその上下左右を優先して掘る
   3. 周りを掘り尽くしたら(A)の処理に戻る

3日目(2/12)

行列単位で占うと、油田の場所が判別つかないケース(例えば、右上左下に固まっているケースと右下左上に固まっているケース)があるというデメリットを見つけたため、占うやり方を変更しました。島を縦横をいくつかの区画に区切った方がより良さそうです。区画の大きさですが、大きいのが二つあるようなパターンで、小さく区切ってもあんまり意味なさそうだったので、油田の形のうち一番小さい大きさに合わせて変動するようにしました。

また、せっかく油田の形が与えられているので、この情報を使いたいなと思いました。
ですが当方の引き出しがなく、このデータをうまく使う方法が思いつきません。いや、ありました。私にはモンテカルロが。
ということで、初期にランダムに油田を配置したパターンを無数に作り、あらかじめ占った結果との誤差(区画ごとの誤差の二乗の累計和にしました)が少ないパターンを持ってきてワクワク度を計算するといった流れに変更しました。
この日に提出したコードは下記のような処理です(得点：6067890239)。

1. 区画ごとにそれぞれ占いを行う。
2. ランダムに油田を配置したパターンを無数に作成する(A)
3. 作成したパターンのうち実際の採掘結果と矛盾するものは破棄する。
4. 作成したパターンと占い結果を比較して誤差の少ないものを選定する。
5. 選定したパターンの各マスを足し合わせてワクワク度を計算する。
6. 掘った油田数が合計数に達するまで以下の処理を行う
   1. まだ掘っていないマス目のうち値の高いマス目を掘る。
   2. たまに(A)からやり直す。

(A)からの再実行をたまにしか行っていないのは、毎回行うとタイムアウトのリスクが高くなるからです。

seed0ではほとんど0のマスを掘らなくなりました

4日目(2/13)

武器としてモンテカルロしか持っていないのですが、なんとかこいつを改善していきたい気持ちになりました。
まず、ランダムに生成されるパターンをなるべく正解に近いっぽいものにしたいです。
そこで各油田に対して生成可能な各位置にそれぞれ初期値を1とした重みを設定します。
採掘した結果0が出た場合、そのマスにかぶるような油田は生成することができないので、対応する各位置の重みを0にします。また、誤差が低いものとして選ばれたパターンの配置は再度選定されるように重みを増やすといったことを行いました。

重み付け処理に加えて、今までは採掘した油田数が合計数に達するまで結果を出力していませんでしたが、誤差がある一定以下のパターンを見つけた場合は、とりあえず回答してみるようにしました。

この日提出したコードは以下のような処理です(得点:5325890239)。

1. 区画ごとにそれぞれ占いを行う。
2. ランダムに油田を配置したパターンを無数に作成する(A)
3. 作成したパターンのうち実際の採掘結果と矛盾するものは破棄する。
4. 作成したパターンと占い結果を比較して誤差の少ないものを選定する。
5. 選定した各パターンの油田位置の重みを上げる。
6. 誤差が一定以下のパターンが存在していた場合は、回答を行う。
7. 選定したパターンの各マスを足し合わせてワクワク度を計算する。
8. 掘った油田数が合計数に達するまで以下の処理を行う
   1. まだ掘っていないマス目のうち値の高いマス目を掘る。
   2. 油田数が0であった場合は、その位置を含んだ油田が生成されないように重みを変更する。
   3. たまに(A)からやり直す。
      
      とうとうエスパーできるようになりました！

5日目(2/14)

seed19と戦っていました。占い誤差が0.1と大きく、油田数も多いため、油田のない地帯にも油田があるかのような占い結果が得られてしまい、最後の方はなかなか油田を特定することができません。　追加で何回か占うと良いのかな？とも考えましたが、最終的には油田数が多い時は、ある程度油田を掘り当てたらそこから判明している油田の上下左右を掘っていく幅優先探索を併用するようにしました。これが最終提出となりました(得点:5132890239)。

1. 区画ごとにそれぞれ占いを行う。
2. ランダムに油田を配置したパターンを無数に作成する(A)
3. 作成したパターンのうち実際の採掘結果と矛盾するものは破棄する。
4. 作成したパターンと占い結果を比較して誤差の少ないものを選定する。
5. 選定した各パターンの油田位置の重みを上げる。
6. 誤差が一定以下のパターンが存在していた場合は、回答を行う。
7. 選定したパターンの各マスを足し合わせてワクワク度を計算する。
8. 掘った油田数が合計数に達するまで以下の処理を行う
   1. 条件を満たした場合は幅優先探索を行う
   2. そうでない場合は以下の処理を行う
      1. まだ掘っていないマス目のうち値の高いマス目を掘る。
      2. 油田数が0であった場合は、その位置を含んだ油田が生成されないように重みを変更する。
      3. たまに(A)からやり直す。
         
         ラスボスとして名高いseed19

最終解法について

0のマスを開けるとランダム生成される油田の場所が絞り込まれるため都合が良いですが、0以外のマスについては特にランダム生成時に何も考慮していませんでした。生成後に採掘結果と矛盾していないかという処理を行っていたため、たくさん0以外のマスを掘ってしまうとランダム生成したパターンが破棄される数も多くなってしまい結果として何も選定されなくなるという事態が発生してました。また、油田を全て掘るのが基本方針なので、0のマスを掘ってパターンの絞りこみを行うという方針が合っていないため無駄に採掘回数が多くなっているのではないかと、改善点がたくさんあるなぁと思いつつの提出になりました。この辺はもっと勉強して次回に活かしたいです。

提出したコードは下記に置いています.
https://github.com/hirohiso/AHC-030-PolyominoMining

(探索的にコーディングしているとブランチ管理が雑になるんですが、みんなどうしてるんでしょうかね・・・・)

最後に

完走した感想ですが、特に専門的な知識を持っていなくてもとりあえずの提出ができるというのがAHCのいいところなのかなと思いました。思いつきの処理を試しに入れ込んでいくのが、オープンワールドゲームやっているのと同じような楽しさを感じました。
反省点としては入力の制約や生成方法の制約などはもっとちゃんと読んでおけばよかったと思いました。(seed19みたいなのは全体の割合としてそこまで生成されないことがわかり、時間かけなくても良さそうと判断できる)
とても面白かったので次も参加したいと思います。油田を掘り当てて石油王になりたい人生でした。

LINEスタンプ うさぎ帝国 推しが尊い２より