ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

TopCoder Marathon Match 118 DanceFloor 参加記

TopCoder プログラミング 競技プログラミング マラソンコンテスト

Topcoder

f:id:betrue12:20200603004944p:plain

初めてのTopCoderマラソンマッチ。34位/68人とちょうど真ん中の成績でした。

問題概要

f:id:betrue12:20200528114637p:plain

N\times N のグリッドの各マスが C 色のうちいずれかで塗られている。 D 人のダンサーがいて、 S 単位時間かけてグリッド上を移動する。このとき各マスが1回踏まれるたびに、周期 C で色が変化する。色変化のローテーションはマスごとに異なる。

各ダンサーについて、「ある時刻にこのマスにいなければいけない」という制約条件がいくつか与えられる。同一ダンサーの、時系列で見て隣り合う2つの制約条件を両方満たすことができること（つまり、指定時刻の差が指定マス間のマンハッタン距離以下であること）は保証される。

全てのダンサーの移動が完了したグリッドにおいて、各色それぞれの連結成分の個数を数える。色 c の連結成分の個数が a_{c} であるとき、 \sum_{c}a_{c}^{2} がスコアとなる。

スコアが小さくなるようなダンサーの移動経路を出力せよ。

方針

焼きなましを書きました。

指定時刻にダンサーがいる場所は決まっているので、全ての経路は隣り合う指定条件の間を移動する小経路に分割できて、これらは独立に決めることができます。なのでまずこれをバラします。

初期解

小経路を順番に決めていきました。このときは連結成分ではなく「同じ色が隣り合っているところ」がなるべく多くなるような貪欲を書きました。

近傍の取り方

まず小経路を1つ選び、その中で差が5以下の2つの時刻を選び、その両時刻について移動方向をスワップしました。

近傍を取る前の解について、各マスを踏んだ合計回数と各小経路で踏むマスを全て記憶しているので、移動方向のスワップであればその間で踏んでいた/新しく踏むマスの回数を差分計算するだけで済みます。

スコアの計算

Union-Findを用いました。

Union-Findを初期化して全マスを計算し直す方法と、差分で更新する方法の2つを考えました。差分更新は近傍を取る前の解の状態をUnion-Findに残しておいて、

  1. 暫定解において各連結成分がどのマスを含んでいるかを予め持っておき、踏んだ回数に変更があるマスと同じ連結成分に属しているマスだけを抜き出す。
  2. それらのマスの連結状態を全てリセットし、連結成分の個数も修正する。
  3. それらのマスの4近傍を見て、同じ色なら連結する操作を行い、連結成分の個数を適切に減らす。

みたいなことをするとできて、解を採用しない時のロールバックはUnion-Findの経路圧縮を捨てて変更履歴を持っておくと可能です。

ただし盤面が小さいときや色数が少ない時は全計算のほうが早かったので、入力によってどちらを使うかを切り替えました。 C \gt 2 かつ N \gt 15 のときに差分更新をしています。

マージンを余らせて最後に埋める

初期解を作る時に各小経路のマージン（最短移動に比べて余分に移動できる回数）を使わないようにして、焼きなましをしたあとにそれらのマージンを利用して連結成分を減らせるところを探す、というアイデアを考えました。

実際にビジュアライザで見た時に1マスだけで孤立しているような部分があり、ピンポイントで消せる可能性があると思ったからです。

実際に試すと色数が多いときにはスコアの減少に寄与し、色数が少ないときにはそれよりも初期解にマージンを使ったほうが良い結果になりました。この方法は C \gt 4 の時のみ使っています。

初期解からやり直す

自作ビジュアライザ（後述）で焼きなましの過程を見ていると、特に問題のサイズが小さいときには焼きなましの序盤で盤面が完全に様変わりしていてほとんど意味をなしていないことに、最終日の夜に（！？）気づきました。

パラメータ調整してもあまり良い感じにならなかったので、単純に問題のサイズが小さい（具体的には初期解のスコアが小さい）時には時間を等分して何度か初期解からやり直すという修正をしました。

例えば N=11, C=4 とかの小さいケース（seed 7）でスコア7じゃなくて4や3を引ける確率が上がる、程度の効果はあったと思います。

最終提出に盛り込んだ内容は以上です。

自作ビジュアライザ

公式ビジュアライザは最後の盤面の状態を見られる点では有用でしたが、私がコンテスト中に考えていた範囲ではダンサーの移動経路を見てもあまり嬉しくありませんでした。それよりは焼きなましで推移していく盤面の様子が見たかったので自作しました。

時間で区切ってその時の解をファイル出力しておき、Pythonとmatplotlibで描画しています。

感想戦を経て

Twitterでの感想戦を見て、

  • 連結成分の代わりに、違う色が隣り合っているところを最小化するようにして差分計算を爆速にする
  • 通る機会の少ない外周に孤立点が残りがちなので、経路を外側に散らせるように初期解や評価値を工夫する

の2点がキモだと思いました。初期解は隣り合う色だけを見て構成していたので、そのまま焼きなましを回すのは思い付けても良かった…

スコアが同じでも良い（将来性が高い）状態と悪い状態の差はあるはずで、そこをなんとか区別できるような評価関数を見つけようとしましたが、上手くいきませんでした。

コンテスト中は何をしたらいいのか全然分からなくて細かい高速化やヒューリスティックをちまちま試していましたが、終わってみればもう少し根本的になんとかできたな、という感想です。

結果は振るわなかったですがマラソンも楽しいですね。AtCoderでも今後マラソンコンテストが増える気配がありますし、TopCoderのMarathon Matchもまた機会があれば参加しようと思います。