AT_masters_qual_a Smoothing by Swaps

[problemUrl]: https://atcoder.jp/contests/masters-qual/tasks/masters_qual_a $ N\times\ N $ マスの盤面がある。 一番左上のマスの座標を $ (0,0) $ とし、そこから下方向に $ i $ マス、右方向に $ j $ マス進んだ先のマスの座標を $ (i,j) $ とする。 $ N\times\ N $ マスの外周は壁で囲われており、マス間にも壁がある場合がある。 辺を共有する2マスは、間に壁がない時に「隣接マス」であると定義する。(13:15に追記) 各マス $ (i,j) $ には $ 1 $ から $ N^2 $ の数字 $ a_{(i,j)} $ がそれぞれ1つずつ書かれている。 高橋君と青木君の二人は、グリッド上の好きな初期位置からスタートし、以下の一連の行動を最大で $ 4\ N^2 $ 回行う。 1. 高橋君と青木君の現在位置に書かれている数字を交換したいならば交換する。 2. 高橋君は自身の現在位置に隣接するマスへ移動したいならば移動する。 3. 青木君は自身の現在位置に隣接するマスへ移動したいならば移動する。 一連の行動は $ 1\rightarrow\ 2\rightarrow\ 3 $ の順で行われ、全体で1回の行動とみなす。 数字を交換せずに隣接マスへ移動してもよいし、数字の交換後に移動せず同じ位置に留まっても良い。 二人の現在位置が同じマスとなっても構わない。 最終的に隣接するマス間の数字が出来るだけ近くなるように二人の行動を決定して欲しい。

入力は以下の形式で標準入力から与えられる。 > $ t $ $ N $ $ v_{0,0}\ \cdots\ v_{0,N-2} $ $ \vdots $ $ v_{N-1,0}\ \cdots\ v_{N-1,N-2} $ $ h_{0,0}\cdots\ h_{0,N-1} $ $ \vdots $ $ h_{N-2,0}\ \cdots\ h_{N-2,N-1} $ $ a_{0,0} $ $ \cdots $ $ a_{0,N-1} $ $ \vdots $ $ a_{N-1,0} $ $ \cdots $ $ a_{N-1,N-1} $ - $ t $ は入力の生成方法を表す整数で、$ 0\leq\ t\leq\ 19 $ を満たす。詳細は入力生成方法の欄を参照せよ。 - 盤面の大きさ $ N $ は $ 10\leq\ N\leq\ 100 $ を満たす。 - $ v_{i,0}\cdots\ v_{i,N-2} $ は `0` と `1` からなる $ N-1 $ 文字の文字列であり、$ v_{i,j}=1 $ であればマス $ (i,j) $ とその右隣のマス $ (i,j+1) $ の間に壁があり、$ v_{i,j}=0 $ であれば壁がないことを表す。 - $ h_{i,0}\cdots\ h_{i,N-1} $ は `0` と `1` からなる $ N $ 文字の文字列であり、$ h_{i,j}=1 $ であればマス $ (i,j) $ とその下隣のマス $ (i+1,j) $ の間に壁があり、$ h_{i,j}=0 $ であれば壁がないことを表す。 - 全てのマスは互いに到達可能であることが保証されている。 - $ a_{i,j} $ は初期状態でマス $ (i,j) $ に書かれている数字を表し、$ 1\leq\ a_{i,j}\leq\ N^2 $ を満たす。

まず初めに、高橋君の初期位置 $ (p_i,p_j) $ と青木君の初期位置 $ (q_i,q_j) $ を決め、以下の形式で一行で標準出力に出力せよ。 > $ p_i $ $ p_j $ $ q_i $ $ q_j $ 初期位置は盤面の範囲内であれば、自由に決めて良い。 続いて、全体で $ k $ 回の行動を行う場合、1回の行動毎に以下の形式で1行に3文字を空白区切りで、合計 $ k $ 行を標準出力に出力せよ。 > $ s $ $ d $ $ e $ - $ s $ は数字の交換を行うかどうかを表す文字で、交換する場合は `1` 、しない場合は `0` である。 - $ d $ は高橋君の移動先を表す文字で、上下左右に隣接するマスに移動する場合は、それぞれ `U` `D` `L` `R`、移動せず現在位置にとどまる場合は `.` である。 - $ e $ は青木君の移動先を表す文字で、高橋君の場合と同様である。 移動先との間に壁がある場合や、行動回数が $ 4\ N^2 $ 回を超えた場合は WA と判定される。

### 得点 隣接するマスのペア全体の集合を $ E $ とし、隣接マスの数字の差の二乗和 $ \sum_{u,v\in\ E}(a_u-a_v)^2 $ を考える。 初期状態における二乗和の値を $ D' $、最終状態における二乗和の値を $ D $ としたとき、以下の得点が得られる。 \\\[ \\max\\left(1, \\mathrm{round}\\left(10^6\\times \\log\_2\\frac{D'}{D}\\right)\\right) \\\] 下記で述べる $ t $ の値毎に $ 10 $ 個ずつ、合計で 200 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 $ t $ の値毎に別のテストセット(`test_t`)に別れており、不正な出力や制限時間超過をした場合、対応するテストセットのみが $ 0 $ 点となる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。 ### 入力生成方法 **入力のうちの $ a $ を除いた部分は、入力を生成する seed 値を 20 で割った余り $ t $ に応じて固定であり、下記にリンクがある入力ジェネレータに含まれる `in_fixed/t.txt` がそのまま使われる。 テストケースには各 $ t\in\ \{0,1,\cdots,19\} $ の入力がそれぞれちょうど 10 個ずつ含まれる。** 各マスの数字 $ a_{i,j} $ は $ 1 $ から $ N^2 $ の値をランダムに並び替えることにより生成される。 ### ツール(入力ジェネレータ・スコア計算プログラム) - [ソースコード](https://img.atcoder.jp/masters-qual/ak2uQT08.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/masters-qual/ak2uQT08_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、チーム外とのビジュアライズ結果の共有や解法・考察に関する言及は禁止されています。ご注意下さい。