AtCoder Heuristic Contest 044お疲れ様でした。149,801,634点で2位です。やったー！

今回も軽めに解説記事を書いていきます。

問題概要
解法
コンテスト中の立ち回り
感想

問題概要

いい感じに掃除当番を決めてね。

atcoder.jp

解法

概要

焼きなましをしました。
評価はシンプルなシミュレーションです。
シミュレーションは $L$ を少しずつ大きくして徐々に精緻化していきました。

AHC044、149.801Mで2位。勝ちきれず悔しい……。
焼きなましをしました。AHC039のようにLを3906, 7812, ..., 500000と徐々に精緻化します。初期解は適当。
近傍は1点moveと2点swapで、move, swapのときは相方としてスコアが改善しそうなやつを重みつき乱択で選ぶと結構良くなりました。 #AHC044 pic.twitter.com/QqcWRtQgOB
— TERRY (@terry_u16) 2025年3月16日

解の持ち方

解は $a_i, b_i$ をシンプルに持ちました。

初期解は本当に適当で、 $a_i=b_i=i$ としています。適当すぎ……。まあ焼ける問題なので大丈夫です。

評価関数

上位陣は「親の目標値/2の和が自身の掃除回数になる」というような考察を行っている人が多かったように思いますが、私は愚直にシミュレーションしました。（あの……）

その代わり、シミュレーションの長さ $L_k$ を $L_k=\lfloor 500000/2^{8-k} \rfloor$ $(k=1, 2, \cdots, 8)$ と定め、 $3906, 7812, \cdots, 250000, 500000$ と2冪で伸ばしていきました。これにより徐々に評価の精緻化を行っていきます。 $L_k$ で焼きなました解を $L_{k+1}$ の初期解として、焼きなましを8回行うイメージです。

グラフの連結性を考慮しなくてもよいため、実装はちょっとだけ楽になります。

近傍

近傍は1点変更と2点swapがベースです。 $c=(a_0, \cdots, a_{N-1}, b_0, \cdots, b_{N-1})$ として、

1点変更: $i$ をランダムに1つ選んで、 $c_i$ をランダムな値に変更する
2点swap: $(i, j)$ のペアをランダムに選んで、 $c_i$ と $c_j$ をswapする

という近傍です。

この近傍で焼きなましをしてみると、実行時間を伸ばせばスコアが伸びること、近傍の受理率がさほど高くないことが分かります。愚直シミュレーションのせいでスコア計算が重いので、近傍の計算量を少し増やしてでも筋の良い近傍を選ぶことができるとスコアが伸びそうです。

そこで、完全にランダムに近傍を選ぶのではなく、「なんとなくスコアが上がりそうな近傍」を選ぶような工夫を入れていきます。2点swapの場合を例に取ると、以下のような近傍選択を行いました。1点変更の場合も概ね同様です。

目標値との差異 $\Delta T_i=|t_i-T_i|$ に比例した重みつき確率でランダムに社員を選ぶ
社員 $i$ に向かう有向辺 $e^i$ と社員 $j$ に向かう有向辺 $e^j$ のペア $(e^i, e^j)$ を列挙し、社員 $i, j$ だけを見たときの辺のswapによるスコアの改善量 $\Delta S_{e^i, e^j}$ を計算する
$\Delta S_{e^i, e^j}$ が0以下のもの（スコアが悪化することが見込まれるもの）を候補から外す
$\Delta S_{e^i, e^j}$ に比例した重みつき確率でswapする辺のペア $(e^i, e^j)$ をランダムに選ぶ

1.の重みつき確率は「差異の大きい社員を重点的に改善したい」お気持ちを、4.の重みつき確率は「解が大きく改善しそうな近傍を重点的に選びたい」お気持ちをそれぞれ込めています。2.のスコアの変化量は本来社員 $i, j$ の子孫全てに影響が波及するのですが、ここでは「なんとなくスコアが上がりそうな近傍」を選ぶことが目的なので一旦無視しています。*1

ちなみにこの近傍を入れない状態の解は148.001M点程度（133位相当）でした。相当変わりますね。

なお、最終的には重みつき確率を $\Delta T_i, \Delta S_{e^i, e^j}$ から $\Delta T_i^4, \Delta S_{e^i, e^j}^4$ に変更しています。ほんの少しだけスコアが上がりました。

コンテスト中の立ち回り

ざっくりどのような立ち回りだったか書いていきます。

問題文を読みつつ環境整備（～0h07m）

問題文を読みます。むずい……。

とりあえず環境構築として、公式toolsのダウンロード、pahcerの準備などを行います。

雑焼きなましを実装（～0h23m）

よくわからないので、とりあえず雑な解法を実装して様子を見ることにします。5分くらいで考えた解法を雑に実装して感触を確かめるのはよくやる手段です。

AHC039に少し思いを馳せると、最初は $L$ を粗くして徐々に細かくすることでなんとなくいい感じになりそうな気がするので、そうします。まずは1点変更の焼きなましを実装して投げると139.80M点になりました。まあこんなもんかという印象です。

2点swapを実装（～0h28m）

明らかに2点swapを入れた方が良いので、入れます。147.68Mで暫定3位になり、思ったよりスコアが出せる問題なんだなという気持ちになります。

今回の問題は最終的なスコア目標をどこに置くかで方針が変わってくるので、この情報は結構大きいです。

考察とリファクタ（～1h24m）

さすがに5分くらいで考えた解法では勝てないので、ちゃんとした考察を試みます。

何か賢い構築型解法がないか考えて、 $10000, 5000, 2500, \cdots$ と2冪で $t_i$ を作る解法が思い浮かびました。ただ現時点でトップが149M台になっていて、1人あたりの誤差を $100$ 未満にすることが要求されており、どう頑張っても達成できなさそうなことから棄却しました。