TopCoder Open 2018 MarathonMatch Poland Lightning Round メモ

問題

 H \times Wの盤面が与えられる.それぞれのマスは領域に分かれている(領域には飛地もある).また,どのマスも5色以下の色で塗られている. このとき,領域に以下の制約を満たすように領域に色を塗る.

制約

  • 領域同士が辺で接している場合,それらの領域は違う色であること.
  • ただしなるべく少ない色を使うこと.
  • また,できるだけ元の色を保持できること.

1日目

問題を確認したつもりになる.色数を減らせばいい問題だと認識したが,まったく解法が思いつかない.
その日はほかに用事があったのでコードは全く書いていない.

2日目

とりあえずランダムに色を塗るプログラムを書く.
ただこれはめちゃくちゃ性能が悪くて,1時間回しても10色とかそこらへんの解しか出ない. 投げてみると100位付近….

3日目

「graph coloring local search」とか「graph coloring simulated annealing」とかで検索してみる.
お手軽そうな焼きなまし法のPDFを見つけたので実装.内容を簡単に下にまとめておく.正直これで本当に制約を満たす解が見つけるのか疑問だったが,動かしてみると普通に見つかって感動した. https://arxiv.org/abs/1712.00709

PDF に載ってる焼きなましの概要

  • 初めに使う色数を決めておく.( 大体どの問題も6,7色で落ち着いたので余裕をみて8色から試していった)
  • 頂点にランダムに色を割り振る(この時点ではColoringの制約に違反している).
  • 近傍解: 適当な頂点の色の変更で作る
  • 目的関数: 両端の頂点の色が同じ辺の数 (最小化)
  • 目的関数が0になればColoringできたことになる.

まず愚直に実装して投げてみると90位くらいだった.そのあとパラメータを見直して,6色で塗れる数が多くなると75位くらいにはなった.
この時点ではまだ,oldColorsとの差は考えていなかった.
彩色が終わったグラフに頂点の色を変える山登り(もちろんColoringの制約が壊れないように)で塗り替え数を少なくなるようにしたらまた順位が上がって70位付近.
そのあと塗り替え部分も焼きなましにしたり,高速化したりでprevが56位だった.

最終的な解法とExample

8色で塗れるか焼きなましを試す.塗れたら7,6色と試していく. もし焼きなましが時間内で終わりそうになかったら,残り時間は塗り替え数を少なくするための焼きなましに使う. ちなみにシード1から400では73%が6色で,他23%は7色で塗ることができた.
Example scores:
0) 700351.0
1) 730551.0
2) 608070.0
3) 721516.0
4) 602872.0
5) 604814.0
6) 612986.0
7) 611629.0
8) 604774.0
9) 606147.0

コンテスト終了後

Twitter見てて自分がスコアリングを全く理解していないことに気づいた.
rawスコアは100000*色数 + 塗り替えた色数で計算されて,自分はこれが最終スコアかと思っていた.
が,実際にはほかの人の解のうち最も色数 C_{min}が少ないものと塗り直し数 P_{min}が少ないものと自分の解で計算される \frac{C_{min}}{C_{your}} \times \frac{P_{min}}{P_{your}}がスコアとして使われる.
問題はしっかり読もう.ちなみに色数の焼きなましを5秒で打ち切って,残り5秒を塗り替え数を減らすようにした場合は下みたいな感じになりました. 6)は色が7色に増えてしまっていますが,塗り直し数が減ってるのでこっちのほうがいい解です. 時間を増やしても劇的に変化していないので,自分の実装した焼きなましだとあまり塗り直しは減らせてないみたいでした.
Example Scores:
0) 700351
1) 727464
2) 608070
3) 720114
4) 602663
5) 604814
6) 710964
7) 611585
8) 604747
9) 606147