■

TopCoder Marathon Match 82 参加レポ

開催期間:
12/8くらい？~12/20
問題概要
N*Nのグリッドとpenaltyが与えられる。
各マスは0~4の色で塗られているか、塗られていないかである。これに塗り足して（あるマスを複数の色で塗ることが許される）、どの色もつながっているようにせよ。
全てのマスを全ての色で塗るのが自明な解である。あなたの仕事は次の式で計算されるスコアをできるだけ小さくすることである。
スコア　＝　各マスのスコアの合計
あるマスのスコア　＝　n + n * (n - 1) * penalty where n = そのマスが塗られている色の数

スクリーンショット。(少し色が違うマスは、最初から塗られていたマス）

雑感
マラソンマッチには二度目の参加。
暫定約75万点(相対得点なので、トップの選手の100/75倍のスコアということ…のはず）。コード書いてたのは３日ほど。

とにかく時間がなく（なぜ参加したし…）、冷静に考察する余裕はなかった。でも時間があっても点数伸びるかどうかは閃きに依存しそうな感じ。あと実装力が追いつくかも怪しい。悔しい。
まあしかし冷静に考えるとよくも悪くもないくらいのスコアだとは思う。
黄色なれるかなぁ。厳しそう。

私の解法
解を作っては少し崩してまた作る、というのを延々と繰り返すというもの。
解を作る方法は、「各連結成分から同時にダイクストラをして、一番最初に同じ色かつ違う連結成分にたどり着いたものを、そのパスでつなぐ」を繰り返す。

あと、端の方は大抵遠回りし得なので、そうなるようにちょっとハックしてある。

考察
これでそれっぽい解が得られる自信はあったが、良い解が得られる気は全くしない（すごくラッキーだと、たまたま得られるだけ）ので、方針死んでると思われる。

局所改善にもなっていない。