MM118 参加ログ
MM118（5/21~5/28）の参加記ログです。
思ったことを書きなぐっただけでまとまってないです
5/22
問題文を読んだ。
ダンサーが何人かいると言っているが区間ごとに分けて考えれば良さそう。つまり「始点・終点・最大ステップ数のタプルが複数与えられる」という問題設定と考えて基本的にはいいはず。
衝突とかも考えなくて良いので探索しやすい性質をしている反面、目的が連結成分数の最小化なのでつらくもある。
グリッド上のパス上の最適化は"UL"<->"LU"とか"LR"<->""とかを遷移とする探索をするのが一般的だと思うし今回もそれでいいのではと思っている。というか他に思い付かん。
連結成分に関する計算が重くなりそうだけどそれなりに回数回るでしょと思っている。ダイコネとか使えるけどさすがこういうのは愚直が速いんじゃないかな
隣り合う同色の数を最大化する焼きなましであれば高速に回るはずだしそっちで初期解作ってという感じかな
この手の遷移の問題点として状態から状態への距離が遠くなりがちというのがあるのでそこに気を付けて探索を設計していくことになりそう
パスを丸ごと変えるという遷移もなくはないけど今回は無理そう
とりあえず、パスを局所的に変える遷移で①真の目的関数と②隣り合う同色最大化の二つを組む。
5/23
考えてたやつを実装した。思ってた以上に①がうまく回らない。代わりに②はうまくいく。というか②の結果から①に移行すると解が悪くなったまま戻ってこないとかある。
ちなみにダイコネで殴ってる（実装楽だったので）。おそらく愚直の方が速い（少なくともNが小さいケースでは）のであとで実装する。
適当に100ケース回してみた。わりとスコア下界を達成しているケースもそれなりにある。順位表を見ると1位が75、2位が60とかでやばさを感じる。rawScore=1が可能なケースでrawScore=2を出したらそれだけでそのケースの得点は0.5なので、こういうケースがかなり重要になってくる。
出力をみると、真ん中の方にでかい連結成分があって周囲が全く色のそろってない状態になっているケースとかがある。移動の軌跡がマス全体を一様に被覆するようにできると良いのかもしれない。
下界を達成できるケースは全マスを一色にするのを目的関数に入れるのもありかもしれない。
f0 = (D*S)/(N*N*C)が問題の難易度の指標の一つになりそう（各マスで平均何順するか。大きいほど簡単）。ハイパラ調整に使えるかも
全マス一色にする焼きなましを書いた。f0>5のケースで使えそう？ただしほんの数パーセントの違い。-> f0>3でも使えそう
初期化を考える。外側が探索されないがちなので、外側に近いところを通るようにするパターンと、遷移の種類を多くとれるようにギザギザに進ませるパターンを用意。f0>1は前者、それ以外は後者という感じにしてみた。
初期化を複数作って初めて気づいたけど、初期解からあまり動けていないようだ（出力からどちらの初期化を使ったかが判別できる程度）。
隣接同色最大化の焼きなましで外側ほどスコアを高くするようにしたりしてみた。数パーセント改善する程度
Cが偶数でscore=1を狙う場合、パリティに注意しないと不可能になるケースがある。どの色にそろえに行くかは事前に決める。
微妙な改善しかできてないので、根本的に探索の方法を考え直さないといけない気がするけどアイディアがない…
一旦現状を纏める。
基本は経路を局所的に変更する遷移で焼きなまし。遷移は具体的に、"LR"<->"", "UL"<->"LU", "LR"<->"RL", "LR"<->"UD", "LUR"<->"U"とこれらを回転、反転したもの。操作列は双方向連結リストで持つ。遷移可能な箇所は追加削除ランダム取得がO(1)のsetで管理する。
目的関数として、1.真のスコア、2.隣接同色数最大化、3.特定の一色に染める の3つを用意。score=1が狙えるくらいであれば3を、そうでなければ2で探索し、最後に1で探索する。
5/24
時間取れず
5/25
ちょっとだけやる。
とりあえずダイコネの部分を愚直に書き直した。速くなった。
いくつか実装案はあるが方向性を定めるためいったんTL3秒にして提出
->スコア62で4位、1位のスコアは69。TL9秒にすれば狙える範囲だと思う。とりあえず現状では方針を大きく外してはなさそう。時間もとれなさそうなので、細かい調整に入っていいかも知れない。
とりあえず盤面を一色に染める焼きなましの5回リスタートを組んだ。->1パーセントだけ改善
5/26
時間取れず
5/27
終了が28日午前2時なので実質最終日
時間がないので細かい調整に入る。
温度スケジュールとか焼きなましの種類・初期化の方法の選択基準をちゃんと調整した。放置してたハイパラを適当に調節した。ローカルで10％くらい上がった。
順位表のスコアを見ると、1回目の自分の提出が53に対して1位が75とか。
とりあえず提出->同じタイミングで上位2人が提出してて位置が分からん。おそらく1位まであと10％くらいだと思う。->提出結果3位で1位まで12%とかだった。いずれにせよ1位は無理。
しばらくハイパラ調整してたけどもうこれ以上は上がりそうにない。結局雑に焼きなましを書いて終わるいつものパターンになってしまった…
周りも上がってくるだろうし上位に残れるか険しい
