blog2019-03-27MM109参加記MM109に参加したので参加記。provisionalでは2位でした。testが終わってからのせる(かも)です。無向グラフが与えられる(頂点数30~1000)。各辺には重みと価値が与えられており、重みの制限が与えられるので、その範囲内で辺を選択する。点対と価値のペアの集合も与えられており、選択した辺をたどってその点対が連結である場合それに対応する価値を得ることができる。(点対の価値の和)を最大化するように辺を選択せよ。読みたい人は下のリンクに飛んでください。TopCoder問題を見てからの思考回路*1大雑把編とりあえず、点対の価値の和をあげないとどうしようもなさそう。点対を結ぶとなるとdijkstraが自然そう。価値が大きい点対から順にdijkstra走らせるのは悪くないはず。綺麗な構成法なども思いつかないので、まぁビームサーチか焼きなましでしょう。ビームサーチ、状態うまく持つの大変だし、評価めっちゃ難しそう(というか僕がビームサーチまともに使ったことない)。点対を追加したり削除したりするとよさそう。構成するグラフは当然森になる(点対の価値に寄与しないものは後処理でやればいい)。複数の点対を結ぶ最小の木は各点対についてdijkstraを走らせても得られないことがある。dijkstraのときにランダムで辺を無視すりゃええ感じになるやろ(適当)。点対削除するんだけど、複数の点対で使われているパスがめっちゃ動きにくい(そのパスを使うすべての点対が消えないといけないため)。分岐のないパスを取り除いてからもう一度つなぎなおすということも楽にできることに気づく。てわけで上のようなことを適当にごちゃごちゃさせた焼きなましをした。コーナーケース編そこそこサイズが大きいときはまぁいいんだけど、小さいとき、少しミスっただけで割とスコアが削られる(相対評価で最大が小さいため)。小さいとき、とにかく色々試すのが大切。てわけで、サイズが小さいときは50回ぐらいめっちゃ適当に色々な構成をしてみて、一番よさそうな奴を見つけてから焼きなまし。前処理編グラフが与えられてるけど、これ無駄多くね。次数が2でどの点対にも含まれてない頂点は潰してよい。ある辺であって、その辺を使わないほうがよい場合はその辺を消してもいい。行き止まりになってるどの点対にも含まれてない頂点も消していい。あるけどまぁこんな感じ。その他編あとは高速化とチューニング。dijkstra周りがどうしてもボトルネックになる。ここは実装依存だし列挙してもあまり価値がないので省略。なんか実行するたびに答えがブレるところがあったから、焼きなましを1/2にして二回走らせてみるようにしてみたら、手元では少し良くなった。submitするとprovisionalでは少し悪くなった。怖かったけど、手元で1000回回したらそっちのほうがよかったので2回走らせるバージョンを投げた(まぁ誤差程度の差だけど)。testの結果は以下のような感じ。35360.0手元でのbestは以下のような感じ。検索はてなブログをはじめよう!gasinさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。