THIRD プログラミングコンテスト2023（AtCoder Heuristic Contest 030）参加記

超久々の更新です。最近はまんまと猫ミーム中毒です。

さて、この度参加したTHIRD プログラミングコンテスト 2023（AtCoder Heuristic Contest 030）で 237 位を取り、ついに AtCoder のヒューリスティックレートが青色になりました。アルゴヒュ併せて二年以上ぶりの色変です。長かったです。嬉しいです。

問題自体もとても楽しくいろいろ収穫のあったコンテストだったので記録を残したいと思います。

問題概要

問題本文はこちら。

• $N$$\times$$N$マスの島の中に$M$個の油田が埋まっている。
• それぞれの油田は$1$$\times$$1$マスの正方形を上下左右に繋げた連結なポリオミノの形(テトリスみたいなイメージ)をしていて、事前にその形状も向きも分かっているが、島のどこにあるかが分からない(別々の油田同士が重なっている場合もある)。

• 島の中で油田が埋まっているマスをなるべく少ないコストで過不足なく言い当てたい。そのために毎ターン以下の行動が取れる。ターン上限は$2$$\times$$N^2$。

  • どこか 1 マスを選択して掘る。そのマスに埋まっている油田の量が分かる。コストが 1 かかる。
  • 好きに選んだ 2 マス以上の集合$S$を選んで占う。選んだマスに埋まっている油田の量$v(S)$に誤差を乗せた値が分かる。$k$マス選んだ時にコストが$\frac{1}{\sqrt{k}}$かかる。
  • 油田が埋まっていると予想したマスを回答する。正解か不正解が分かる。コストが 1 かかる。

最終的な解法

提出コードはこちらです。

流れは以下フローチャートの通りです。
ポリオミノのありうる配置パターンをうまいこと減らしつつ全探索というアイデアでした。
ポイントとしては、

• 各ポリオミノが存在しうるマスのパターン絞り込み

  • 最初に占ってポリオミノがいそうな領域をぼんやり把握
  • 数マス試し掘りをしてポリオミノが存在しうるパターンを減らす
• ありうるパターンを DFS で全探索して一番油田が多そうな配置を回答

DFS での全探索を開始するか否かを決める閾値を用意してあり得る配置パターンの数で毎回判定していたのですが、この調整が曲者でした。

閾値を大きくする
⇒ 早い段階で解が見つかる可能性が増すが、やり過ぎると TLE で 0 点のケースも増える。

閾値を小さくする
⇒TLE のリスクは減るが、全体的にスコアが落ちる。

入青がかかった勝負でどこまでぶっ込むか非常に悩んだのですが、大量 TLE を見たら完全に心が折れそうだったので無難な調整に落ち着きました(DFS_LIMIT=$3$ $\times$ $10^6$)。

なお結果

ビジュアライズ結果

最終提出コードで seed=0 と seed=1 のテストケースをそれぞれビジュアライズしたものが以下です。

seed=0 では、$M$=$2$なのでポリオミノの形のまま占いを繰り返し、それだけで油田の配置特定に成功しています。コストは 16 程度かかっていますが、ベイズ推定をうまく使うとたった 2 回の占いで コスト 1 未満で正解を出せるようです。なにごと？

seed=1 では、$M$$\neq$$2$なので 3x3 の矩形で島全体を走査しながら占ってから、油田が埋まってそうなマスをなるべく距離を離してまんべんなく探しています。ある程度油田が見つかったら、既に見つかった油田マスの隣接マスを重点的に掘り、油田と油田以外の境界線を見つけられるようにしました。最悪全油田マスを掘り尽くしたら、それらのマスを回答するようにしています。

日記

取り留めのない書き散らしです。

2024/02/12

• 占いのコストが小さいからなるべく掘らずにいっぱい占い使いたい。

  • ポリオミノの形そのままとか 3x3 等の矩形でスライドして占い大まかな分布を掴むか。

  • いかに回数減らすか。

    • 明らかにスコア高い地点があったらそこで打ち切る？

  • ポリオミノの形そのまま占いは 2~3 個目の油田からは事前計算した推定 v(S)マップでいい感じのとこを占う。

    • 事前に 3x3 占い走査しておく？
  • 周囲マス全てを占うのではなく、何らか間引く
  • 占い結果の v(S)をグリッドマップ に 均等割で足すのは違和感。これまでの占いで求めた値とで重み付けできないか？

2024/02/13

• 【済】ポリオミノ走査した時は 3x3 走査しない
• まず 3x3 で 2 回位置をずらしながら走査して大まかな油田分布を把握(10 ～ 20 コスト)

• 以下をループ

  • 【済】試し掘りをなるべく場所をばらけさせつつ実施

  • 【済】BFS の後に位置推定しては？

    • 微妙

  • 今確定している情報と矛盾せずに最もそれっぽくポリオミノを置ける配置の組み合わせを回答

    • 0→ ポリオミノを置いてはいけない
    • 1 以上 → 最も相応しい組み合わせを配置(置かない選択肢はない)
  • ある時点でこのポリオミノはここに確定、と決めつけず新たに得られた情報を基に毎回新たに考え直すのがいいと思われる

  • 山登り or 焼きなましで、各ポリオミノのベスト配置上位 5 個程度(推定 v(S)の下限あってもいいかも)を用意して、1 個選んで動かすのを繰返す

    • 局所最適にハマりそう。焼きなましが良さそう。
    • 移動させたポリオミノがその場所固定とした時の他の最適配置を計算してスコア計算
    • 組合せ数が少ないなら全探索で良い。

    • oil$\_$map と oil$\_$forecast$\_$map の乖離が気になる

      • oil$\_$map は矛盾検知だけに使う？

• 絶対スコアはそこまで良くなっていないのに順位が一度 200 位以内になった。

  • みんな M が小さいケースは強いが M が大きいケースは弱いとかあるかも？

2024/02/14

• 占い結果と試し掘り結果を基に、推定 v(S)が高く試し掘りの結果とも矛盾しない配置を乱択で探そうとした。

  • うまくいかなかった。考えられる理由は以下。

    • 占い範囲を狭くするとターンが足りない
    • 占い範囲を広くするとポリオミノが重なっているところに優先的に置こうとしてしまう

2024/02/15

• 確定している 0 のマスの情報を基に、各ポリオミノを走査した時にある 1 つのポリオミノを配置することでしか確定している 1 のマスを埋められないような状況が判定できるのでは？

  • self.possible$\_$poly$\_$map でありうる油田の左上マスの位置を管理
  • occupied から消せるのは、v(yx)>0 で definitive_PoS に存在しない id のみ
  • update_definitive のタイミングでは確定済みマス見ない。確定したタイミングで…(日記はここで終わっている)

2024/02/16

• 確定したポリオミノと確定していないポリオミノの候補いくつかで DFS をしていい解を出力

  • 【済】同じ回答は防ぐ仕組みが必要

    • 回答用座標リストをソートしてタプルにする

• 未確定だけどほぼ確定(ポリオミノのマスの 8 割以上で v(y,x)>0)なら確定扱いにする

  • 試したけどスコアが上がらなかった

• DFS のループ回数を増やしたらスコアが上がりそう

  • Rust に書き換えれば単純にスコア伸ばせそう

• 試し掘りの場所決定をもう少しいい感じに出来ないか

  • 一定ターン過ぎたあとは既に見つかっている v(y,x)>0 の周囲を掘るようにした
  • trial_dig でひとマス掘るたびに v(y,x)>0 なら隣接マスも掘ってはどうか

2024/02/17

• ChatGPT に助けを請いつつ必死に Rust に翻訳しようとする

  • 心が折れる
  • C++への移植を頑張る

2024/02/18

• C++への移植が完了するがスコアが伸びない

  • 結局 DFS を TLE まで while ループ中で繰り返すことになるため、DFS の通り数限界を 10**7 にしたところで何度も繰り返すと TLE 対策の全掘りルートに入ってしまうのが原因と思われる。
• 細々とした改善(あまり掘れていない最初のうちは、周囲が全部未発掘マスの場所を優先して掘るとか)

2024/02/19

• 祈りを捧げる
• 真心を込めたパラメータ調整

まとめ

今回のコンテストは過去に良い順位を取れたAHC003やRECRUIT 日本橋ハーフマラソン 2023 冬（AtCoder Heuristic Contest 018）のようなグリッド上の推定系の問題に見えて好きそうだなというのが第一印象でした。あと問題文が短めだったのも嬉しかったです。

余談ですが、本コンテスト開催元の THIRD 社さんには僕がファンをやらせていただいているbowwowforeachさんが在籍されていることもあり気合十分だったので、うまく入青できてとても嬉しいです。

最後に、今回は活かしきれませんでしたが C++は Rust よりは楽に書けそうなので、今後のヒューリスティックコンテストは C++で出るのもありかもなーと思いました。

以上です。