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

参加しながら考えたこと試したことの源泉かけ流し。

最終的な方針は まとめ にまとめてあります。

問題概要

atcoder.jp

N×N のグリッドがあり、K 種類のサーバが 100 個ずつ配置されている。これらのサーバを真っ直ぐなケーブルで繋ぎクラスタを作る。ケーブルは交差できない。サーバは上下左右のセルへ移動させることができる。移動とケーブル接続の操作は合わせて 100 * K 回行うことができる。クラスタ内の同じ種類のサーバのペアごとに 1 点、違う種類のサーバのペアごとに -1 点を得る。スコアを最大化せよ。

1 日目

問題を読む。グゥゥ、面白い...！

今回の AHC はスコアの正規化がされないのね。

移動+接続の回数の上限がコンピュータ数と一緒なので、全ての Server を接続しようとするとほとんど移動ができないわけね。

同じ Server を繋いでいくと O(n2) でスコアは増加していくのに対し、違う Server が混入したときのペナルティは O(n) で増加なので、多少違う Server がクラスタに混じってもデカいクラスタを作るべきか。

N が小さくて Server ギュウギュウのケース、K=2 ならまだしも K=5 とかはこれロクなスコア取れる気がしないな...。

うーん、とりあえず小さいクラスタちまちま作るよりはデカいの 1 つボン！と作った方が強いので、どれか一つの種類の Server のみに注目して頑張ってクラスタ作る感じで進めてみるか...？

  1. 何もしなくても繋げるところは仮で繋いでクラスタとする
  2. あるクラスタから他の各クラスタに対し最少何手で繋げられるようになるか計算して、一番手数が少なかったクラスタを実際に接続できるよう色々動かしクラスタを合体させる
    • ペナルティを受け入れて別の Server を経由して繋げるようなケースもある

こんな感じ？プリム法みたいなイメージ。

...ん、どれか一種類の Server に注目してそれを繋げることに注力すると考えると、K の値に拠らずスコア上限が 4950 になるのでテストケース毎の重みもそんなに差がなくなってくるのか。
だからスコア正規化されてないのかな。そういうことなんスよね、tomerun さん...！

や、K=2 とかになるとどっちの種類も繋げていかないといけない気はするな。
100 個のクラスタ 1 つと 70 個のクラスタ 2 つが概ね同じくらいのスコアになるらしい。そう言われると難しいような？
まぁ今はそれはいいや。

2 日目

あるクラスタから他の各クラスタに対し最少何手で繋げられるようになるか計算して

これの実装が重くて難儀している。

いや、4 割くらいのテストケースでは 100 個繋げて 4950 点取れるようにはなったんだけど、下図のような他の種類のサーバに埋もれてるのを掘り起こさないといけないようなパターンがまだ実装できてない。

順位表見ると今のトップで平均 5350 点くらいなので、掘り起こし + 余った手数で他の種類のサーバを繋げるをやればまだなんとか追いつけそうに見える。焦ることはない。

3 日目

違う種類に埋もれてるサーバを掘り起こす操作を実装し、平均 4700 点くらい出せるようになった。

嬉しい誤算として、K=5 の N 最小ギチギチケースでも思ったよりなんとか繋げられるらしいことが分かった。

ギチギチ系のケースは K=5 よりも K=3 とかの方がキツいようだ。

ここまで来れば一旦デカクラスタ作る処理は OK かな。
残った手数で他の種類のサーバを繋げる処理を書こう。

他の種類のサーバも（既に確定したクラスタのサーバには触れずに）メインのサーバと同じ手順でデカクラスタ作るようにした！

後は一連の処理が高々数十 ms で終わって時間が余ってるので、クラスタのマージ順とかに若干ランダム性を持たせてたくさん解作ってベスト選ぶやつをやる。

これで平均 5750 点、提出して 300,479 点！

8000 点超えのケースがあったので覗いてみたらこんな感じになっていた。

なるほど、確かにうまく噛み合わせれば 2 個目のデカクラスタもかなり大きくできるのね。
ただこれ狙ってできるものなのかなぁ。

デカクラスタが出来上がった後、連結箇所を切り替えることで残されたスペースの最大区画を大きくできるならやる、みたいな？
クラスタは木なので、どこかを繋げるとループができて、ループ上の連結箇所は 1 箇所切っても OK になるので、そんな感じで連結箇所の切り替えを行うイメージ。

プリム法のベースのクラスタとして一番サーバ数の大きいものを選んでいたけど、これをたまにランダムに選ぶようにしたらもう少し伸びて 307,036 点。

4 日目

連結箇所の切り替え、ノーコストで行える（=サーバをズラすことなく繋ぎ変えられる）ケースがあまりなくて、後回しで良いかなという気持ちになってきた。

それより

あるクラスタから他の各クラスタに対し最少何手で繋げられるようになるか計算して

これの繋ぎ方のバリエーションがまだ少し詰められそう。
例えば、一種類目のサーバのクラスタを確定させて次の種類のサーバの処理に移ると、確定させたクラスタのサーバは絶対に動かさないようにしてるんだけど、次数 1 のサーバをケーブル縮める方向に動かすのは何の問題もないので、これで別のクラスタを繋げられるようになるなら試すべき。

↑ を実装して手元で 1 ケース平均 230 点くらい伸びた！
クラスタの繋げ方のバリエーション増やしていくと着実に伸ばせるような気がするね。

他にも埋もれてるサーバを掘り起こしてクラスタ繋げるパターンをもう少し磨いて平均 +100 点くらい。

ここで提出して 327,359 点。
暫定順位は 2 位だけど 1 位と 30k 点差くらいつけられている。えぇ...。

5 日目

繋ぎ方のバリエーション追加をちまちま試してみるも、なかなか伸びなくなってきた。うーむ...。

ビジュアライザを眺めてて思ったのだけど、最初に作るデカクラスタが盤面いっぱい使っていると、他の種類のサーバでクラスタ作る際に領域が分断されてしまっていてあまり大きいものが作れなくなる。
ので、最初にクラスタ作るサーバはちょっと中央に寄せて、盤面端は必ず開けるようにしてみたらどうだろう。

例えば下図は 4 番（緑）のサーバが最初のクラスタ。
盤面を上下に大きく分断してしまっている。

これ思ったより効いて、平均 200 点くらい改善した！
下図では 2 番（濃い青）が最初のクラスタ。

提出して 341,774 点。イイネ！

密度の高い盤面に対して何も特別なことをしてないので良くない気がしてきたので盤面を眺めている。

下図は密度 80% くらいのケース。
このくらいの密度なら最初のクラスタは 100 個繋げられるらしい。思ってたより優秀。

下図は密度 90% くらいのケース。
ここまで来ると 100 個繋げられなくなってくる。

これ見ると数少ない空きセルをケーブルに使ってるのがもったいないので、ケーブルの分ギュッとサーバを詰めて空いたセル活用して他のサーバを誘致できそうな気がする。

密度高のケース考えるのがダルくてちまちま高速化やって平均 100 点くらい伸びた。
でもそろそろ頭打ち感あるので他のことやろうね。

6 日目

繋ぎ方のバリエーションを追加したら平均 160 点くらい伸びた。ワァァ
具体的には「あるクラスタのサーバから 4 方向に直線を伸ばして、直線が同じ種類の他のクラスタにぶつかったら繋ぐ（途中違う種類のサーバにぶつかったら最寄りの空きセルに移動させる）」という操作があったのだけど、これを直線の当たり判定を脇に 4 マス分くらい広げて、脇に見つけたサーバは直線上に引き寄せるみたいなことをした。

途中の障害物をどけつつ繋ぐタイプのバリエーションはまだ伸び代があるのかも。

繋ぎ方のバリエーションに少し手を加えて平均 140 点くらい伸びた。
具体的には「次数 1 のサーバをクラスタからパージして目的のクラスタからのケーブル射程範囲内に移動させて繋ぐ」という操作で、ケーブル上は通過できないつもりだったのだけど良く考えたら通過しても何の問題もない（実際に接続するのは移動後だから）ので、そうした。

これ、つまりは 1 個目のデカクラスタ作った後、それによって分断された領域からもサーバを持ってこれるようになったってことなので、それがスコアに響いたのかな〜という気がする。
...ってことはやっぱりデカクラスタの連結箇所を切り替えるやつ試してみるべきなのでは？
でもこれ実装重いし改善しなかったらショックが大きいので手付けづらいんだよな...。
そもそも今って 1 個目のデカクラスタは極力盤面端にサーバ配置しないようにしてるからそれほど領域の分断が起こってなくて、効果薄な気がする。

繋ぎ方のバリエーションに少し手を加えて平均 100 点くらい伸びた。
具体的には「あるクラスタのサーバから 4 方向に直線を伸ばして、直線が同じ種類の他のクラスタにぶつかったら繋ぐ（途中違う種類のサーバにぶつかったら最寄りの空きセルに移動させる）」の操作で、実装を簡単にするため障害物をどけるパスとしてサーバからの直線上を通るのを禁止してたのだけど、これだと幅 1 の細い通路上に障害物があった場合にどうにもならなくなるので、ちゃんと実装してあげた。

ここらで提出して 370,026 点。

繋がりそうな見込みがないクラスタ同士はそもそも繋ぎ方候補の探索をスキップした方が良い気がしてきた。

いろいろ試したけど一番良かったのは、クラスタ内のサーバを矩形で囲った左上、右下をそれぞれ min_pt, max_pt として、クラスタ同士の距離を下の定義にしたとき、距離が 4 以上のクラスタ同士は繋ぎ方候補の探索をしないようにした時で、平均 100 点くらい伸びた。

int distance(const Cluster& c1, const Cluster& c2) {
    int dx = max(0, max(c1.min_pt.x, c2.min_pt.x) - min(c1.max_pt.x, c2.max_pt.x));
    int dy = max(0, max(c1.min_pt.y, c2.min_pt.y) - min(c1.max_pt.y, c2.max_pt.y));
    return max(dx,dy);
}

min(dx, dy) じゃなくて max(dx, dy) の方が伸びるのかなり意外だな。
かなり過剰に枝刈りしちゃいそうだけど、それが逆に良いのかしら。
実際 K=5 とかでは 5 倍くらいソルバを回せるようになってる。

ここで 10000 点超えのケースが生えたので記念にペタリ。
4 と 5 のサーバでそれぞれサイズ 100 のクラスタができている。スゴイ！

7 日目

いい加減密度高い盤面の対策をやろう。

手軽に空きスペース作る方法として、次数が 1 のサーバをケーブル縮める方向に移動させるというのがある。
いずれの 2 つのクラスタのペアについても接続する方法が見つからなかったとき、これをやって空きスペースを作った後再チャレンジするようにしよう。

これ有効なのは密度が 80% 以上くらいかな〜と思ってたけど、意外にも密度 63% 以上のケースで改修前と比べてスコア差がプラス収支になった。
全体だと平均 25 点アップくらい。対象ケースが少ないだけにまぁそんなもんか。

そうなるとやっぱり 7000~8000 点くらいに留まってるケースを伸ばしてあげる方が良いかもしれない。

アイデアが湧かないので N, K 毎の得点平均を表にしてみた。

K=4,5 の場合は N に対してスコアが右肩上がりっぽくなってるけど、K=2,3 だと N が大きすぎるとスコアが下がっていくようだ。
盤面が大きいと移動コストがかかって手数制限が厳しくなってくるんだね。

K=3, N 最大のケースのうちスコアが一番低いものを覗いてみた。

うっ、これは明らかに真ん中を横に分断している赤いケーブルが邪魔になってる...。盤面端は通れるようになってるとはいえこれは厳しい。
まぁ他のケースはこれほど酷いことにはなってないし、乱択だとこういうこともあるよねという感じかなぁ。
よく見たら昨日の 10000 点取れたケースも縦に真っ二つな繋ぎ方してるけどうまくいってるし。

結局この後劇的なスコアアップはなくて、ランダム性追加したり密なケースでスライドパズルっぽく運ぶのを実装したりしてちまちまスコアを伸ばして終わった。

まとめ

暫定順位 / スコア

6 位 / 383,023

方針

  • 乱択山登りをたくさんやって一番良かった解を返す
  • 山登りでは、1 種類のサーバにのみ注目し、クラスタ同士をプリム法のような感じで徐々に繋げていく。1 種類のサーバを繋ぎ終わったら次の種類へ。
  • クラスタ同士の繋ぎ方の候補は概ね↓のような感じ。

  • 遠いクラスタ同士は繋ぎ方の候補の探索をスキップするなどして高速化。