TCO18 MM R1 RoadsAndJunctions 参加記録

問題文：

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=17153&pm=14907

順位表：

https://community.topcoder.com/longcontest/?module=ViewStandings&rd=17153

問題概要

平面上にN個の点が与えられる。一点当たりコストCで最大2N個の点を加えることができる（位置を重複させてはならない）。新たに加えた点は、それぞれ確率Pで消滅する。（最終的に得られる点群の最小全域木のコスト）＋C×（追加した点の数）をraw scoreとし、(best/your)^2を最大化する。

やったこと

点をばらまき最小全域木をもとめる。次数が２以下のものを取り除き、木構造を固定した状態で山登りをする。ないほうがよさそうな点を削除し、評価値を求める。

以上までを１遷移として焼きなました。

同じ位置に点を重複させた方がいいこともあるので１つずらすなどして配置した。

評価関数は、

（すべての点を使った時の最小全域木のコスト）＋  各点ごとの、(C×(その位置に置く点の数)＋(P^(その位置に置く点の数))×(消滅したときの最小全域木のコストの増量))の和　　

とした（各点ごとに独立に考えても真の期待値とそんなにずれないという仮定を置いた）。

ローカルでの評価は、モンテカルロ法によってE(1/rawscore^2)を求めた。

感想、反省

ローカルの評価がずっとバグっていて期間のほとんどを無駄にした。それ以外にもいろいろバグが多かった。そもそも順位表があまり信用できないこともあってスコアが落ちても致命的なバグがあることに気づけなかった。最終結果はともかく全期間通じて動きが過去最悪だった。結局最初に書いたものを少し改善したものを最終提出とした。

やはりコードはきれいに書くべきだ。