yukicoder No.5002 stick xor
https://yukicoder.me/problems/no/5002yukicoder.me
成績
51,325点 (4位)
最終的な解法
各長方形を{向き(y軸方向 or x軸方向),左上の点のy座標,左上の点のx座標}の3整数で表した.従って動かせる値は3k個となる.
3k個の整数をランダムに与えることで長方形の初期配置を行い,焼きなまし法で改善した.遷移は以下の3タイプを1/3ずつの確率で行った.
1長方形の軸方向移動
長方形の長い方向に沿って1マス移動させる.更新O(1).
平行な2長方形間の長さの交換
平行で,同じ行(または列)上にない2長方形A,Bの長さを交換する(実装上は長方形の位置を入れ替える).長方形Xの長さをlen(X)とすれば,更新O(|len(A)-len(B)|). 平行・同一行でないという条件をつけているのは,2長方形が重なりを持たないようにして更新を単純にするため.
1長方形のランダム移動
1長方形Xを取り除き,ランダムな配置で置き直す.更新O(len(X)).
参加記
5/25
参加宣言.なお5/27のマラソン勉強会はこの時点で補欠であり,参加できると思っていなかった.
ゆきこーだーでまらそんのべんきょうをするぞー
— Hoikoro (@Hoi_koroo) 2018年5月25日
勉強ということで,レプリカ交換法を焼きなまし法に使ってみることをテーマとした.
ゆきマラソンは実装したいものがあるがスコアが出るかは不明
— Hoikoro (@Hoi_koroo) 2018年5月25日
上記3種類の遷移によって影響を受けるマスの数を考えると,遷移の「大きさ」は軸方向移動<長さ交換<ランダム移動 となりそう.そこで以下の方針を考えた.
- 3つのレプリカを用意する
- T1<T2<T3となる3つの温度をそれぞれに与え,徐々に冷却する.
- 温度T1となっているレプリカは軸方向移動のみの遷移,T2のレプリカは長さ交換のみの遷移,T3はランダム移動のみを行って焼きなます
- 定期的にスコア差によって決まる確率に従ってレプリカの交換を行う
5/27
マラソン勉強会に参加した. 帰宅後,ランダム移動のみの遷移で焼きなましを書いた.4万点.
勉強の成果をいかんなく発揮して4万点に達したので寝よう…
— Hoikoro (@Hoi_koroo) 2018年5月27日
5/28
上記のレプリカ交換法を実装した. 49,669点. その後はビット演算を利用して高速化したり,レプリカ交換法をやめて普通の焼きなましに変えるなどの調整のみ行った.
通常の焼きなましに変えた時点で51,089点まで上昇し,暫定トップに. レプリカ交換は実は足を引っ張っていたらしい.
別作業の合間にyukicoder MM の調整を続けていたら51kまで上がった記念 pic.twitter.com/zui3Wx4vN4
— Hoikoro (@Hoi_koroo) 2018年5月28日
また,長さ交換の遷移を除き,軸方向移動とランダム移動のみの遷移で焼きなましを行ったところ,ローカルの32テストケースで42000点ぐらいしか得られなかった.長さ交換遷移が有効そうだとわかった.
5/29
温度調整のみ行った.残り秒数をtとして
- 変更前:
- 変更後:
これで51,325点.
yukicoder, 6/1までとなるとこれで打ち止めかも.51325点
— Hoikoro (@Hoi_koroo) 2018年5月29日
5/31
6/1はマラソンに取り組めなさそうなのでこの記事を書き,予約投稿とした.
感想
- 長さ交換遷移のところを長さiと長さ(i+1)の長方形の交換とするのはよりよい遷移な感じがする.
- 貪欲で5万点,強すぎる
- マラソン勉強会の参加記も書く