TopCoder Marathon Match 100 - SameColorPairs メモ

問題

 H \times W (10 \leq H, W \leq 100)の盤面のそれぞれのセルに C (1 \leq C \leq 6)色のうちの一色のタイルが置かれている. 同じ色のタイルを2枚選んでその2枚のタイルの作る矩形の中に違う色のタイルがないときに2枚のタイルを除去できる. なるべく多くのタイルを除去せよ.
上位3名に賞金,50位以上だとTシャツがもらえる.

結果

prev: 32位
システス: 33位
無事にTシャツをゲットしました!!

思考過程と方針

選択肢が多すぎる & 盤面の評価どうする? → ビームサーチは難しそう.それなら焼きなましか → 操作の順番が重要なので簡単に近傍が作れなさそう.最適解はたくさんありそうなのでランダムでもある程度行けるのでは??という感じでランダムで行くことにしました.
適当にタイルを選んで消せるか試し,消せるタイルがなくなるまで試していく感じです.まず単純にこれを実装して投げるとまあまあいい感じでした.そこから定数倍高速化したりしました.
最後にもうこれ以上高速化できなさそうだったので,苦肉の策として数回に一回,そこまでのベストな解の後ろを少し戻して最後のほうだけランダムに探索するようにしました.これのおかげで0.3%くらいローカルで改善しました.
ちなみに上位の方たちは盤面を分割して焼きなまししていたみたいです.まだどういう感じだったのか完全に理解しきれていないので,コードが見られるようになったら見てみたいと思います.
5月にはTCOもあるので楽しみですね.