olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

北大&日立MMその1

1日目
King's Graphはどうでもいいので、2S*2S四方のフィールドに元のグラフの頂点を乗せていくことにする。
(King's Graphへの変換後に辺が伸びているかはチェビシェフ距離が1か否かで判定できる)
とりあえず愚直貪欲を書いてみようと思って、頂点0をフィールドの中央に置いた後、一番スコアの伸びるものを貪欲に配置していくことにした。
ここまでで153329点
時間の許す限り開始点を変えつつ、より重い辺がたくさん伸びている頂点から回すと155626点
ランダム2点swapを実装し、156150点
2点swapを全探索に変更しつつ高速化をして156658点
軽いケースで初期解の探索に時間をかけるようにすると156716点
この時点では3位狙えるんじゃね!?みたいに思っていた。
二日目
全探索3点swapをバグらせつつも書ききり157037点
全探索4点swapを実装すると同時に、2点swap~4点swapを関数化、ここで3,4点swapをバグらせる。が、スコア更新し157048点
全探索5点swapも実装したが効果がなさそうなので没に
三日目
方針が降ってこなくてお掃除をしていた。
1点moveを実装していないことに気づき1点ムーブを実装し157334点
moveとかswapの順番をいろいろいじってたら157483点
四日目
前日に引き続きいじっていたら157553点
そろそろ頭打ちだなあと思い始めたので、初期解の改善に取り組む。
配置していくにあたって共通の隣接ノードを持つ頂点同士を隣り合わせるように変更を加えると157599点
ずっとこれをいじる。
五日目
前日に引き続きいじっていたが芳しくない結果だったのでやる気を失いかける。
こどげに逃げようかな~とか考えていると、今の方針が特に意味のないものであることをゆる~く説明できるようになったので今の方針を捨てることを決意。
コードをグッと睨むと定数倍重くするだけ(約20倍)で初期解の探索時に深さ2の全探索を行えることに気づく。
六日目
ようやく深さ2の全探索の実装を終え、158413点。
すると4点swapがお役御免になったので4点swapに別れを告げる。
3点swapまでは最悪ケースでも約3000msで行えるので初期解の探索にもう少し時間をかけるようにすると158562点。
ケースハック(?)を試み始める(ア)
七日目
ひたすらケースのNの特定作業を行う。
あと、一番最初に配置するノードはどれがいいのか調べると、やはりより重い辺がたくさん伸びてる辺を最初に置くのがいい可能性が高いことが判明する。
N=3とN=7で全探索しようかな~とか考えていたけどすでに最適解が出ていた。
八日目
全ケースのNを特定するもシステスらしくて悲しいね
長さ3の全探索を実装しようとしていたけど場合分けが半端なくてあきらめた。
九日目
初日に捨てたビームサーチが案外うまくいくのでは!?みたいに思ったので実装を始める。
全然ダメだったので方針を捨てる。と同時に案が尽きたので終了
十日目
なんやかんやでMM復活
長さ3全探索の実装を再開。
十一日目
前日の続き
十二日目
前日の続き
方針を変えないまま実装の方針を変えることにする。
十三日目
実装成功するも何故かスコア落ちる。
さらに実装方針を変更する。

 

REが出て80位まで落ちた…悲しい…

よく考えたら焼き鈍しの問題なのに方針捨てたのはまずかったので次回以降気を付けような👊