A - Sliding Tree Puzzle 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MB

ストーリー

パズルが大好きな高橋くんは以下のような有名なスライドパズルで遊んでいる。

N \times N の盤面上に N^2-1 枚のタイルが配置されている。 1タイル分の空きマスがあり、4方向に隣接するタイルを空きマスへスライド移動させることが出来る。 絵が各タイルに分割して描かれているので、スライド操作を繰り返すことでタイルを移動させ、絵を完成させよ。

困ったことに、高橋くんは説明書を捨ててしまったため、完成図が分からなくなってしまった。 記憶によると、木 が描かれていたらしい。 スライド操作を繰り返すことで、木を完成させてほしい。

exampl

問題文

N \times N の盤面上に N^2-1 枚のタイルが配置されている。 上から i 行目 (0\leq i \leq N-1)、左から j 列目 (0\leq j\leq N-1) の座標を (i, j) とする。 各タイルは中心から上下左右の4方向のうち1つ以上の方向に向かって線が伸びた図形が描かれており、左方向を1、上方向を2、右方向を4、下方向を8としたビットマスクを用いて以下のように表現される。

タイル
2進数表現 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
16進数表現 0 1 2 3 4 5 6 7 8 9 a b c d e f

0 番は空きマスを表し、空きマスはちょうど一つだけ存在する。 一回の操作で空きマスの上下左右に隣接するタイルを1つ選んで空きマスの位置にスライド移動させることが出来る。移動後は移動元のマスが空きマスとなる。 操作は最大で T=2\times N^3 回繰り返すことが出来る。

操作を終えた時点のタイル配置に対して、空きマス以外の N^2-1 マスを頂点とし、以下のように辺を張ったグラフを考える。

  • 各 (i, j) (0\leq i\leq N-2, 0\leq j\leq N-1) について、(i,j) が下方向に線が伸びた図形の描かれたタイルで、(i+1,j) が上方向に線が伸びた図形の描かれたタイルであるならば、(i,j) と (i+1,j) の間に辺を張る。
  • 各 (i, j) (0\leq i\leq N-1, 0\leq j\leq N-2) について、(i,j) が右方向に線が伸びた図形の描かれたタイルで、(i,j+1) が左方向に線が伸びた図形の描かれたタイルであるならば、(i,j) と (i,j+1) の間に辺を張る。

このグラフに含まれる最大の木の大きさ、すなわち、閉路を持たない最大の連結成分の頂点数が出来るだけ大きくなるような短い操作列を求めて出力せよ。 T 回以内の操作により、(N-1,N-1) に空きマスを配置した状態の、大きさ N^2-1 の木を作成出来ることは保証されている。 ただし、出力する操作列における最終的な空きマスの位置は任意であり、(N-1,N-1) に移動させる必要はない。

得点

操作回数を K、操作を終えた時点での盤面に描かれた最大の木の大きさを S とすると、以下の得点が得られる。

  • S<N^2-1 の場合、\mathrm{round}\left(500000\times \frac{S}{N^2-1}\right)
  • S=N^2-1 の場合、\mathrm{round}\left(500000\times (2-\frac{K}{T})\right)

操作回数が T を超えたり、存在しないタイルを空きマスに移動させようとする不正な操作を行った場合、WA と判定される。

テストケース数

  • 暫定テスト: 50個
  • システムテスト: 3000個、コンテスト終了後にseeds.txt (sha256=041256f962c6ba1a60294ad7a575684d6e401163cba316cf978f2e66a4f7b0e3) を公開
  • 暫定テスト、システムテスト共に、N=6,7,8,9,10 の入力が同じ個数ずつ含まれている

各テストケースの得点の合計が提出の得点となる。 暫定テストでは、一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 システムテストでは、不正な出力や制限時間超過をした場合、そのテストケースのみ0点となる。

実行時間について

実行時間には多少のブレが生じます。 また、システムテストでは同時に大量の実行を行うため、暫定テストに比べて数%程度実行時間が伸びる現象が確認されています。 そのため、実行時間制限ギリギリの提出がシステムテストでTLEとなる可能性があります。 プログラム内で時間を計測して処理を打ち切るか、実行時間に余裕を持たせるようお願いします。

入力

入力は以下の形式で標準入力から与えられる。

N T
t_{0,0} \cdots t_{0,N-1}
\vdots
t_{N-1,0} \cdots t_{N-1,N-1}

N は盤面の縦・横のサイズを表す整数で、6\leq N\leq 10 を満たす。 全てのテストケースで、T=2\times N^3 である。 t_{i,0} \cdots t_{i,N-1} は長さ N の文字列である。 j 番目の文字 t_{i,j} は初期状態におけるマス (i,j) に置かれたタイルに描かれた図形を16進数表記したものであり、0-9 もしくは a-f のいずれかである。

出力

空きマスの上下左右に隣接するタイルをスライドさせる操作をそれぞれ、一文字 U, D, L, R で表し、K 回の操作を長さ K の文字列として標準出力に一行で出力せよ。

例を見る

入力生成方法

N, T の生成

N は seed値 を5で割った余り + 6 により生成される。 このため、seed値を調整することで特定の N の値を持つ入力のみを生成することが可能である。 T=2\times N^3 と設定する。

t_{i,j} の生成

[k]=\{0,1,\cdots,k-1\} と定義する。 V=[N]\times [N]\setminus \{(N-1,N-1)\} を頂点とした全域木 (V,F) を以下のようにしてランダム作成する。

  1. \{\{(i,j),(i+1,j)\}\mid (i,j)\in [N-1]\times [N]\setminus \{(N-2,N-1)\}\}\cup\{\{(i,j),(i,j+1)\}\mid (i,j)\in [N]\times [N-1]\setminus \{(N-1,N-2)\}\} をランダムな順にシャッフルして e_0, e_1, \cdots とする。
  2. F=\emptyset から開始し、各 e_k=\{(i,j),(i',j')\} に対して順番に、(i,j) と (i',j') が (V,F) 上で連結でないならば e_k を F に加える、という操作を繰り返す。

得られた全域木から、完成図を以下のように作成する。

  1. 各 (i,j) について、\{(i,j),(i+1,j)\}\in F であるならば、(i, j) のタイルに下方向の線を引き、(i+1,j) のタイルに上方向の線を引く
  2. 各 (i,j) について、\{(i,j),(i,j+1)\}\in F であるならば、(i, j) のタイルに右方向の線を引き、(i,j+1) のタイルに左方向の線を引く

最後に、完成図の状態から開始して T=2\times N^3 回ランダムな操作を行い、操作後の盤面の状態を t とする。ただし、k (\geq 2) 回目の操作は k-1 回目の操作を元に戻す方向以外の最大3方向の中から一様ランダムに選択する。

ツール(入力ジェネレータ・ビジュアライザ)

コンテスト期間中に、seed=0 に対するビジュアライザの出力画像(PNG)のみ twitter で共有が可能です。動画形式での共有は禁止されているのでご注意下さい。 必ず指定されたハッシュタグを用い、公開アカウントを使用して下さい。共有出来るのはseed=0に対するビジュアライズ結果と点数のみで、GIF動画や出力文字列、他のシードでの点数の共有や、解法・考察に関する言及は禁止です。 (追記)ビジュアライザにはNの値を変更する機能がありますが、Seed=0でも変更したものの共有は不可です。

共有された画像の一覧

入力例 1

6 432
62ce43
a068f9
a89da9
5d93cb
276253
424ba8

出力例 1

RRRDLUULDDDDLUUUR

Story

Takahashi loves puzzles and is playing with the following famous sliding puzzle.

There are N^2-1 tiles on an N \times N board. There is a single empty square, and you can slide an adjacent tile in any of the four directions into the empty square. Some picture is divided into each tile. By repeatedly sliding the tiles, please align the picture.

The trouble is, Takahashi had thrown away the instruction manual, so he lost the target picture. According to his memory, the target picture was a tree. By repeating the sliding operation, please complete a tree.

exampl

Problem Statement

There are N^2-1 tiles on an N \times N board. Let (i, j) denote the coordinates of row i (0\leq i \leq N-1) from the top and column j (0\leq j\leq N-1) from the left. Each tile contains a figure with lines from its center towards one or more of four directions: up, down, left, and right. We represent each tile using a bitmask with 1 for left, 2 for up, 4 for right, and 8 for down, as follows.

Tile
Binary 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
Hex 0 1 2 3 4 5 6 7 8 9 a b c d e f

The number 0 represents an empty square, and there is exactly one empty square. With a single operation, you can slide one of the tiles adjacent to the empty square in the four directions to the location of the empty square. After the move, the square from which the tile was moved becomes an empty square. You can repeat the sliding operation at most T=2\times N^3 times.

After finishing the operations, consider a graph with N^2-1 squares other than the empty square as vertices and the following edges.

  • For each (i, j) (0\leq i\leq N-2, 0\leq j\leq N-1), if (i,j) is a tile with a downward line and (i+1,j) is a tile with an upward line, then construct an edge between (i,j) and (i+1,j).
  • For each (i, j) (0\leq i\leq N-1, 0\leq j\leq N-2), if (i,j) is a tile with a rightward line and (i,j+1) is a tile with a leftward line, then construct an edge between (i,j) and (i,j+1).

Your task is to find a short sequence of operations such that the size of the largest tree in this graph, i.e., the number of vertices of the largest connected component without cycles, is as large as possible. It is guaranteed that within T operations you can construct a tree of size N^2-1 with the empty square in (N-1,N-1). Note that the final position of the empty square is arbitrary and you do not have to move it to (N-1,N-1).

Scoring

Let K be the number of operations and S be the size of the largest tree painted on the board after applying the sequence of operations. Then, you will get the following score.

  • If S<N^2-1, \mathrm{round}\left(500000\times \frac{S}{N^2-1}\right)
  • If S=N^2-1, \mathrm{round}\left(500000\times (2-\frac{K}{T})\right)

If the number of operations exceeds T or you perform an illegal operation to move a non-existent tile to the empty square, it will be judged as WA .

Number of test cases

  • Provisional test: 50
  • System test: 3000. We will publish seeds.txt (sha256=041256f962c6ba1a60294ad7a575684d6e401163cba316cf978f2e66a4f7b0e3) after the contest is over.
  • Both provisional and system tests contain the same number of inputs for each N=6,7,8,9,10.

The score of a submission is the total scores for each test case. In the provisional test, if your submission produces illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE , and the score of the submission will be zero. In the system test, if your submission produces illegal output or exceeds the time limit for some test cases, only the score for those test cases will be zero.

About execution time

Execution time may vary slightly from run to run. In addition, since system tests simultaneously perform a large number of executions, it has been observed that execution time increases by several percent compared to provisional tests. For these reasons, submissions that are very close to the time limit may result in TLE in the s ystem test. Please measure the execution time in your program to terminate the process, or have enough margin in the execution time.

Input

Input is given from Standard Input in the following format:

N T
t_{0,0} \cdots t_{0,N-1}
\vdots
t_{N-1,0} \cdots t_{N-1,N-1}

N is an integer representing the height and width of the board, satisfying 6\leq N\leq 10. In all test cases, T=2\times N^3. t_{i,0} \cdots t_{i,N-1} is a string of length N. The j-th character t_{i,j} is 0-9 or a-f which is the hexadecimal representation of the figure contained in the tile (i,j).

Output

By representing each operation of sliding the upward, downward, leftward, or rightward adjacent tile into the empty square by a single character U, D, L or R, respectively, output the sequence of K operations as a string of length K in one line to Standard Output.

Show example

Input Generation

Generation of N and T

We generate N as the remainder of the seed value divided by 5 + 6. Hence, you can generate inputs with a specific N value by adjusting the seed value. We set T=2\times N^3.

Generation of t_{i,j}

Let [k]=\{0,1,\cdots,k-1\}. We randomly generate a spanning tree (V,F) with vertices V=[N]\times [N]\setminus \{(N-1,N-1)\} as follows.

  1. First, we randomly shuffle edges \{\{(i,j),(i+1,j)\}\mid (i,j)\in [N-1]\times [N]\setminus \{(N-2,N-1)\}\}\cup\{\{(i,j),(i,j+1)\}\mid (i,j)\in [N]\times [N-1]\setminus \{(N-1,N-2)\}\} and obtain an ordered edge list e_0, e_1, \cdots.
  2. Starting from F=\emptyset, for each e_k=\{(i,j),(i',j')\}, we insert e_k into F if (i,j) and (i',j') are not connected in (V,F).

From the obtained spanning tree, we construct tiles on which a tree of size N^2-1 is drawn, as follows.

  1. For each (i,j), if \{(i,j),(i+1,j)\}\in F, then draw a downward line on tile (i, j) and an upward line on tile (i+1,j).
  2. For each (i,j), if \{(i,j),(i,j+1)\}\in F, then draw a rightward line on tile (i, j) and a leftward line on tile (i,j+1).

Finally, starting from the constructed tile layout, randomly perform T=2\times N^3 sliding operations, and let t be the tile layout after the operations. Here, the k (\geq 2)-th operation is chosen uniformly at random from at most three directions excluding the direction that reverts the (k-1)-th operation.

Tools (Input generator and visualizer)

You are allowed to share output images (PNG) of the provided visualizer for seed=0 on twitter during the contest. Note that sharing in video format is prohibited. You have to use the specified hashtag and public account. You can only share visualization results and scores for seed=0. Do not share GIFs, output itself, scores for other seeds or mention solutions or discussions. (Added) The visualizer has a feature to change the value of N, but sharing visualization results for changed inputs is also prohibited.

List of shared images

Sample Input 1

6 432
62ce43
a068f9
a89da9
5d93cb
276253
424ba8

Sample Output 1

RRRDLUULDDDDLUUUR