Hoi_koro memo

Editorialと異なる解法をしたら更新するblog

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). f:id:hiko3r:20180530235250j:plain

平行な2長方形間の長さの交換

平行で,同じ行(または列)上にない2長方形A,Bの長さを交換する(実装上は長方形の位置を入れ替える).長方形Xの長さをlen(X)とすれば,更新O(|len(A)-len(B)|). 平行・同一行でないという条件をつけているのは,2長方形が重なりを持たないようにして更新を単純にするため. f:id:hiko3r:20180530235254j:plain

1長方形のランダム移動

1長方形Xを取り除き,ランダムな配置で置き直す.更新O(len(X)).

参加記

5/25

参加宣言.なお5/27のマラソン勉強会はこの時点で補欠であり,参加できると思っていなかった.

勉強ということで,レプリカ交換法を焼きなまし法に使ってみることをテーマとした.

上記3種類の遷移によって影響を受けるマスの数を考えると,遷移の「大きさ」は軸方向移動<長さ交換<ランダム移動 となりそう.そこで以下の方針を考えた.

  • 3つのレプリカを用意する
  • T1<T2<T3となる3つの温度をそれぞれに与え,徐々に冷却する.
  • 温度T1となっているレプリカは軸方向移動のみの遷移,T2のレプリカは長さ交換のみの遷移,T3はランダム移動のみを行って焼きなます
  • 定期的にスコア差によって決まる確率に従ってレプリカの交換を行う
5/27

ラソン勉強会に参加した. 帰宅後,ランダム移動のみの遷移で焼きなましを書いた.4万点.

5/28

上記のレプリカ交換法を実装した. 49,669点. その後はビット演算を利用して高速化したり,レプリカ交換法をやめて普通の焼きなましに変えるなどの調整のみ行った.

通常の焼きなましに変えた時点で51,089点まで上昇し,暫定トップに. レプリカ交換は実は足を引っ張っていたらしい.

また,長さ交換の遷移を除き,軸方向移動とランダム移動のみの遷移で焼きなましを行ったところ,ローカルの32テストケースで42000点ぐらいしか得られなかった.長さ交換遷移が有効そうだとわかった.

5/29

温度調整のみ行った.残り秒数をtとして

これで51,325点.

5/31

6/1はマラソンに取り組めなさそうなのでこの記事を書き,予約投稿とした.

感想

  • 長さ交換遷移のところを長さiと長さ(i+1)の長方形の交換とするのはよりよい遷移な感じがする.
  • 貪欲で5万点,強すぎる
  • ラソン勉強会の参加記も書く