RECRUIT 日本橋ハーフマラソン 2023夏（AtCoder Heuristic Contest 022）解説

AHC022 お疲れ様でした。相対スコア 1,604,106,037,513 点で 1063 人中 48 位でした。長期コンテストで 2 桁順位を取れたのは初めてなので、記念に解法記事を書きます。

問題概要

ワームホールの入口と出口が N 個ずつありますが、その対応付けは分かっていません。ワームホールの出口周辺の気温情報を頼りに、対応付けを推定してください。ただし、最初に一回だけ出口セルがある空間の温度を自由に設定できます。

atcoder.jp

基本方針

基本的には以下の方針で解き、パラメータの値によって方針を多少変化させました。

配置パート
- 適当な順序で出口セルに温度 $0, P, 2P, \cdots , (N-1)P$ を割り当て、その他のマスの温度は盤面全体の温度勾配が滑らかになるよう設定する
計測パート
- ワームホールは出力の確信度合いが最も低いものを選ぶ
- 移動量は予想される出力の分散が最も大きいものを選ぶ
回答パート
- 全体の尤度が最大になるように $(0, 1, ... , N-1)$ の順列を選択し、回答する

配置パート

基本

まず適当な出口セルの温度を $0$ に設定し、この出口セルからマンハッタン距離の近い順に温度 $P, 2P, … , (N-1)P$ を割り当てます。温度を $0$ にするセルは、もっとも配置コストが小さくなるように選びます。 $P$ は $L, N, S$ の値から適当に決めます。

その他のマスの温度は盤面全体の温度勾配が滑らかになるよう設定します。ボロノイ図のような感じで温度を適当に埋めてから、出口セルの温度だけ固定してガウシアンぼかしを繰り返し適用すると、右のように盤面全体で滑らかな温度勾配を得られます。

$S, N$ が大きい場合：極端な温度のセルを作る

$S, N$ が大きい場合、基本方針だけでは近い出口セル同士の区別がつかず、正答率が下がってしまいます。その対策として、極端な温度を持つセルを $1, 2$ 個つくると、各出口セルの位置推定が容易になり、 $S$ が非常に大きいケースの正解率が上昇します。（という理屈が働いていると思うのですが、本当かどうかはわかりません……）

seed=8 (L=30 N=87 S=784) の場合は極端な温度のセルを 2 個用意する

計測パート

前提となる確率計算

ワームホール $i$ に関する観測情報の集合 $\mathbf{\theta}_i=(\mathbf{\theta}_{i1},\mathbf{\theta}_{i2},\cdots,\mathbf{\theta}_{im_i})$ をもとに、対応する出口が $j$ である確率 $P(p_{ij}\mid\theta_i)$ を計算することができます。ワームホールの入り口と出口の対応がランダムであることを利用すると、ベイズの定理より以下が成り立ちます。

$P(p_{ij}\mid\theta_i)=\displaystyle\frac{P(\theta_i\mid p_{ij})}{\sum_{j'=0}^{N-1} P(\theta_i\mid p_{ij'})}$

ところで、右辺に登場する $P(\theta_i\mid p_{ij})$ は計算で求めることができます。ワームホール $i$ の出口が $j$ であると仮定すると、そこから $(y,x)$ だけ移動したセルの位置と、そこで観測できる温度の確率分布が決まります。したがって、各観測情報 $\theta_{ik}$ から $P(\theta_{ik}\mid p_{ij})$ は計算可能なので、そこから以下が得られます。

$P(\theta_i\mid p_{ij})=\displaystyle\prod_{k=1}^{m_i} P(\theta_{ik}\mid p_{ij})$

基本

ワームホールの選び方

$\max_j P(p_{ij}\mid\theta_i)$ を、ワームホール $i$ と出口セルとの対応付けの確信度合いとみなします。全部のワームホールで自信を持って回答するため、確信度合いが最も低いワームホール $i$ を都度選択しました。確信度合いの最小値が一定値を超えると計測パートを終了し、回答に移ります。

移動量の選び方

ワームホールを選択した後、観測地点の出口セルからの移動量を決定します。このとき、もっとも出口セルを判別しやすい場所として、観測される温度の予測値の分散が最も大きくなる地点を選択します。

$S, N$ が小さい場合：移動量を制限する

$S, N$ が小さい場合は移動量 $(y,x)$ を制限しても全問正解することができます。計測コストは 1 回あたり $100\times (10+|y|+|x|)$ かかるため、移動量を制限して計測コストを下げることが可能です。

回答パート

回答パートでは、全体の尤度 $\prod_{i=0}^{N-1} P(p_{iE_i}\mid\theta_i)$ が最大になるような $(0, 1, ... , N-1)$ の順列 $(E_0, E_1, ... , E_{N-1})$ を選択し、出力しました。この最大化問題は以下のグラフの最小費用流問題に帰着して解くことが可能です。

最小費用流問題に帰着して順列を推定する形にすると、他のワームホールに関する観測情報も加味して出口セルを推定できるのがメリットですが、出口セルの推定を一度に 2 個間違えてしまう可能性があるのが難点です。全体的な正解率は最小費用流を使用したほうが高かったため、採用しました。

提出

以上をすべて実装したのが以下の提出になります。詳細なパラメータや、具体的な計算方法などはこちらを参考にしてください。

atcoder.jp

感想

最初は問題文の読解に手こずり、難しそうな問題だなと思っていたのですが、いざ取り組んでみると各パートで工夫のしがいがあって面白く、ビジュアライザも見映えがあって楽しい問題でした。

長期の AHC に本腰を入れて取り組んだのは（多分）初めてなので、普段よりよい順位を取れてよかったです。観測・回答パートでは統計の知識がかなり役立った感じがあります。一方で、 $S, N$ が大きい場合の配置パートに関しては考察不足でした。どうせ $S$ が大きいと各出口セルの温度は比較的どうでもよくなるのですが、 $S, N$ が小さい場合から大きく方針を変えるのは思い至りませんでした。最後の数日はパラメータ調整ばかりやっていたので、もう少し方針転換について考えてもよかったかもしれません。