RECRUIT 日本橋ハーフマラソン 2022夏（AHC013）に参加しました。
atcoder.jp問題はServer Room。移動と連結を共通の手数で行う問題でした。
結果は提出948人中74位でした。（暫定50件は56位）
システムテストだと1件平均5200点くらい。
問題
（問題文そのままの用語だと長くなるので、コンピュータの種類は色、コンピュータはサーバと言い換えます。）
グリッド上にあるサーバを動かしたり直線で繋いだりして、良い感じに連結成分を作ってね。サーバは2～5色あるけど、なるべく同じ色同士を繋いでね。
考察
とりあえず点数計算を読むと、同色サーバ100台の4950点クラスタを何個作れるかという問題に見える。
MM139、MM128に似ている。*1密なケースの移動にはAHC011も応用できそうかな。あとHTTFでやった最小全域木。とりあえず今回は、前提としてあまり頑張る気力が無いので安定した点数を取ることを目標にする。
とはいえNやKにより性質が変わり、複数の解法を使い分けることもありえそう。解法は1個か、多くて2個しか実装できないだろうなぁ。汎用性が高くて、4950点（に近い点数）のクラスタを作ることに特化した解法を作りたい。
候補はMM128と同様に目標盤面を作ってから動かすか、最小全域木…かなぁ。でも接続回数が移動回数の影響を受けるというのもあって、後者は具体的な方法が湧いてこない。作って思い通りに動く保証も無いし、汎用性の高さで言えば目標盤面を作る方法か。こちらはレイアウトによって何手動かす必要があるのか概算できるので方針も立てやすいし、サーバが直線状に並ぶので失敗してもリカバリーをかけやすい。とりあえず接続を考えずに動かすだけ動かして、移動を何回で打ち切るかを全探索しちゃえばなんとかならないかな。
次に目標盤面の形を決める。似た問題のMM128では、渦巻や、表面積を最大化したアメーバのような形が強かった。でも今回の問題では全マスにサーバがあるわけではなく、置かなくてもいい場所がある一方で、曲がる場所には必ずサーバを置かないといけない。なので疎な盤面に対しては角の設置のために過剰な移動を強いることになるかも？ということで、今回は曲がる回数を少なくする方針に決定。実装楽そうだしね。*2初動は多層渦巻、途中からは1色狙いは短冊の中央に串を刺した形、2色狙いは天井と床から棘を生やす形にした。
（使用位置を取捨選択したり調整したりができれば曲がる回数が多くても良いと思うが、良い感じに調整できる気がせず…）
実装
基本の動きは、以下の4つのフェーズ。
1. 目標盤面を作る
2. 目標盤面を目指して動かす
3. 交差点にサーバを動かす
4. サーバを接続してクラスタを作る
1. 目標盤面を作る
1色狙いと2色狙いをそれぞれ作る。縦縞を作って、1色なら真ん中、2色なら上下に横棒を刺す。横棒を一直線にしつつ間にも余計なサーバを入れないことで、「こことここが繋がらない」みたいな事故を避ける。5000点と1000点を半々で出すより4000点を安定させたい。
縦縞を横に何個ずらすかと使用色の組み合わせを全探索して、1色2色のそれぞれで初期盤面に近いものを採用する。
ちなみに使わない色は全部同じ扱い。使わない色のサーバを詰め込む場所はゴミ置き場と呼んでいた。
2. 目標盤面を目指して動かす
BFSで移動距離が近いものから貪欲に動かす。移動元と移動先のマッチングはサボる。
3. 交差点にサーバを動かす
貪欲に動かす。目的の色のサーバがあまりに遠いことがあるので、元々別の色のサーバがいる場合はそのままとし、ダイクストラでも別の色を持ってくる追加コストを距離5相当とした。
4. サーバを接続してクラスタを作る
まず横棒を接続したら、あとは大体貪欲にやる。直接接続できない場合は、1個まで他色のサーバを経由する。
ここまでが基本。
手数を節約したり、ちょうどいい解を探すために、いくつか追加のロジックがある。
移動回数を探索する
何回で移動を打ち切って接続に移るかを探索した。前半の移動はコスト1、後半はコスト3などの非効率なものになるので、コストが軽い移動が優先されることになる。
バグで接続の計算が重い時期があり、高速化のために移動回数は三分探索した。*3最序盤は盤面が整っていないので低スコア、最終盤は移動に手数を使いすぎるので低スコア、中央はちょうどいいので高スコアとして、概ね凸な関数になっていることを期待した。ただし完全に凸というわけではないので、候補が30個くらいに絞り込めたらあとは全探索する。提出スコアが0.1％低下した代わりに4倍速になったので、上手く機能してはいそう。
使わなかった位置をゴミ置き場に変換する
例えば左から一直線に[1-1-1-1-1 3 5 2 4]と1だけを繋いでいる場合、最後の1以降である3524は1がいるべきエリアに居座っていてもいい。実際の動作ではどかしてしまうので、最高スコアの解を求めた後に目標盤面を修正してどかさないようにして、再度計算する。この浮いた手数で点数上昇を狙う。
余計なサーバを取り除く
例えば[1-2-1]と直線で繋がっている場合、このまま繋ぐと2手かけて接続することになる。これを「2をどかして1と1を接続」に変換すると、2手のまま不純物を取り除いて得点を上げることができる。このどかした2が良い仕事をする可能性もあるため、処理としては2をどかして接続をやり直すとした。
目標盤面でなくても隣ならOK
使用したいサーバがゴミ置き場にいても、目標盤面にある同色のサーバと隣接していれば移動は必要ないとみなす。基本的にこの状態のサーバを目的地に動かすには2手以上かかるので、2手浮く計算になる。ちなみにもう1色の使用色の邪魔をする配置は駄目。
…という感じ。
最終的には、2色使用時は6000～7000点くらいが多いのかな。2色使用だと1手移動するやつを一部動かして終わりなので、4950 *2点は流石に遠そうでした。
やらなかったこと
他色サーバ位置を経由した移動
邪魔なサーバを隣にどかして通過すれば2手、そのサーバを戻すとしても3手で経由できる計算。多色だと欲しいサーバが閉じ込められていることもありこのロジックは欲しかった。実装時間切れ。
目標盤面の90度回転
サボり。あとは縦縞のレイアウトや高さを可変にするとかも。
位置のマッチング
速度が割とばらつくので、安全のため切った。N対Mのマッチングになりがちなので、こういうときは最小費用流が欲しくなる。
その他細かい調整
交差点に動かすときに他色サーバを置く追加コストを可変にして探索する、移動順や結合順をもっと検証する、などなど。
ローカルでベンチマーク
そこまでやりたくない気分のときもある。
使用したアルゴリズム
- BFS、ダイクストラ（経路探索）
- Dial's Algorithm（ダイクストラ高速化）
- 三分探索（移動打ち切り数探索）
- UnionFind（サーバ連結の管理）
- ハンガリアン法（使っていた時期もありました）
他の人の感想を見て
なんで皆焼いてるの？？？
何を食べればこれを焼いて解ける問題だと思えるの？？？
感想
NとKで性質が変わる問題でしたが、私の解法だとそこまで方針に違いは出なかったですね。もっと良いやり方はあるにせよ、同じ方針でも破綻はしないよという意味で。そういう意味では、手法の選択は成功と言えそうです。最小全域木を弄るのは無理無理。
4950点以降は打ち込むほど楽しいタイプのコンテストに見え、やりたいことは8割終えられたので満足です。
