TCO18 MM Lightning Round Map Recoloring 参加記録

問題文：

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17149&pm=14893

順位表：

https://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=17149

最終結果3位でした。

問題概要

２次元グリッドがNR個の領域に分けられている。領域には飛び地もあり得る。また、各マスには色が塗られている。同じ領域に属するマスが同じ色で塗られ、隣り合う領域に異なる色が塗られるように色を塗り替えるとき、（使った色の数）×（色を塗り替えたマスの数）を最小化せよ。

考えたこと

色を最初に固定した。validな解を見つけるため同色隣接領域のペアの数を目的関数とする焼きなましを書いた。ほとんどのケースで６色解が見つかったが、７色使った方がいいケースもあった。解が得られたら、ランダムに一部の色の割り当てを変え、再度解を見つけるための焼きなましをした。得られた解は塗り替えマス数で評価し、もし解が悪くなるなら、前に得られた解に戻した。この部分にも焼きなましの遷移式を用いた。

反省

6色か7色かの判断を適当にやりすぎた。ちゃんと探索してやるべきだった。forumの統計によると、１位、２位に比べて６色でやりすぎらしい。

色を変えるたびに隣接する同色の領域の色を消し、色のついてない領域の数で焼きなます様な方法もあった。その方がよさそうに思える。

validな解を探す焼きなましの遷移において、塗り替えコストの情報を使っていないの点が良くなかった。

invalidな状態を許し、同色隣接領域を禁止する条件をペナルティで表現する方法もあった。コンテスト中考えたがとてもうまく気がしなかったので試してもいなかった。