マラソン参加記~MM135~
0．はじめに
こんにちは、tardigradeです。本記事ではMM135のmy解法をまとめています。コンテスト中の考察ノートも兼ねているので、多少読みにくい箇所もあるかと思いますが、温かい目で見ていただけると嬉しいです。
自己紹介
名前は「tardigrade(たーでぃぐれいど)」です。「くまむし」の英訳から来ているので、「くまむし」や「くま」と呼ばれることもあります。2022/04/14の時点でのMMのレートは1141です。
1．問題把握
- なるべく多くの島を橋で結びたい
- 橋は縦横にかける(間に島を挟めない)
- 各島に接続できる橋の本数は決まっており、その本数だけ過不足なく接続するか、まったく接続しないかのどちらか
- 橋は多重にしてもよいが制限あり
2．最初に考えたこと
- 島をノードとしたグラフを作れそう
- 初期解を作った後で「橋を外して別の島に付け直す」という操作が重そう
- 工夫なしに↑の操作をすると容易に局所解に陥りそうな気がする
- とりあえず山登り法まで実装したい
3．1,2回目の提出
整理のために構造体や関数を色々作ります。
交差判定は、vectorで辺を管理して判定のたびに全探索する方法を取りました。効率が悪い気もしますが、いい実装方法がぱっと思いつきません。
dfsでスコアの計算をしながら橋を架けることにしました。「右、左、下、上」の順で周りの島を見て、架けられるだけめいいっぱい架けます。
現状の欠点として
- 判定の都合上、サイクルが作れない
- 見る順番が一定でつまらない
などが挙げられます。
最初なのであまり変なことはせずに、dfsをする頂点の順番を時間いっぱい乱択する解法を書きます。
1回目にこれを提出し、すぐにバグに気づいて2回目を提出しました。
この時点での相対スコアは31くらいで、8位/20でした(過疎…)。
4．3回目の提出
ビジュアライザを眺めていると、調べなくてもよい島があることに気づきました。例えば Bi = 12 かつ C = 2 のとき、この島iにはどう頑張っても橋を架けることができません(最大でも8本しか橋が架けられないため)。こういう島は最初から無視するようにするとよさそうです。
また、先ほどは完全な乱択をしていましたが、「改善なら更新・改悪ならそのまま」にすることで、山登りっぽい形にしてみます(これで効果的な近傍を取れているのかはよくわかりません)。
さらに、スコアの計算方法を勘違いしていたことにここで気づきました。直します。
これだけやればだいぶ改善するだろうと思いきや、手元(seed1～100)では微妙に改悪でした。悲しいですがとりあえず投げてみます。
ちょっとだけ改善され、相対スコアは29.24、順位は16位/29になりました。
5．4回目の提出
実行時間を5倍くらいにして、高速化による改善の余地があるかを確認しました。ありませんでした。
局所解に陥っている感じがしたので、安直に多点スタートにしてみます。途中でまたしてもバグに気づき、これを直しました。このバグが山登りをするうえでかなり致命的なもので、いい感じにスコアが伸びます。投げます。
相対スコアは34くらいで、順位は19位/35になりました。
6．5,6回目の提出
適当に定数倍高速化をしてお終い。ほんとは焼き鈍し法を実装したかったのですが、どうやってもスコアが改悪してしまい断念。どうやってパラメータを調整したらいいのかが謎で、実戦では未だに使えてない…。
7．まとめ
システス前暫定26位でした。
「山登りまでやってそれで終わり」っていうムーブを毎回しているような気がするし、成長がないですね。
「ある範囲の橋を破壊して再構築する」みたいなこともしてみたかったけど、学業が忙しすぎた…。上位勢の解法を見てみたいです。
