Topcoder MM128(TCO21 Regional) - BallSwaps 参加記録

TopcoderのMarathonMatch128に参加しました。

www.topcoder.com

問題はBallSwaps。良い感じに連結成分を作る問題でした。

事前テストは70人中7位。

地域毎の順位で賞金が出る大会なんですが、これで日本4位って魔境すぎませんか？

f:id:inani_waon:20210806030127p:plain — MM128 Seed2

問題

N*Nのグリッドがあり、各セル内に1つボールがある。ボールはC色ある。

隣接するボール同士を交換して、色毎に1つの連結成分になるようにせよ。

（その手数を少なくせよ）

考察

中間状態の評価が難しそう。

●●●●

こういう状態とか。反復横跳びが怖い。となると、青写真を作ってからそれを完成させる感じか。なんかMM123っぽい。

どんな青写真が良いか考える。移動数を最小化するためには、初期配置に近い青写真を作りたい。初期配置は各色のボールが多少の偏りはありつつ満遍なく散っている状態なので、そのような配置を取りつつ上手く連結できる図形にしたい。

蛇腹ボーダー

●●●●

これは上下に0～N手必要で、1ボールあたりN/2手かな。

単層渦巻

●●●●

計算しづらいけど、これも上下に各0～N/4手でN/2手くらいか？蛇腹ボーダーよりちょっと良い気がする？（実際は蛇腹ボーダーより有意に優位っぽい）

ブロック

●●●●

なんか良くない気がする。上下に各0～N/2手でN手？実測すればもうちょっと良い気がするけど…。

多層渦巻

●●●●●●

ド本命。部分的に見ればC個のブロック内で色交換するだけなのでC/2手。Nが大きくCが小さいケースほどこれが強くなる。ただ、NがCの倍は必要かな。NがCの倍数じゃないケースとか、生成ロジックが難しそう…。

江戸でペンキ塗りのアルバイトをした経験が生きた。

初期版は単層渦巻で決定。完成次第多層渦巻を作ったり、左右上下反転や回転、別パターンから最良を選ぶ感じかな。あとは色の順番によって違いが出そうだから、ハンガリアン法で二部マッチかな。ますますMM123っぽい。

実装

単層渦巻で57点。端から渦巻状に、一番近いものを持っていく。意外と良いスコア。

どのボールを目標地点に持っていくかをハンガリアン法で決めて、コストの目安にする。移動中に他のボールを巻き込んで盤面が変わるので、贅沢に1個ボールを動かす度にチェックする。また、コストの目安が出来たので、色の順番を全列挙する。Nが大きいと全て回らないので時間制限付き。移動経路のボールが移動するので厳密なスコアは出せないんだけど、大体上手く行くっぽい。これで77点。勝ったな（確信）

残り2色くらいになったとき明らかに無駄だなーという動きをしているんだけど、汚い解決策しか思いつかない。そういうので変なコーナーケースで沼にはまりたくないんだよね…。

多重渦巻は†Excel†でテンプレートを作って良い感じに加工することにした。82点。強くはなったんだけど、周囲の伸びが強くて追い付けない…。

最終日に晩御飯を食べながら10000件耐久テストを回すと、失敗しているケースを4件ほど発見。テンプレート加工時に孤立ボールが出てしまうらしい。UnionFindでチェックを入れて対応。せっかくなので、終盤に「実は完成してるけど青写真が完成するまで続けるぜ！」みたいなのを検出できるようにした。logだしハンガリアン法のN^3に比べたら全然重くない。

移動経路を踏み荒らすやつの改善が出来るか試行。既に青写真と同じ色のボールが乗っているところは避けるようにしてみる。微改善。移動により青写真と同じ色のボールを乗せられるなら優先通過するようにしてみる。悪化。なんで？ → これDFSだけでやってるのでキューの順番が狂ってる気がする。DPやダイクストラにすると多少違ったかも？

ついつい大きいケースを見てしまうんだけど、小さいケースも大切。時間余ってるしね。単層渦巻は左右・上下反転も試行するようにした。これでseed=1が10→8stepに。

あとはテンプレートを調整する感じで、81点で終了。やりたいことは大体やりきったかな。これで勝てなかった人には完敗。