AHC 030 - Kiri8128の日記

AHC 030 参加記

AHC 030 おつでした。

プレテスト 7,885 M で暫定 55 位です。

（追記）システスは 528 B で 51 位でした。

最終提出

提出コード

$M$ が小さい場合は可能なすべての状態（各油田の左上の座標の組）を持って、期待獲得情報量がなるべく大きくなるクエリを投げるのを繰り返す（☆）
が大きくなるにつれて
- 行・列ごとに☆を行い、状態数がある程度減ったらマージして再度☆を行う
- 行 $\bmod 5$ と行 $\bmod 4$ から行を復元する
- 左 $3$ 列などだけを見て $2$ ～ $3$ 個の油田の位置を確定してから上のことを行う
- それも無理そうなら $4$ セルごとに組にして、それぞれをベイズ推定する
- それも無理そうなら $1$ セルごとに聞く

情報量の計算

一般論

事前分布 $P(X)$ に従う統計量 $X$ を観測することで事後分布 $Q(X)$ を得た場合に得られる情報量は

$-\displaystyle\sum_{x}Q(x)\log \frac{P(x)}{Q(x)}$

あるいは連続の場合は確率密度関数 $p(x)$ および $q(x)$ を用いて

$-\displaystyle\int_{x}q(x)\log \frac{p(x)}{q(x)}dx$

と表せる *1 。

情報量最大化への帰着

問題の言い換え

問題は「油田埋蔵量が正のマスをすべて特定すること」だが、これを「すべての油田の位置を特定すること」と言い換えたい。

実はこれは $M$ が小さければほぼ正しい。つまり油田の配置は油田埋蔵量が正のマスとほぼ一対一に対応する。 $M$ が大きい場合は単射にならないことが多いが、 $M$ が大きい場合は大変なので（後述するつもり）、この言い換えをする。

情報量のオーダー

油田の配置は、初期情報だけからだと $\displaystyle\prod_{i=1}^{M}(N-h_i+1)(N-w_i+1)$ 通りある。これを一意に特定するにはこの対数に相当する情報量 $\displaystyle\sum_{i=1}^{M}\log(N-h_i+1)(N-w_i+1)$ を得る必要がある *2 。

状態数は $N^{2M}$ で抑えられるので、 $0$ か $1$ かを全部持つ状態数 $2^{N^2}$ よりかなり小さくなっている。

コスト当たり約 $x$ の情報量が得られるとすると、 $\displaystyle\frac{2M\log N}{x}$ で正解に辿り着くことができるという計算になる。

貪欲法

いろいろ不確実性が高いので、「各ターン、（得られる情報量の期待値）÷（コスト）を最大にするムーブを繰り返す」という貪欲法でも十分強そうということが分かる。

正規分布で近似

（この項は結局使わないので読み飛ばしても OK）

仮定

$X$ の事前分布が正規分布 $X \sim \mathcal{N}(\mu, \sigma^2)$
観測により、実際の値に誤差 $e \sim \mathcal{N}(0, \sigma_{e}^{2})$ を加えた値が得られる

観測値の分布

このとき観測値 $Y$ の分布は $Y \sim \mathcal{N}(\mu, \sigma^2 + \sigma_{e}^{2})$

事後分布

また観測値が $Y=y$ であれば事後分布は正規分布 $\mathcal{N}(\mu_{\mathrm{post}}, {\sigma_{\mathrm{post}}}^2)$ に従う

ここで

$\mu_{\mathrm{post}}=\displaystyle\frac{\frac{\mu}{\sigma^2}+\frac{y}{{\sigma_{e}}^{2}}}{\frac{1}{\sigma^2}+\frac{1}{{\sigma_{e}}^{2}}}$

${\sigma_{\mathrm{post}}^2}=\displaystyle\frac{1}{\frac{1}{\sigma^2}+\frac{1}{{\sigma_{e}}^{2}}}$

得られる情報量

これを上の一般の場合の式に代入して、簡単のために $t=\displaystyle\frac{{\sigma_e}^2}{\sigma^2}$ とすると、得られる情報量は

$-\displaystyle\frac{1}{2}\log (1+\frac{1}{t})+\frac{1}{2t}+\frac{y^2}{2t(1+t)\sigma ^2}$

得られる情報量の期待値

これを $y$ について期待値を取ると得られる情報量の期待値が次だと分かる。

$-\displaystyle\frac{1}{2}\log (1+\frac{1}{t})+\frac{1}{t}$

何マス選べば良いか

kマス選んだときの平均・分散

適当に近似すると $k$ マスを無作為に選んで占ったときに得られる情報量の期待値が分かるのでそれを最大化すれば・・・

あたりまで考えたときに、少し実験してみると $\epsilon$ が小さいと情報量が増えすぎちゃうことに気付いた（例えば $0$ か $1$ しかとらない場合、情報量は最大でも $1$ だけど正規分布で近似すると $5$ とかが得られてしまうなど）。

離散

なので事前分布も誤差関数も離散でやった方が良さそう。

誤差と遷移確率

$k, \epsilon$ を固定して考える。

あるサイズ $k$ のマスの集合について、油田数の合計の分布は、それまでに聞いたクエリから理論上厳密に計算できる。

よってこの場合もその集合についてクエリを投げたときに得られる情報量の期待値が（計算量を気にしなければ）厳密に求まる。

可能なすべてのクエリに対してコスト当たり期待獲得情報量を計算するのが良いが、時間的に難しいのでいくつか候補を選んでコスト当たり期待獲得情報量が最大のものを選ぶこととしたい。

計算方法（離散の場合）

事前分布が $P(x)$ および事後分布が $Q(x)$ が分かると、得られる情報量は上述のとおり次のように表される。

$-\displaystyle\sum_{x}Q(x)\log \frac{P(x)}{Q(x)}$

あるマスの集合について質問するという観測について、観測を行う前の段階でどれぐらいの情報量を得られるか計算するには、次のように考える必要がある。

各観測結果について、その観測結果が得られた場合の情報量を計算する
それらを事前分布の重みで加重平均する

1. については、観測結果から事後分布を計算する必要があるが、これはベイズで計算できる。ちゃんとやるとでかいテーブルが必要になって結構大変だが、 $\epsilon$ はケースごとに固定なので、 $k$ （クエリに投げるセルの個数）ごとにテーブルを前計算しておけばなんとかなる。 Python だとそれでも結構つらいので、なるべく同じ $k$ でクエリを投げるようにした。

実装方法

方針

すべての状態について、クエリ結果をもとに確率分布を管理する。
トップの状態が $2$ 番目にある程度差を付けたら Answer クエリを投げる

データの持ち方

通りの状態をすべて管理する。
- 初期状態では事前分布は互いに等確率なので、すべて同じ重みとする
クエリを行うごとに、結果に対して整合的になる確率を掛ける
- 実装上は対数確率を加算する
- 管理する量が膨大になるのを防ぐため、十分小さい確率になったら管理対象から外す

どのクエリを選ぶか

なるべく結果の分散が大きくなるようなクエリを聞くのが良い
マス同士の共分散が高い（≒近くにある）マス同士を一緒に選ぶのが効率的であることが多い
ただし一度クエリを投げると、次回からはそのクエリの結果は既知となるので、同じ（あるいは似ている）クエリをたくさん投げても得られる情報量の期待値は少なくなりがち

計算量削減の工夫

独立空間への分解

$O(N^{2M})$ 個の状態を管理・更新するのは、 Python では $M=2$ かせいぜい $M=3$ ぐらいしか対応できない *3 。

行だけ見て、すべての油田の行の位置を決定する

→列だけ見て、すべての油田の列の位置を決定する

みたいな方針だと管理する状態数を $O(N^{M})$ まで減らせるので $M=4$ ぐらいまで対応できる。

「行だけ見る」というのは、 $(i, j)$ を $i$ に移す関数 $f((i, j)=i$ により「圧縮」操作をしたと考えることができる。

これでうまくいくのは、「行だけ見る」が加群の商群になっていることが効いている。

より一般化すると加群 $f:\mathbb Z ^{2}$ の部分加群 $X$ を固定すると、その商群で考えることができる。

一部のマスだけで判定する

例えば左 $3$ 列だけを見て、ここにかぶっている油田が $3$ 個以下であると仮定すると、調べるパターンは ${}_{M}C_{3} \times (3N)^{3}$ になる。さらに行をまとめたり列 $\bmod 5$ などを考えることで探索パターンを減らし現実的な計算量で順次特定していくことができる。

私の実装では、これを一度行って $2$ ～ $3$ この油田の位置を固定して、上の独立空間に分解する方法になった。

その他やったこと・考えたこと

今回はローカルで実行せず、すべてコードテストでデバッグした
- 提出コードと同じコードでコードテストデバッグできるようにした
- せっかくビジュアライザ練習してたので使えば良かった
- 途中まで導入してないと心理的に途中から作るのがめんどくなってしまって良くない
- コードテストで困ったこと
  - クエリ回数が多いと、クエリ部分だけに絞っても全部出力できないのでデバッグできない
序盤は $M=2$ 以外は打ち切るとかでやっていて、後半に徐々に $M$ を増やしていこうと思っていたが増えきらなかった
Web 版ビジュアライザの罠：
- との上限・下限が設定されている雰囲気があるが、あり得ないパターンが含まれている
  - $N=10$ かつ $M=20$ とかを表示して、特定むずそうだなーとか言ってたけど存在しないケースだった

できなかったこと

全部の状態を持たなくても、クエリの結果に矛盾しない配置を焼きなましとかギブスサンプリングとかで得るのでも当てられるか
- 焼きなましは、全部当てないと使いづらそうだし、自分の実力だとだめそうなので棄却
- ギブスサンプリングだと、最初例えばランダムに 10000 状態持っておいて、クエリごとに尤度を更新して、ある閾値を下回ったらダメな部分を付け替えるみたいなイメージを考えていた（けどこれも自分の実力だと無理そうなので棄却）
「一部のマスだけで判定」を逐次的に実行することでが大きい場合も計算量を爆発させずに探索ができるはず
- 実装しきれなかった。
- PyPy では 1 回やるだけで $1$ 秒程度かかってしまうので、高速化しないとむり

今後やりたいこと

焼きなまし（無限回言ってる）
Rust に乗り換える（無限回言ってる）
- 今回ちょっとだけ chat GPT くんに翻訳してもらおうとしたけど無理だった

（追記） $M$ ごとのシステス順位

$6$ 以上ほぼ $1000$ 位付近ですね・・・

（これで全体 $51$ 位取れてるので力の入れどころは合っていたということで・・・）

$M$	$\mathrm{Rank}$	$\mathrm{Score}$	$\mathrm{Case}$	$\mathrm{Average}$
2	36	146,610,872,823	369	397,319,438
3	27	144,668,767,503	354	408,668,834
4	22	137,882,178,018	358	385,145,748
5	348	23,766,708,507	398	59,715,348
6	1002	7,026,140,456	288	24,396,321
7	703	7,877,432,650	241	32,686,442
8	998	5,235,875,353	190	27,557,238
9	975	6,288,036,010	156	40,307,923
10	981	4,758,143,130	109	43,652,689
11	672	7,383,989,361	140	52,742,781
12	972	5,054,494,368	84	60,172,552
13	979	4,430,272,358	71	62,398,202
14	968	4,682,556,825	60	78,042,613
15	659	5,073,713,315	51	99,484,574
16	955	4,973,223,557	43	115,656,361
17	970	3,373,058,320	28	120,466,368
18	972	6,253,621,561	36	173,711,710
19	952	1,569,309,822	12	130,775,818
20	979	1,215,604,211	12	101,300,350