https://kiri8128.hatenablog.com/entry/2025/04/07/220212

AHC045 の参加記事です。

41.377B でプレテスト 47 位でした。

上位勢とは割と異なるところもあるので筋が良いかはあやしいですが、シンプルな実装でそれなりのスコアが出るのでご参考まで。

やったこと

推定とグループ構築の2段階に分けてそれぞれを解く
推定パート
- 状態の持ち方
  - 各頂点について、初期状態以外は2次元正規分布で近似する
  - 点間の相関は考慮しない
- クエリの選び方
  - 正三角形を繋げるようなクエリを投げる
  - クエリ前に最も最長方向の分散が大きい点は必ず選ぶ
  - 2点目を決めた後は、隣接点を2頂点とする正三角形のもう一つの頂点付近から頂点を選ぶ
  - たくさん試し、点ごとに得られる期待情報量の重み付き和が最大になるものを選択する
  - 重みは最長方向の標準偏差
  - ただし L が6以下の場合は実際にシミュレーションを行い分散（の平方根）の減少量が最大になるものを選択した
- 更新
  - クエリの結果はシミュレーションで反映
  - 事前分布からサンプリングを行う
  - 各頂点について隣接頂点（最小全域木の辺でつながれた頂点）の集合がクエリ結果と一致するものを採用する
- クエリをすべて消費した後、もう一度同じクエリを最初から投げたと想定して再度更新を行う
グループ構築
- 推定した座標に基づいて「『グループ内の2点間の距離の二乗和÷グループの要素数』の合計を最小化する」という問題に言い換え、これを焼きなまし法で最小化する
- 言い換え問題は、スワップの差分計算が O(1) でできる！
- 言い換え問題の結果をそのまま使い、できたグループごとに推定座標に基づく MST で結び方を決める
- なお、後処理で最小全域木の長さを実際に計算する焼きなまし（山登り）も試したが特に良くならなかったのでやめた

考察いろいろ

どんなクエリが良いか

長さが近い辺はどちらが長いか不明であり、長さが明らかに異なる辺は逆転が起きないと仮定する。実際、事前分布の分散をもとに、近すぎる頂点は選ばないようにしている。そうすると、クエリの検出力は、クエリの応答として現れる結果の種類数とみなせる *1 。

選ぶ点の個数ごとに、どういうクエリの検出力が高いかを見ていこう。

結果としては、正三角形をたくさん連ねる形の効率が良さそうということが分かる。

なお分散が等しい場合、小さい正三角形でも大きい正三角形でも得られる情報量は変わらない。ただし標準偏差に比べ近すぎると位置の逆転が発生し良い情報が得られないので、ある程度以上離す方が良い。

クエリによる分布更新のイメージ

サンプリングと更新は以下のようなイメージ。黒の円が事前分布。下の2点を結ぶ辺が最も近い（MST に使われなかった）ことが分かった場合、1000回サンプリングして条件を満たす点が赤い点たち。そこから推定される2次元正規分布の2σ領域が赤楕円になる。

Lが小さい場合

青の楕円はクエリ前の推定域を2σ水準で表示しています。つまり約86%はこの楕円に入ることになります。楕円でなく正方形になっている場合は、まだクエリとして一度も選ばれていないため初期分布から変化していないことを示しています。

赤の楕円はクエリ後の推定域です。クエリ前に比べて小さくなっていることから、精度が上がっていることが分かります。

Lが大きい場合

点を正三角形状に順につなげています。一気に情報が得られるのでLが小さい場合に比べてターンあたりの情報量がお得です。

グループ分け

何も良い方法が思いつかなかったので焼きなましです。

評価関数を MST の長さにすると計算量がやばいので工夫しました。

高校数学で習ったあれを思い出していました。

これ： $| \vec{a} - \vec{b} |^{2} = | \vec{a} | ^{2} - 2\vec{a}\cdot\vec{b} + |\vec{b} |^{2}$

例えば $k$ 点 $A_{1},\ A_{2},\ \cdots A_{k}$ の集合に点 $X$ を追加した場合の寄与は

$\displaystyle\sum_{i=1}^{k}| \vec{x} - \vec{a_{i}} |^{2} = k| \vec{x} | ^{2} - 2\Big(\vec{x}\cdot \displaystyle\sum_{i=1}^{k}\vec{a_{i}} \Big) + \sum_{i=1}^{k}|\vec{a_{i}}|^2$