RECRUIT 日本橋ハーフマラソン 2022夏（AtCoder Heuristic Contest 013）

問題概要
解法概略
実装概要
過程
まとめ等

暫定25位（327,798点）、最終31位（12,887,959点）の者の解法概要とそれに至る過程です。

問題概要

A - Server Room

$N \times N$ の二次元グリッド上に $1$ ～ $K$ の数字が書かれたマスが $100$ 個ずつあり、その他のマスは空白。
移動と接続の操作を合計回までできる。
- 移動：数字が書かれたマスを上下左右に隣接する空白マスに移動させる。
- 接続：同じ行または列にある数字が書かれたマス同士を接続する。距離の制限はなし。接続線同士が交差したり別の数字マスを飛び越えたりするのは不可。
同一連結成分に存在する同じ数字の組ごとに $+1$ 点。
同一連結成分に存在する異なる数字の組ごとに $-1$ 点。

※以下数字のことを色と呼ぶ。
※また、以下の解法等の記載は実際の実装と比べてアバウトであり、細かい点まで正確とは限らない。

解法概略

連結成分のサイズを $M$ とすると $O(M^2)$ で点数が増えるため、まず $1$ 色からなる連結成分を貪欲に大きくする。　具体的にはダイクストラ法で連結成分の付近にある同色マスを見つけ、連結成分の上下左右の延長線上に動かして間の他色マスをどける。
その後 $2$ 色目について、 $1$ 色目の部分を基本的には動かさずに1色目と同様のロジックで大きくする。　 $2$ 色目が完成するにはほぼ至らなかったので、 $3$ 色目以降は考えない。
移動回数 $+$ $(2$ つの連結成分のサイズの和 $)$ が $100K$ に達するまで連結成分を大きくするための移動を行う。
移動の後接続時に手数が余ったら、連結成分のサイズを大きくできる箇所から優先的に接続する。
$1$ 色目と $2$ 色目を何にするかを $_KP_2$ 通り試す。
$N$ が小さいケースでは上記1.で間の他色マスをどける必要がある動かし方の優先度を下げたいと思い、一部ケースだけダイクストラで遷移のコストを重くしようとしたが、最終的には $N$ によらず全ケースでその処理のコストを $1$ 倍から $4$ 倍まで試すようにした。*1

実装概要

初期位置のまま可能な限り同じ色を接続したものを初期解とする。
　
初期解の中で最大の連結成分に対し、連結成分に含まれない同色マスを近いものから連結成分のいずれかのマスと接続可能な位置に移動させていく。
　
「近いものから」の部分は最大連結成分が占有するスペース内の各マスを始点としたダイクストラ法で。
　コストは基本 $1$ だが、他色マスへの遷移は $2$ にしたりなど。通常の $4$ 方向に距離 $1$ ずつ前述のコストで遷移する他、移動を完了させたマスから $4$ 方向に（同色マスに当たるまで）距離無制限にコスト「他色マスを通過した回数」でも遷移。*2

　
「接続可能な位置に移動」の部分は、移動させたいマスを起点としたダイクストラ法で。
　ここではほぼ実際の移動にかかる手数（下記5.も考慮）をコストにした。なお実際に盤面情報を更新せず求めているため、他色マスが複数存在したりすると正確ではない。（例えば下図で移動させたいマスから左側を調べていった時に、邪魔なマス $2$ つをどちらもどけるコスト $2$ で見積もってしまうが、実際は干渉し合ってもう $1$ 手余計にかかる。）

　キューから取り出した座標が目的の連結成分のいずれかの数字マスから上下左右の延長線上に達した時点で終了。　ただし、間に他色マスが存在する場合は、それらを動かすコストを加算して再度キューに追加し、再び取り出された時点で終了とする。

　
上記4.の際、目的の位置へ移動させる途中に他色マスが存在する場合はそれらも動かす。
目的の位置へ到達後、接続先との間に他色マスが存在する場合はそれらも動かす。
　
邪魔な他色マスの動かし方は、ダイクストラ法で最も近い空白マスを探し、経路復元によって空白マスを邪魔なマスの位置まで移動させてくる形。
　ここではコストは基本 $1$ だが、 $1$ 色目のマス（ $2$ 色目処理中の場合）、処理中色で接続に使用予定のマス、他色マスの部分は $+1$ した。*3
邪魔なマスを動かす際、動かしたい先が既存の連結成分と被る場合でも、接続部分であれば通過可能とする。　これは既存連結成分の接続部分は目的の空白マスとみなさず、経路復元時に接続部分に邪魔マスが残ってしまった場合はもう一度それを動かす対象とすることで実現。
邪魔なマスを動かす際、動かしたい先が既存連結成分を木とした時の葉の部分であり、葉と繋がる辺の方向が空白マスの場合は、その方向に $1$ マス動かして既存連結成分の占有スペースを $1$ マス減らすことができるようにも対応。*4

　
上記2～9.をまず $1$ 色目について実施。
　
ここまでの移動結果を元に一旦可能な限り接続する処理を行う。
接続する処理では、前提としてUnionFindを使って閉路ができないようにする。
　
まず $1$ 色目のみ隣接マスを全て接続する。隣接マスの接続であれば、他の接続の邪魔になることはないため。
　
上記10.までで接続可能位置に移動させてきたマスの順番に接続処理を行っていく。この際、接続に使用予定として確保していたマスのみを通って接続可能なマスとのみ接続する。*5
　
あとは $1$ 色目→ $(2$ 色目→ $)$ その他の順、サイズが大きい連結成分順（といっても $1$ 色目の隣接部分しか繋がっていないのでほとんどサイズ $1$ だが）、サイズが大きい連結成分と繋がる箇所順に接続を行っていく。
上記15.の接続を操作回数の上限なしに可能な限り行った後、その結果を使ってもう一度接続処理をやり直す。（今度は「サイズが大きい連結成分順」の条件が生きてくる）
　
上記16.までの結果を初期解とし、 $1$ 色目が占有するマスと $2$ 色目で最大の連結成分を特定した後、上記2～16.の処理を $2$ 色目に対して行う。
　
ロジックが不完全なため、以下のように前回の結果からやり直すということを繰り返した。
1. 初期位置のまま接続した結果
2. $1$ 色目を育てて一旦接続した結果
3. 接続処理をやり直した結果
4. $2$ 色目を育てて一旦接続した結果
5. 接続処理をやり直した結果
6. 上記2～5.をあと $2$ 回繰り返し*6
  　
解法概要の5.と6.に記載の、 $1$ 色目と $2$ 色目の組み合わせと、他色マスをどけるコストの倍率ごとに、上記18-1.を起点にして同様の試行を行い、最良の結果を取得する。
　
接続処理を無制限に行っているため、出力時は移動と合わせて $100K$ 回の時点で打ち切るようにする。*7

過程

参加時間確保

どうせ取らなければならない休暇がまだ残っていたので、8/15と16に使う。
8/9, 10, 12を在宅勤務にする。*8

スコア感と方向性を確認

とりあえずどういう接続の仕方をしたら高得点になるのかを簡単に確認する。
- 例えば $1$ 色のみ $10$ マスからなる連結成分を作れば、 $_{10}C_2=45$ 点。
- $2$ 色が $10$ マスずつからなる連結成分を作ると、 $45+45-10 \times 10=-10$ 点。
- 同色 $100$ 個の中に別の色が $1$ 個紛れ込むくらいなら、 $4950-100$ 点でまあ十分プラスではある。

満点を取るためには $99K$ 回接続する必要があり、全然移動できないのでさすがにあり得ない。
何割くらいを移動に費やすことになるのかよくわからないが、最終的には $3$ 色くらいまとめて揃えていけるようになる必要があったりするのだろうか。

各色をまんべんなくそこそこの大きさにするよりは、 $1$ 色を大きくした方が良さそうなので、そこから手を付けていくことにする。

比較的簡単にできることから実装

最後の詰めの段階では $1$ マスを隔てて大きな連結成分 $2$ つが繋がるような場合も考える必要があるかもしれないが、一旦忘れることにして必ず同色同士しか接続しないことにする。*9

とりあえず接続しないと $0$ 点なので、隣接する同色マスだけ接続してみる。　 $7,555$ 点でサンプルコード以下。

離れたマスも接続してみる。交差する場合にどちらを優先するのが最適化はわからないが、とりあえず実装概要15.のような連結成分の大きい順の貪欲とする。　 $32,000$ 点ほど。

得点計算も実装しておく。　移動元が数字で移動先が空白であるかどうか、接続時に同一行/列の数字マスを指定しているか、交差や通り抜けが発生していないか、といったチェックもなるべく入れておく。*10

$1$ つ動かせば接続できるようなマスを動かしてみる。　 $41,000$ 点ほど。　ただしこれだけの操作のための実装では後々使い物にならず、遠からず捨てることになる。

基本的な移動処理を実装

まだ手数が余りまくりなので、ここまで実装した結果を元にさらに良い操作を付け足していくようなことをしたくなってくる。

$1$ 色に注力してダイクストラとその経路復元で起点とした最大の連結成分に近付けていくことをやり始める。

ビジュアライザを見ていると、接続させたい単独のマスを移動させるのではなく、間の邪魔なマスをどけた方が少ない手数で済むことも多い。　ひとまず、同色の $2$ マスの間に他色マスが $1$ つだけある場合、それを $1$ マス脇に動かせるようにする。
移動経路の途中に邪魔なマスがあった場合にも脇に動かせるようにする。

この時点では邪魔なマスをどけるのは脇が空いていて $1$ 手で動かせる場合のみなので、密ケースでは多分ほとんど機能しておらず、繋げたいマスも途中まで動かしてきて結局他のマスが邪魔で繋げられないということが多かったと思われる。

移動にしても接続にしても、前回結果（移動は戻さず、接続は連結成分サイズの情報だけ参考にする）を元にやり直せば状況が変わっていて成功するような場合が実験している限りではよくあり、確実に成功するようにあらゆるケースを考えたロジックにするよりは、とりあえず数回繰り返す方がお手軽だった。

ここまでで $220,000$ 点ほど。　実際にはビジュアライザを確認して意図通りに動いていないところを見つけて修正しながら $2$ 万点くらいずつ上がっていっていた。

移動処理の確実性向上

実装概要7.の通り、空白マスが隣にない場合でも邪魔なマスをどけられるように改善。ただしこの時点ではまだ接続で使用予定になっているマスには立ち入れない状態。

移動処理で目指すマスを知るため、起点の連結成分に $1$ つ繋げる度に「ここに移動させれば接続可能になる」というマスの情報を更新するようにしていたが、邪魔なマスを動かすことが増えたため、接続可能ラインが途中でふさがれたりなどして情報が正確でなくなっていた。
このため、情報更新のタイミングを増やしたり、移動の際に本当に接続可能か確認し直したりする。　 $270,000$ 点ほど。

移動のさせ方を改善

最終形が決まれば、必ずしもこれまで移動させてきた通りではなく、初期形と最終形で同じ色のマス同士ならマッチングを変えてもよい。
疎ケースでは各マスがマンハッタン距離しか動かない最適な移動ができて、密ケースではAHC011（スライドパズル）で有効だったビームサーチとかやってもいいのではないか。
とりあえずマンハッタン距離をコストにして最小費用流をやってみるが、最密ケースは別としても、他はそんなに何十手も違いがある感じではなさそう。
ビームサーチとかを書き慣れているわけでもないので、ラスト $1$ ～ $2$ 日でやることがなくなったら考えることにする。*11

これまで繋げたいマスの移動ルートが起点連結成分からダイクストラを行って遷移元をたどって行くようなものだったが、ビジュアライザを見るとわざわざ遠い接続可能地点を目指していることがあった。　そもそも遷移のコスト設定が適当なのと盤面の変化に対応できていないためっぽい。
そこで、実装概要4.のように移動ルートを求めるためにダイクストラを行うようにする。　ここらで $300,000$ 点を超えてくる。

さらに、前々からビジュアライザを見ていつかは対応したいと思っていた、実装概要8.や9.を散々バグり散らかしながら実装する。　 $310,000$ 点台になる。

結局まだ連結を $1$ マス増やすのに長大な手数をかけて移動させているようなケースがあり、起点連結成分からのダイクストラの時点でもう少し正確に移動コストを求めて調べる順序を良くしたいと考えるが、もうあまり時間がない。
調べる順序は必ずしも低コスト順でなくても、最終的に $100$ マス繋げ切るならそんなに違いは出なそう。それよりは移動ルートを決めるダイクストラの方をなんとかしたい気がする。
そこで、解法概略6.のように他色マスをどける必要があるマスへの移動はコストを重くすることを考える。本当は実際の手数を求められればいいが、実装概要4.のような問題に対処するのは今更厳しいので適当に倍率を付けて誤魔化すことにする。

初めは最密ケースだけ固定で $2$ 倍とかしようとしていたが、実行時間は余っていたので結局全ケースで $1$ 倍から順に試すこととした。
$N$ や $K$ が大きいケースでは間に合わないこともあるので、時間で打ち切る処理を入れつつ、 $1$ 倍で色の選び方を $_KP_2$ 通り試した後 $2$ 倍で $_KP_2$ 通り、 $\cdots$ となるよう試行順序に注意する。　これで $320,000$ 点台に。

最終提出
　

案はあったがやれなかったこと

実装概要9.で葉の隣が空白の時に $1$ マス引っ込ませることしかできなかったが、できれば隣が空白でなくとも連鎖的に動かせるようにしたかった。

単独マスを起点連結成分に向かって動かすだけでなく、連結成分内の要素（基本的には葉になると思う）の方を動かして接続させる。

ダイクストラの遷移コストをもっと実態に近付ける。　これは実際に移動させている処理から手数だけを得て元に戻すことをラスト $30$ 分ほどでサクっと書ければ入れてみるつもりだったが、動かないケースが出てきてしまったので断念。

「移動のさせ方を改善」の最初に書いていたビームサーチ。

その他バグ取り。以下はseed=0～1999の中での最高点と最低点の結果だが、これらを見ただけでも直したいところがまだすぐに見つかる。

赤丸のところまだ詰んでいないのに他 $3$ 色の接続に手数を使っている。

赤丸のところを接続する手数が足りなくなるなら、最後の方の移動を取りやめたい。

まとめ等

暫定結果：327,798点、25位
最終結果：12,887,959点、31位、パフォーマンス2306相当
レート変動：1907→1987（+80）

25位であればおそらく黄色になっていたが、過去最高パフォでまあ大成功には違いない結果。

序盤から20位台辺りにいた時間が長かったので、方針を根本的に見直すようなことをあまり考えなかったのは良くなかったかもしれない。
4位解説を見て類似点が多いと思ったが、2色を交互に動かすのは考えられていなかったとしても、スタート位置を最大連結成分固定ではなく乱択するくらいはやれていたかった。（なお、終了後にさらっと実装してみた限りでは点数変わらず。多くても400回程度、ひどいと1桁回数しか試行できていなかったが。）
　

これまでの成績は長期だと平均黄パフォあるかないかくらいで、短期だと平均青下位パフォくらい。
ヒューリスティック向けのアルゴリズムに慣れておらず、焼きなましなどを取り入れようとすると1日がかりになってしまうので、焼きなましさらっと書けますか？な短期コンが全然駄目な状態。

焼きなましもビームサーチもなしで、ダイクストラとUnionFindくらいしか使わずここまで戦えたので、自分としてはうれしい問題だった。
とはいえ、もちろんできるようになるに越したことはないのだが。
　

今回はとにかく、ビジュアライザを見ながら「人力でやるとしたらここはこうしたい」を片っ端から実装していった形になったと思う。

*1:平均的にはNが最も小さいケースでのみ2倍にすると良かったが、3倍4倍で改善するケースも0ではなかった。

*2:もう少し実際移動にかかる手数に近付けるのを試したかったが上手くいかず。

*3:ここも重みの付け方もう少しちゃんと検討した方がよかったかも。

*4:葉であるかどうかの判定方法が悪くて最終日にこれのデバッグに3時間以上費やした。

*5:移動処理を完了すると同時に接続処理も行った方が確実で、ビジュアライザにも随時接続状況が反映されてわかりやすかったと思われるが、上記9.のように既に一旦確定させた部分を壊す際に情報の更新が大変になると考えていた。　まず最初に接続する処理を作るところから始めた結果、完全に分離されたというのもあるが。

*6:コンテスト期間初期の頃は5回くらい繰り返していたが、徐々に少ない回数で点数が変わらない状態になるようになっていった。

*7:ビジュアライザで同色の大きい塊があるのに、途中までしか接続されず終わっているということも発生してしまっている。

*8:元々7割ほど在宅勤務しているので、ちょっと意識して出社日にしなかっただけ。

*9:必要性はあまりなさそうではあったが、最後まで忘れたままだった。

*10:後々動作確認時に「数字から空白への移動になっているか」のチェックには散々引っかかったが、おかげで提出してWAになることは一度もなかった。

*11:他にやることが尽きることはなく、これはやらずに終わった。