RECRUIT 日本橋ハーフマラソン 2022夏(AHC013) 参加記
問題
成績
最終 2000 テストケースで 13,808,196 点 (平均 6904 点)、 19th / 850 でした。2回目の橙パフォ＋レート黄色到達＋1ページ目めでたい！
解法
自分の解法は、ざっくり以下の通りです。
- 貪欲法っぽく同じ種類のサーバを繋げて巨大な木を構成する操作を、1種類ずつ行っていく
- 2種類目以降のサーバを繋げやすくするために、最初に作る種類のサーバだけ入れない領域を作成する
- 空白が足りなくなったら、既に繋げたサーバ間の空白を消して縮める
- 木の構築開始地点、禁止領域の形、木を構築するサーバの種類の順序を色々試して最善のものを選択
以下、もう少し詳細です。
同じ種類のサーバを繋げて巨大な木を構成
得点の計算方法から複数の小さなクラスタを作るよりも一つの大きなクラスタを作った方が高得点になりやすいため、同じ種類のサーバを100台繋げることを目指します。巨大な木を作るために、1台ずつサーバをくっつけて木を構築する方法を実装しました。
ただし、真面目にコスト計算すると処理が重いと判断して、クラスタに属するサーバと、クラスタに属さないサーバを接続するためのコストを、以下のように妥協して見積もりました。
例えば、上の図で種類 "3" のサーバを接続する場合として、左上のクラスタ内に接続されたサーバを、右下のクラスタに属さないサーバに接続する例を考えてみます。この場合、
- 各サーバを上下左右に動かす範囲、かつ2サーバで構築される長方形領域内部に限定して、どの位置で接続するかを列挙する
- 各サーバを移動する軌跡および予定する接続上に存在する、種類 "3" 以外のサーバの個数を計測（邪魔なサーバ、と呼びます）
- 接続を作るためにどかす必要のある、邪魔なサーバの個数が最も少ない接続の位置を選択する
という流れで、接続位置の候補を決めます。
この例では上下の接続5本、左右の接続候補5本のうち、右から2番目の縦方向に接続しようとします。
ただし、結構細かな実装は割と複雑で、
- クラスタに属するサーバは、既にある接続の整合性を保ったまま動ける範囲は限られている可能性があるので、その場合はより限定された候補になりえる
- 既に同じ数字で接続が張られているところへ移動する場合は、その接続の整合性を保ったまま1マスずつ動かす関数を実装して頑張る
等を考慮する必要があります。
（クラスタに属するサーバ、クラスタに属さないサーバ）のペアは、サーバ間の $x$ 座標、$y$ 座標の差分をそれぞれ $dx, dy$ とすると、 $ \min(dx, dy) <= 3 $ に収まる範囲で全探索しました。これは、接続までに要するターン数の下限が $ \min(dx, dy) $ のためです。
実際に上記の接続を行うときは、邪魔なサーバを最も近い空白へ押しやるために毎回復元付きの BFS で邪魔なサーバをどかしています。ただし、後から全体を俯瞰した時に明らかに手損の状態もそのまま残して進んでいきます。
最初に作る種類のサーバだけ入れない領域を作成
上記の方法でサーバを自由に繋げた場合、2種類目以降に作るクラスタの木のサイズが小さくなってしまったため、最初にクラスタを構築する種類のサーバだけが入れない、かつ接続の辺も張れない領域として、上記のような王の字を指定しました。例えば、1 → 2 の順にクラスタを作るとすると、1は王の字に辺も含めて入ることができないため、次にクラスタを作る種類である2の木が構築しやすいことが期待できます。王の形は、横方向に盤面サイズ/4、縦方向に4マスを空けた、幅2の王の字のみを試しました（最終的にこの形になったのは、単に時間が足りなかったからです）。
ただし、特に空白が少ない場合などでは禁止領域がない方がよい場合もあったので、全く制約を書けない場合なども試しています。
最初は上記のように周囲2マスを空けるような禁止領域を作ったのですが、開発序盤で貪欲法の探索部が弱かったことで移動量の損がかさんでしまったりしたこともあり、最終的な調整まで間に合いませんでした。王の字の形状は、周囲2マスを全部禁止にするよりも禁止領域の面積が狭くある程度全体に届くため、私の解法のように貪欲法の探索度合いが弱くても機能しやすいかなぁという気持ちで設計しました。
余談ですが、後で周囲2マスを禁止領域に指定するコードも後日追加してみたところ、それだけで50テストケースで 350,376 → 354,334 になったので、王の字で全てはカバーできていなかったようです。結果論ですが、コンテスト残り2時間の時に一番費用対効果が高かったのはこの部分だったのかもですね。
既に繋げたクラスタを縮める
上記のように、空白が少ないテストケースだと、雑に貪欲で繋げていくとすぐに空白がないせいで手詰まりになってしまいます。そこで、手詰まりを回避するために、余計なサーバが移動不可能になったら既に繋げたサーバ間の接続の空白を見つけて縮める操作を行いました。
色々試して最善のものを選択
高速化する時間が十分とれず、1試行解を作るのに数10ms 程度必要だったので、Nが小さなテストケースでも100回程度しか試行回数が稼げませんでした。
そのため、乱数に頼って乱択せずとも、（クラスタを構築するサーバの種類の順序、最初の種類のサーバで木を構築開始する地点、禁止領域のパターン）を色々変えて一番良い解を出力するだけで十分時間を使い切ることができました。
結果の解釈
テストケース毎の分布は、wleite さんの統計情報がとても参考になりました。
終わってみれば、サーバの種類が少ない K = 2 がとても弱かったようです。クラスタを構築するための手順が全然最適化できていなかったので、雰囲気的には貪欲に繋げていく方法が限定的であったり、山登りなり焼きなましできなかった弱点が出てしまったのかなと感じています。
起きたこと（時系列）
本当にメモを取る余裕がなかったので、今回は何も書けず…
所感
- 実装に苦労したコンテストでしたが、実装に苦労した分最初に100サーバ全部繋がった時にはめちゃくちゃ嬉しかった（AHC011 や AHC008 みたいに実装が大変だった系のコンテストは結構そうなりがち）。
- 今回みたいに実装が重いコンテストは、実際にコードにバグはないけど論理的にバグがある状況になりがちなので、もう少しデバッグ周りで補助ツールを充実させたいなという気持ちになりました。これいつも言ってる気がするけど。
- 次こそこういう実装重いコンテストで焼きなましたい。こっそり練習頑張ります。
