MM109参加記

　MM109に参加したので参加記。

　provisionalでは2位でした。
　ソースコードとか順位表とかはsystem testが終わってからのせる（かも）です。

問題概要

　無向グラフが与えられる（頂点数30~1000)。
　各辺には重みと価値が与えられており、重みの制限が与えられるので、その範囲内で辺を選択する。
　また、点対と価値のペアの集合も与えられており、選択した辺をたどってその点対が連結である場合それに対応する価値を得ることができる。
　(辺の価値の和) * (点対の価値の和)を最大化するように辺を選択せよ。

　ちゃんと読みたい人は下のリンクに飛んでください。
TopCoder

問題を見てからの思考回路*1

大雑把編

　とりあえず、点対の価値の和をあげないとどうしようもなさそう。
　点対を結ぶとなるとdijkstraが自然そう。
　とりあえず価値が大きい点対から順にdijkstra走らせるのは悪くないはず。
　綺麗な構成法なども思いつかないので、まぁビームサーチか焼きなましでしょう。
　ビームサーチ、状態うまく持つの大変だし、評価めっちゃ難しそう（というか僕がビームサーチまともに使ったことない）。
　焼きなましです。
　とりあえず点対を追加したり削除したりするとよさそう。
　まぁ構成するグラフは当然森になる（点対の価値に寄与しないものは後処理でやればいい）。
　複数の点対を結ぶ最小の木は各点対についてdijkstraを走らせても得られないことがある。
　dijkstraのときにランダムで辺を無視すりゃええ感じになるやろ（適当）。
　点対削除するんだけど、複数の点対で使われているパスがめっちゃ動きにくい（そのパスを使うすべての点対が消えないといけないため）。
　分岐のないパスを取り除いてからもう一度つなぎなおすということも楽にできることに気づく。
　てわけで上のようなことを適当にごちゃごちゃさせた焼きなましをした。

コーナーケース編

　そこそこサイズが大きいときはまぁいいんだけど、小さいとき、少しミスっただけで割とスコアが削られる（相対評価で最大が小さいため）。
　小さいとき、とにかく色々試すのが大切。
　てわけで、サイズが小さいときは50回ぐらいめっちゃ適当に色々な構成をしてみて、一番よさそうな奴を見つけてから焼きなまし。

前処理編

　グラフが与えられてるけど、これ無駄多くね。
　とりあえず、次数が2でどの点対にも含まれてない頂点は潰してよい。
　また、ある辺であって、その辺を使わないほうがよい場合はその辺を消してもいい。
　行き止まりになってるどの点対にも含まれてない頂点も消していい。
　もうちょっとあるけどまぁこんな感じ。

その他編

　あとは高速化とチューニング。
　dijkstra周りがどうしてもボトルネックになる。
　まぁここは実装依存だし列挙してもあまり価値がないので省略。
　だけどここが一番しんどい。
　
　なんか実行するたびに答えがブレるところがあったから、焼きなましを1/2にして二回走らせてみるようにしてみたら、手元では少し良くなった。
　submitするとprovisionalでは少し悪くなった。
　怖かったけど、手元で1000回回したらそっちのほうがよかったので2回走らせるバージョンを投げた（まぁ誤差程度の差だけど）。

成果物

example testの結果は以下のような感じ。
0) 2184.0
1) 1146251.0
2) 2525984.0
3) 10725.0
4) 284900.0
5) 38136.0
6) 782.0
7) 28152.0
8) 29346.0
9) 35360.0
手元でのbestは以下のような感じ。
0) 2184
1) 1155164
2) 2530422
3) 10725
4) 285418
5) 38136
6) 782
7) 28152
8) 29346
9) 35360

seed2で焼きなましがどんな感じになってるかのグラフ（その時点で持っている状態のスコア）

*1:すいすい書いていますが、実際にはかなり時間をかけてたどり着いています、あまり時系列に沿ってないです