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

こんにちは。競技プログラミングをしているssaattooと申します。THIRD プログラミングコンテスト2023（AtCoder Heuristic Contest 030）に参加して 35位でした。

反省、または誰かの為になることを期待して参加記録を残します。

seed=1の様子

問題概要

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

グリッド上にポリオミノが重なりを許して配置されている。その位置を推定してほしい。

解法

大まかな解法は以下の通りです。

M=2のときは、全ての配置が高々 N^{2M}なので全ての配置を保持して占いの結果をもとにベイズ的に確率を更新しました。

M=3のときは、全ての配置について事前の占い結果をもとに尤度を計算して、その上位10000個だけでM=2と同じように解きました。8割くらいは上位10000個に正解が含まれていました。

M>3のときは、

  1. 最初に盤面を格子状に区切って占う
  2. 各ターン占いと採掘結果をもとに油田の配置を焼きなましによって推定する
  3. 焼きなまし結果をもとに占いまたは採掘をおこなう
  4. 適宜回答クエリを投げる

これで暫定テストで22%程度（34位）の点を得られます。

初期占いパート

N, Mによって辺の長さが3から7までの長方形を詰めるように盤面全体を占いました。

焼きなましパート

過去の占いと採掘の結果をもとに、ありそうな油田の配置を焼きなましで探索しました。

近傍は1個以上の油田をランダムな位置に変更させるものでした。評価値は過去の占いと採掘の結果から、その油田の配置の対数尤度を求めてそれを最小化しました。

近傍の設計が悪かったらしく、かなりの高温でもvalidな配置が一つも見つからないことも良くありました。このvalidな配置というものは、尤度が小さすぎずこれまでの回答クエリと一致しないものを指します。

占い・採掘パート

焼きなましでvalidな解が見つかったときは、尤度の大きい２つの差集合をとり、その大きい方を占いました。

焼きなましでvalidな解が見つからなかったときは、以下の優先度が高く中央に近いものを1点堀りしました。

  1. 周囲が全て1以上だと予測されていて、かつ自分が0
  2. 周囲3マスが0だと予測されていて、かつ自分が1
  3. 周囲3マスが1以上だと予測されていて、かつ自分が0
  4. 周囲2マスが0だと予測されていて、かつ自分が1

日記

メモなので汚いです。

目標
  • 2500パフォ
  • 乱択要素を入れる前に貪欲を考える
  • 実装やツールを最初の方は整備する
コンテスト１日目
  • 問題を読んだ。推定系で諦めムード
  • 平均と分散のところがぱっと見ではよくわからない。式をちゃんと理解するべき
  • ジャッジ部分をきちんと実装しよう
  • 盤面サイズとブロック数がかなり小さいのは、しっかり推定しなさいってことかな
  • ミスするとほぼ0点になるので、コストを減らしつつ100%確定という状態までするのだろうか。それともコストを減らして賭けに出る方がいいのか？
  • 方針案
    • ベイズ
    • 尤度を最大化するように焼く
    • 各クエリで確からしさの改善量が最大になるように選ぶのではなく、クエリ全体で確からしさを最大化させたいことに注意
    • ガウス過程？
コンテスト２日目
  • 平均と分散の式がわからない。
  • すでに高い確度で分かっているマスはsurveyに含むべきなのかどうか
  • とりあえずsurvey無しでブロックの位置が確定するまで掘り続けてみる
  • サンプルコードとの相対スコアがわかるので提出する必要は薄そう
  • 0以上のマスを見つけたらbfsで周囲探索
  • 現在の1位はコスト \frac{N^2}{4} ほど。最終は \frac{N^2}{12}くらいかな
  • あるブロック配置のときの尤度を求めるものを作る
  • 推定がミスったときはわざとWAにしたほうがわかりやすい
  • 掘ったやつに一致させる配置は乱択dfsでいけそう？
コンテスト3日目
  • 当然だけど、隣接マスの v_{i,j}は近い
  • 観測結果から尤度を最大化させる配置を焼きなましで求めているけど、貪欲ではできないか？
  • 0以上のマスを見つけたらbfsで周囲探索
    • サンプルの倍くらいで129位
  • 大まかに推定してから、鍵となる点を掘りたい
    • 3×３を1個飛ばしで推定してもコストは \frac{1}{10}くらいでそれなりの精度で予測できている
    • 外側に張り出している角は重要そう
    • または０予測したマスでへこんでいるところ
  • ↑のを実装して提出。ローカルではサンプルの0.3倍で16.7で30位
    • 3×３を1個飛ばしで大まかに推定
    • 何回かに1回焼いて、1マス探索を優先度に従って行う
        1. 周囲が全て1以上だと予測されていて、かつ自分が0
        1. 周囲3マスが0だと予測されていて、かつ自分が1
        1. 周囲3マスが1以上だと予測されていて、かつ自分が0
        1. 周囲2マスが0だと予測されていて、かつ自分が1
        1. 自分が1以上の内ランダム
      • 同じものがあれば、中央に近いものを優先
  • 焼きなましの近傍を1個移動から2個移動にしたら4%ほど改善した
コンテスト4日目
  • 貪欲。各ブロックについてこれまでに掘ったやつに矛盾しない位置を列挙。まだ掘っていないマスの内、一番重なりが多いマスを掘る。
    • これで0.3
  • mm147は役に立つかな？
  • eps=0.01の場合を考える
  • 3×３のマスを測定したとき、その中心の値を推定できないか
  • 各マスについて０である確率を持っておいて、サンプリングするごとに更新する？
  • 複数まとめて測定するとき、はなれたものだと情報がすくなくなる？3×3とかだといいのか?
  • 理想では各 (pos_0, pos_1, ..., pos_{m-1})について確率をもっていて、ansクエリではそれが最大の組を出力したい
  • 3×３より十字のがいいか？
  • 掘るやつ同士ははなれているほうがいい？
  • 1点掘りパートになったら、モンテカルロで一番いいところをほればいいか？
    • まず評価値によるいい感じの貪欲をしたい。
    • モンテカルロだと毎回焼けないので焼きなしで可能な評価がいい
コンテスト5日目
  • 時間無視でモンテカルロを試す
    • 重すぎるし改善しない
  • 各ブロックの存在確率を持ちたいけど、独立じゃないから無理そうって考えてたけど、AHC022では縦方向の正規化ってやつが有効だったそうだけど、これには使える？
  • おおまかにブロックの位置がわかっているとき、1点堀りでは０が判明する方がうれしい？
  • まんべんなく掘ったほうがいい
  • 答えがかぶっているときは、別のを出力
  • スコアが低いのが必ずしも解とは限らないので、温度は高めに
コンテスト6日目
  • 次掘るのに最も良い手は、あり得る解候補を列挙してその候補数を減らせる手
  • 1番と2番の違うところ？
    • １１．６９で37位
    • 差集合のどっちかをsurveyすればいい？
  • 現状スクリーンショット (66).png)
    • epsはほぼ関係ない
    • mが大きい奴をどうするかが大事
    • mが小さいやつはほぼ意味なさそう
  • 推定盤面を複数生成。解が一意になるような1点堀りするマスの集合をマスの個数を最小化するように焼く。一致しているところが多いものを掘る？
    • 点の個数と配置の総積の和を評価値にする
  • ０と１が隣り合っているところを発見すると嬉しそうなので、０と１をみつけたらその間を二分探索？→微妙
コンテスト7日目
  • 時間を10倍にしたら1割くらい伸びる
  • 4倍の点を取るにはどうすればいいか考える
    • 1点堀リの数を4分の1にできるのか
    • surveyを活用するのか
    • ｍごとに提出してそれぞれ何割取れているか確認する
      • 2\le m\le5 、19ケース2.23(11.7%)
        • 3.57(18.7%)
      • 6\le m\le10 、21ケース3.60(17.1%)
      • 11\le m\le15 、7ケース1.34(19.1%)
      • 16\le m\le20 、3ケース0.87(29.0%)
  • １つのブロックでできている島は、4方向から固定してやれば位置がきまる？
  • mcmcっぽくサンプリング？
  • 1点掘るなら、０か1以上かが最もあいまいな場所を掘りたい
  • ある点を掘った後にかかるスコアの期待値を求められたら
  • 推定盤面に対して、スコアが10倍になるだけの数の点を焼きなましにより配置し、その中で一番評価が高いものを掘る
    • この焼きなましは、各ブロックは０と接してるなら4方向に０があると高評価。各ブロック最低1個は1以上の点が欲しい。
    • 点の個数も最小化
コンテスト8日目
  • 線形補完？
  • 推定盤面が焼きなましでx番目にscoreが小さいとき、(x-1)番目までの各盤面と推定盤面と違うところに少なくとも1つ点を置くときの最小個数を評価値とすることができる？
  • (x+y)%2=0しか置かない
  • サンプル
    • 2\le m\le5 、19ケース0.15(0.8%)
      • \frac{N^2}{100}を目指す
    • 6\le m\le10 、21ケース1.02(4.8%)
      • \frac{N^2}{15}を目指す
    • 11\le m\le15 、7ケース0.53(7.6%)
      • \frac{N^2}{10}を目指す
    • 16\le m\le20 、3ケース0.５２(17.4%)
      • \frac{N^2}{5}を目指す
  • 予測配置で面積の小さいものから
  • 差集合の内、最も大きな連結成分をsurvey?
  • 推定盤面で各ブロックの中、上、下、左、右に点がなかったらおく
コンテスト9日目
  • 焼きなましでvalidな解に移動できていない
    • いくつかブロックを取り除いて、矛盾しない位置に移動
  • 9.81で25位
    • 最終的に1.5倍くらいまではのばしたい
  • eps=0.01は半分くらいにできるはず
    コンテスト10日目
  • M=2は全探索できるはずなのでする
    • 考えること
      • 各配置の確率を決定したときに、ansクエリをするべきかどうかの判断
      • surveyするとき、どこをするべきか
    • 4倍くらいに伸びた
      • m=2をこれにしただけで、1.8くらい伸びた
      • M=3,4も最初の焼きなましで間引けばいけるのではないか？
コンテスト11日目
  • 微改善しただけ

終わりに

良かった点
  • copilotを使いはじめて実装速度が上がった
悪かった点
  • コードが汚くなりすぎた
  • 勝てないのに潔く諦めなかった
Todo
  • ファイルの分割
  • 統計、機械学習の知識をつける
感想

見た瞬間に苦手そうだと思ったけど、実際に苦手で最後まで問題の理解が進まなかった。統計の知識が足りなさを痛感した。

M=2のような単純なものから考えていくと考察が良く進んだ。最初から特定のパラメータに限定して考えるというのも悪くないかもしれないと学んだ。