yukicoder No.5002 stick xor
問題
NxNの2次元グリッドが与えられ、各セルは白または黒で塗られている。
このグリッドに対して、以下の操作をK回行う。
i回目の操作では、グリッド内の1xL[i]またはL[i]x1の長方形セルに対して白黒を反転させることができる。
スコアを「(最終状態でのグリッドでの白のセル数) - (最初のグリッドの状態での白のセル数)」とするとき、これを最大化せよ。
- N = 60
- K = 500
- 1 <= L[i] <= 25
最終的に提出したアプローチ
- K個を、順番に、全セルの中で評価値が一番高いところに置いていく
- 評価値は、白にできるマスなら+1点、黒にするけど、その両端が黒なら+0.5点、そうじゃない黒にする場合は-10点
- 次に、適当な場所に長方形セルを動かして良くなるなら採用する山登りを時間いっぱいまで行う
振り返り
初日
制約が1秒しかないので、「評価関数を作って一番評価値がいいところに置いていくgreedy」がよいのでは？と思い実装。
開始1時間ちょいぐらいで、これが最初にしては良いスコア(40,769点)だったので一旦提出。(最終提出の前半部分の方法)
焼きなまし
よくよく考えてみると、時間は短いけど、長方形セルがあまり大きくないので、それを動かすような近傍である程度の回数回せるのでは？と思い、ランダム初期配置＋適当なセルに移動してみる焼きなましを実装。
ただ、やってみると1秒ぐらいでは数百万回程度しか回らず、提出してみるも40,307点。
他の手法を考える
上位陣が50000点近くを出しているので、何か別アプローチがよいのかなと思ってしまったため、マッチング問題にできないか？やgreedy、ビームサーチ、グリッドの切り方など考えてみるも、うまくいかず。
最終提出
結局、良い初期状態から温度を下げた焼きなまし(実質山登り)が現状一番よかったので、初日のアプローチ＋山登り(温度を下げた焼きなまし)のコードで最終提出。
反省
近傍の作り方で焼きなましは大きく性能が違うので、そこらへんの違いを強く意識したい。。。
今回やってしまった「長方形をランダムな場所に移動」近傍は、後半のほとんど白が多い盤面では大きく悪化させるケースが多く、よい近傍とはいえなかった。
参加されてた方の感想戦やブログを参考にメモしておくと、今回有効な近傍そうだったのは
- 位置を1ずらす
- 長さが違う2つの長方形を入れ替える(近い長さ、長さが1違うもの同士)
- 長さLの長方形をL=la+lbと見なして、それと交換
- 再配置するにしても、greedyに良い配置を見つけてそれを近傍とする
変化量が小さい近傍の方がよさそうで、できれば1や2だけ変化させられる近傍が作れないか考えたい。
それ以外にも、
- 長さが短いものは直接的な改善に使えるので、取っておいて最後に配置
などは気づけるようにしたい。
あと、焼きなましでなく、探索で高スコア出している方もいてすごい。
