TUPC2023 D Shift Puzzle
問題概要
白黒のグリッド S から T へ、以下の操作を$ N^3回以下でやってください
行を選んで右にshift
列を選んで下にshift
$ 2 \le N \le 80
自分の解法
$ O(N^2)手でやった
S → 標準形 と 標準形 → T をやる
標準形：黒を左上に集める（ただし右端の列は空けておく）
黒の方が少ないなら白は $ N個以上あるので右端を空けておける
（黒の方が多ければ反転させればいい）
まずは各行が（右端を除いて）単色になるようにする
半端は$ N-1個未満なので右端の列に押し付けられる
具体的な操作
1. 黒にしたい行について、右端が黒かつ右端以外に白があるなら行shiftする
2. 白にしたい行についても同様
3. 右端を列shiftし、1. に戻る
操作回数
1.の回数：（行ごとに）合計高々 $ N-1
2.の回数：（行ごとに）合計高々 $ N-1
3.の回数：多分合計高々$ N^2ぐらい（簡潔な見積もり方思いつかなかった）
その後、右端列の半端を一番上の白行に押し付ける（高々$ 2N回）
おまけ
グリッドに順列が書かれてて、上下左右shiftが出来る版