Skip to content

THIRDプログラミングコンテスト2023(AHC030)

問題概要

  • N * Nマスのグリッドがあり、M個の油田が隠れている
  • 各油田はポリオミノ型の形状をしており、各油田の形はわかっているが、どの位置にあるかは最初はわからない
  • 以下の3種類の操作を最大で2*N^2回まで繰り返して、できるだけ少ないコストで油田のあるマスをすべて特定せよ
    • 1マスを選んで掘る。そのマスの埋蔵量がコスト1でわかる
    • kマス(2マス以上)の集合Sを選び占うことで、そのマスの合計埋蔵量にノイズがのった値がコスト1/sqrt(k)でわかる
      • 値は、kとεと合計埋蔵量から決まる平均と分散の正規分布からサンプリングされた値をxとしてmax(0,round(x))がわかる
    • 油田があるマスをすべて推測する。もし正解ならそこで終了し、不正解であればコスト1を払って継続する

時間

  • 240 時間

個人的メモ

油田の数M

アプローチ

  • ざっくりと、操作を繰り返すたびに情報が増えていって、それによって盤面を特定していく感じ
    • 各操作では、できるかぎり情報を得ることを目指すことで、操作回数やコストを減らす
  • ただ、「占い」ベースの方は、各処理が重かったりして(性能をできるだけ落とさない)高速化や処理時間のバランス調整を実現できる必要があるっぽい

「1マス掘り」ベース

  • 「1マス掘り」は、コストが1で大きいが、正確な値が得られる
    • εが大きかったり、Mが大きいケースではこちらが有利だった模様
  • そこで、できるだけ掘る回数を減らして盤面を特定することを考える
  • ムダな採掘を減らす
    • サンプルコードは、「全マスを掘って埋蔵量が1以上だったマスを答える」というものになっている
    • 油田の形がわかっているので、それまで掘った油田の埋蔵量の合計からすべての油田を見つけ方がわかるのでそこで終了できる
    • 油田の形から、端っこなどで必ず0になるマスは調べなくて良い
  • BFSで探す
    • あるマスで埋蔵量が1以上である場合、油田の形は連結なので、そこから隣接マスに対して埋蔵量が1以上のマスをBFSで探すと、ムダな0のマスをできるだけ探さなくて済む
  • 候補を絞っていく
    • 各油田について、ありえる左上の位置の候補を全部列挙しておく
    • あるマスの埋蔵量がわかった場合、そこから、候補のうちありえないものが除外できる
      • どのマスを掘るかは、候補ができるだけ減らせそうなマスを選ぶようにする
      • また、ある程度まで候補が減ったら残りは全探索とかもできる
  • しかし、これだけだとコストが結構かかってしまうため、上位は難しかった模様

「占い」ベース

  • 「占い」は、コストが1/sqrt(k)で済むが、不正確な値しか得られない
  • 得られた情報の使い方
    • 盤面(油田の位置)の候補xの集合を考え、それぞれの候補の確率P(x)を考えると、ベイズ推定により、占いの合計埋蔵量の情報yを得て、確率を更新できる
  • 占うマスの集合の選び方
    • 選ぶマスの集合はいろいろ考えられるが、強かったのは、上記の候補の確率のエントロピーを考えて、コストとエントロピーの減少量(相互情報量)が多くなるように選ぶことで効率的に情報を得る方法だった模様

盤面候補のベイズ推定

ある盤面xで占いの結果がrとなる尤度

  • ある盤面の候補xで、あるマスの集合Sの占いをして値rが得られた場合の尤度P(r|x)を考える
  • これは、問題文から、正規分布で与えられることがわかっており、round(x)していることからr-0.5〜r+0.5の範囲の確率であることがわかるので、正規分布の累積分布関数からその範囲の確率値が求められる
    • 厳密にはmax(0,round(x))なので、x=0は0.5以下の範囲
  • マスの集合が複数与えられた場合は、それらが同時に与えられる場合として、\prod P(r_i|x)を考えれば良い
    • そのままだと値が小さくなりすぎるので、対数を取った対数尤度で考えるとよい

各盤面での確率値

  • ベイズの定理から、P(x|r) = P(r|x)P(x)/P(r) \propto P(r|x)P(x)と書ける
    • 各油田の位置は一様ランダムに決まるのでP(x)は「1/候補数」としてよい
  • 上記の式から、すべてのxについて求めてから正規化したP(x|r) = P(r|x) / \sum_{x_i}{P(r|x_i)}で求められる

選ぶマスの集合の選び方

尤度が高い2つの盤面を区別できるところを選ぶ

  • 候補盤面の中で尤度が1番高いのと2番目に高い盤面を区別することを考える

エントロピーの減少量(相互情報量が最大)になるところを選ぶ

エントロピー
  • やりたいことは、各盤面での確率値P(x|r)について、正解の盤面xを特定(=その盤面だけ確率が高い状態)すること
  • P(x|r)の確率分布で、あるxに特定できている、まったく特定できていないなどを評価するものとして「(情報理論における)エントロピー」が使える
  • H(X) = -\sum_{x}{P(x)logP(x)}
    • エントロピーは、あるxに特定できている場合は最小、全く特定できていないは最大になる
    • logの底は2(bit)が一般に使われるが、なんでも良い
  • これを使って、マスの情報を得た後で、できるだけエントロピーが減るように、マスの集合を考えることができる
エントロピーの減少量
  • マスの情報を得た後の確率はP(x|r)で、その時のエントロピーはH(X|r) = -\sum_{x}{P(x|r)logP(x|r)}
  • ここで、エントロピーの減少量(差分)を\Delta_r = H(X) - H(X|r)として、値rについての期待値を考えると、\sum_{r}{P(r) * \Delta_r}となる
    • この値が大きくなるようなマスの集合を見つけて投げれば良い
  • この式は、「相互情報量」と呼ばれる値で、こちらでも考えることができる
    • I(X;Y)=H(X)-H(X|Y)
    • I(X;Y)=\sum_{x}\sum_{y}{P(x,y)log\frac{P(x,y)}{P(x)P(y)}}
    • 今回の場合、P(x,y)=P(y|x)P(x)からI(X;Y)=\sum_{x}\sum_{y}{P(y|x) P(x) log\frac{P(y|x)}{P(y)}}にしてから使う
相互情報量最大のマス集合
  • 「相互情報量/コスト」を目的関数として、マスの追加削除などを近傍とした山登りで求める
  • 高速化
    • ただ、まともに計算しようとすると、「候補盤面*占った結果のあり得る値」回すことになるので、かなり重い
    • 以下のような高速化や調整をいれてないと厳しいっぽい
      • 候補盤面は、確率が低い盤面を削除して減らす
      • ある程度小さい確率の部分は無視する
      • できるだけ重い関数を何度も呼ばない
      • 配列などの確保や初期化を何度もしない(差分計算する、逆操作で戻す)
      • 前計算しておく(log計算)
      • パラメータ調整、時間調整

候補が多すぎる問題への対処(M>2への対処)

  • M=2は全列挙ができる
    • M=3でもテストケースによっては可能かも？
  • しかし、M>2の場合、盤面の候補数が多くなりすぎてしまう
  • そこで、確率が高そうな候補を何件かまで保持してそれ以外は無視する(または、サンプリングする)
  • 候補に正解が含まれないと正解できないので、候補に正解が入るように調整するのが大切
    • ローカルでは答えも与えられるので、その情報を使ってパラメータ調整や手法を検討

候補が列挙できる程度になるまで減らす

  • 1マス掘りする
    • 1マス掘りは確定情報なので、確実に候補を減らせる
    • しかし、コストが大きい
  • 適当に占って尤度が高い上位n件を使う
    • 問題ページにある例のように、5x5とかの区間に分けて各区間の占い情報を下に尤度が高い候補上位n件だけを使う
    • 候補から正解が漏れる可能性があるので、その場合は失敗する(確率的に成功する)

乱択山登りで候補生成

  • (矛盾を許容した)ランダム配置からスタートして、できるだけ矛盾がなくなるように部分破壊再構築近傍で山登り

焼きなましによる候補生成

  • 各油田の位置をずらしたり入れ替えたりする近傍で焼き鈍すと、その途中の状態が候補になり得る
  • 尤度が高い盤面候補を求めることで、可能性が高い候補だけ用意できる
    • 今回の場合、確率が高い状態はだいたい似たような盤面(自己相関が高い？)になるので、その周辺だけ調べれば十分な感じっぽい
  • 「油田の位置をずらす(隣接にずらす、ランダム位置にずらす)」近傍以外に、油田の区別がしにくいこともあるため、「油田同士のswap」近傍もいれるとよいみたい

MCMCでサンプリング

  • ギブスサンプリング/MH法

占いマスの形状について

パラメータ調整

  • 1ターンあたりの計算時間
    • 何ターンかかるかを入力パラメータから見積もって、おおよその時間を調整
  • 1ターン内の、各処理にかける時間のバランス
  • 何個候補盤面を持つか
  • 盤面の確率がどの程度になったら解答するか

コスト0の話(clar)

悪いテク

その他

占いで得られる値の分布

類問

ビジュアライズ

解説

(50位まで&発言を見つけられた方のみ)