A - Leveling with a Dump Truck Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

ストーリー

AtCoder社は頻繁にオンサイトコンテストを開催しており、コンテスト会場を自前で建設することにした。 建設予定地は山の中にあり、まずは地面を平らに整地しなければならない。 整地にはダンプカーを使用し、土砂を積む、降ろす、運ぶそれぞれに対してコストがかかる。 できるだけ少ないコストで整地を行う方法を求めてほしい。

問題文

N \times N マスの土地がある。 一番左上のマスの座標を (0,0) とし、そこから下方向に i マス、右方向に j マス進んだ先のマスの座標を (i,j) とする。

各マス (i,j) の高さ h_{i,j} が入力として与えられる。 全てのマスの高さの合計はちょうど 0 である。

初期状態で (0,0) のマスにダンプカーが空の積荷の状態で停まっている。 毎ターン以下の3種類の操作から1つを選んで行うことができる。

  • 0<d\leq 10^6 を満たす整数 d を指定し、現在位置から d の土砂をダンプカーに積む。この操作により、現在位置の高さは d 減少し、ダンプカーに積まれた土砂が d 増加する。高さは負の値となっても良い。この操作は d のコストが発生する。
  • 0<d\leq 10^6 を満たす整数 d を指定し、ダンプカーから d の土砂を現在位置に降ろす。この操作により、現在位置の高さは d 増加し、ダンプカーに積まれた土砂が d 減少する。d の値は操作前にダンプカーに積まれている量以下でなければならない。この操作は d のコストが発生する。
  • 上下左右に隣接するマスへダンプカーを移動させる。N \times N マスの外部へ移動することはできない。ダンプカーに積まれた土砂が d のとき、この操作は 100+d のコストが発生する。

操作は最大で 100000 ターン行うことが出来る。 最終的に全てのマスの高さが 0 となるような、出来るだけコストの小さい操作列を求めて欲しい。

得点

出力した操作列の合計コストを \mathrm{cost} とする。 全ての (i,j) について |h_{i,j}| の和を取ったものを \mathrm{base} とする。 マス (i,j) の最終的な高さを h_{i,j}' としたとき、h_{i,j}'\neq 0 であるような全ての (i,j) について 100|h_{i,j}'|+10000 の和を取ったものを \mathrm{diff} と定義する。 このとき、以下の得点が得られる。

\[ \mathrm{round}\left(10^9\times \frac{\mathrm{base}}{\mathrm{cost}+\mathrm{diff}}\right) \]

テストケースは全部で 150 個あり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。

入力

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

N
h_{0,0} \cdots h_{0,N-1}
\vdots
h_{N-1,0} \cdots h_{N-1,N-1}

全てのテストケースで N = 20 で固定である。 初期状態におけるマス (i,j) の高さ h_{i,j} は -100\leq h_{i,j}\leq 100 を満たす整数値であり、その総和は 0 となることが保証されている。

出力

操作ターン数を T とする。 t ターン目の操作を以下のように文字列 s_t で表す。

  • 現在位置から d の土砂をダンプカーに積む操作: +d
  • ダンプカーから d の土砂を現在位置に降ろす操作: -d
  • 隣接するマスへダンプカーを移動させる操作: 上下左右それぞれ U、D、L、R

このとき、以下の形式で標準出力に出力せよ。

s_0
\vdots
s_{T-1}

例を見る

入力生成方法

必ずしも理解する必要はありません。 Web版ビジュアライザのseed値を変えて、どのような入力が生成されるかを眺めることをオススメします。

L 以上 U 以下の整数値を一様ランダムに生成する関数を \mathrm{rand}(L,U) で表す。 乱数シード \mathrm{seed} を元に、-1 以上 1 以下の範囲にスケーリングされた二次元の Perlin noise を生成する関数を \mathrm{noise}(y,x,\mathrm{seed}) で表す。

まずはじめに、Perlin noise 生成に用いるシード値 \mathrm{seed}=\mathrm{rand}(0,2^{32}-1) を生成する。

次に、各 (i,j) について、h_{i,j}=\mathrm{round}(\mathrm{noise}(i/10,j/10,\mathrm{seed})\times 50) を生成する。 もし全ての (i,j) で h_{i,j}=0 であれば、\mathrm{seed} を生成し直す。

h_{i,j} の総和を S とする。 S=0 となるよう、以下のようにして変形を行う。

全ての座標 (0,0),(0,1),\cdots,(N-1,N-1) を一様ランダムな順番にシャッフルし、その k 番目の座標を (i_k,j_k) とする。 S>0 ならば、各 k=0,1,\cdots,S-1 について、h_{i_{k\% N^2},j_{k\% N^2}} を 1 減らす。 S<0 ならば、各 k=0,1,\cdots,-S-1 について、h_{i_{k\% N^2},j_{k\% N^2}} を 1 増やす。

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

コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。

入力例 1

20
10 4 0 0 4 10 16 20 21 16 11 2 -7 -16 -23 -25 -23 -16 -7 2
16 10 6 5 7 10 13 15 14 10 4 -4 -13 -21 -29 -32 -29 -22 -13 -3
20 14 10 8 9 10 11 12 10 6 0 -7 -15 -24 -31 -33 -31 -25 -16 -8
20 15 12 10 10 10 10 11 8 5 0 -5 -12 -20 -26 -29 -28 -23 -15 -7
16 13 12 10 10 10 10 10 9 7 4 1 -4 -10 -16 -20 -20 -17 -10 -3
10 10 10 10 11 10 10 10 10 10 10 9 7 2 -3 -8 -9 -8 -3 3
4 7 9 10 10 10 10 10 11 14 16 18 17 14 9 5 1 1 4 9
0 5 8 10 10 10 10 10 12 15 20 24 25 24 19 14 9 7 9 13
0 6 10 12 11 11 9 9 10 14 20 26 29 28 24 18 13 10 10 14
4 10 14 16 13 10 7 5 6 10 16 23 26 26 23 16 10 8 6 10
11 16 20 21 16 10 4 0 0 4 10 16 21 20 16 10 4 0 1 4
16 23 26 24 18 9 1 -4 -7 -4 2 9 12 12 8 3 -3 -6 -7 -3
20 26 27 24 17 7 -3 -11 -14 -12 -7 -1 2 2 -1 -5 -10 -12 -11 -7
20 24 24 20 13 3 -8 -17 -21 -20 -16 -12 -9 -9 -11 -14 -15 -15 -12 -6
16 18 17 14 6 -3 -13 -20 -24 -25 -23 -21 -20 -19 -21 -21 -18 -15 -10 -3
10 10 8 4 -1 -8 -14 -20 -23 -25 -25 -26 -27 -28 -28 -25 -21 -14 -5 3
4 2 -1 -4 -7 -9 -12 -15 -18 -19 -23 -26 -29 -31 -31 -28 -21 -11 -1 8
0 -4 -7 -9 -9 -8 -7 -7 -8 -11 -16 -20 -26 -30 -31 -28 -20 -8 2 12
0 -6 -9 -10 -7 -3 1 3 3 -1 -7 -13 -20 -26 -29 -27 -20 -9 2 13
4 -3 -6 -6 -3 3 9 12 12 9 3 -5 -12 -20 -25 -26 -21 -12 -1 9

出力例 1

+10
R
+4
R
R
R
R
R
R
R
+50
R
R
R
R
-7
D
-13
L
-44

Story

AtCoder frequently hosts onsite contests and has decided to build its own contest venue. The planned construction site is in a mountain area, and the ground must first be leveled. Leveling will involve using a dump truck, which incurs costs for loading, unloading, and transporting soil. Determine the method to level the ground with as little cost as possible.

Problem Statement

There is an N \times N grid of land. Let (0,0) be the coordinates of the top-left square and (i,j) be the coordinates of the square located i squares down and j squares to the right from there.

The height h_{i,j} of each square (i,j) is given as input. The total height of all squares is exactly 0.

Initially, the dump truck is at the square (0,0) with an empty load. In each turn, you can perform one of the following three operations:

  • Specify an integer d satisfying 0<d\leq 10^6 to load d units of soil from the current square onto the dump truck. This operation decreases the height of the current square by d and increases the amount of soil loaded onto the dump truck by d. The height can become negative. This operation incurs a cost of d.
  • Specify an integer d satisfying 0<d\leq 10^6 to unload d units of soil from the dump truck to the current square. This operation increases the height of the current square by d and decreases the amount of soil loaded onto the dump truck by d. The value of d must not exceed the amount of soil currently loaded onto the dump truck. This operation incurs a cost of d.
  • Move the dump truck to an adjacent square (up, down, left, or right). The dump truck cannot move outside the N \times N grid. If the dump truck has d units of soil loaded, this operation incurs a cost of 100+d.

You can perform a maximum of 100000 turns of operation. Your task is to determine the sequence of operations that minimizes the cost to make the height of every square 0.

Scoring

Let \mathrm{cost} be the total cost of the output operation sequence. Let \mathrm{base} be the sum of |h_{i,j}| for all (i,j). Let h_{i,j}' be the final height of square (i,j). Define \mathrm{diff} as the sum of 100|h_{i,j}'|+10000 for all (i,j) such that h_{i,j}' \neq 0. Then, you will obtain the following score.

\[ \mathrm{round}\left(10^9\times \frac{\mathrm{base}}{\mathrm{cost}+\mathrm{diff}}\right) \]

There are 150 test cases, and the score of a submission is the total score for each test case. If your submission produces an 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. The highest score obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time.

Input

Input is given from Standard Input in the following format:

N
h_{0,0} \cdots h_{0,N-1}
\vdots
h_{N-1,0} \cdots h_{N-1,N-1}

In all test cases, N is fixed at 20. The initial height h_{i,j} of square (i,j) is an integer that satisfies -100 \leq h_{i,j} \leq 100, and the total sum of all heights is guaranteed to be 0.

Output

Let T be the number of operation turns. The operation in the t-th turn is represented by the string s_t as follows:

  • The operation to load d units of soil from the current square onto the dump truck: +d
  • The operation to unload d units of soil from the dump truck to the current square: -d
  • The operation to move the dump truck to an adjacent square: U, D, L, and R for up, down, left, and right, respectively.

Then, output to Standard Output in the following format:

s_0
\vdots
s_{T-1}

Show example

Input Generation

You are not required to understand this. We recommend changing the seed value in the web visualizer to observe what kind of inputs are generated.

Let \mathrm{rand}(L,U) be a function that generates a uniform random integer between L and U, inclusive. Let \mathrm{noise}(y,x,\mathrm{seed}) be a function that generates two-dimensional Perlin noise scaled to the range between -1 and 1 based on a random seed value \mathrm{seed}.

First, generate a seed value for Perlin noise generation as \mathrm{seed}=\mathrm{rand}(0,2^{32}-1).

Next, for each (i,j), generate h_{i,j}=\mathrm{round}(\mathrm{noise}(i/10,j/10,\mathrm{seed})\times 50). If h_{i,j}=0 for all (i,j), then regenerate \mathrm{seed}.

Let S be the sum of h_{i,j}. To make S=0, perform the following transformation.

Shuffle all coordinates (0,0),(0,1),\cdots,(N-1,N-1) in a uniformly random order, and let the k-th coordinate be (i_k,j_k). If S>0, then for each k=0,1,\cdots,S-1, decrease h_{i_{k\% N^2},j_{k\% N^2}} by 1. If S<0, then for each k=0,1,\cdots,-S-1, increase h_{i_{k\% N^2},j_{k\% N^2}} by 1.

Tools (Input generator and visualizer)

Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.

Sample Input 1

20
10 4 0 0 4 10 16 20 21 16 11 2 -7 -16 -23 -25 -23 -16 -7 2
16 10 6 5 7 10 13 15 14 10 4 -4 -13 -21 -29 -32 -29 -22 -13 -3
20 14 10 8 9 10 11 12 10 6 0 -7 -15 -24 -31 -33 -31 -25 -16 -8
20 15 12 10 10 10 10 11 8 5 0 -5 -12 -20 -26 -29 -28 -23 -15 -7
16 13 12 10 10 10 10 10 9 7 4 1 -4 -10 -16 -20 -20 -17 -10 -3
10 10 10 10 11 10 10 10 10 10 10 9 7 2 -3 -8 -9 -8 -3 3
4 7 9 10 10 10 10 10 11 14 16 18 17 14 9 5 1 1 4 9
0 5 8 10 10 10 10 10 12 15 20 24 25 24 19 14 9 7 9 13
0 6 10 12 11 11 9 9 10 14 20 26 29 28 24 18 13 10 10 14
4 10 14 16 13 10 7 5 6 10 16 23 26 26 23 16 10 8 6 10
11 16 20 21 16 10 4 0 0 4 10 16 21 20 16 10 4 0 1 4
16 23 26 24 18 9 1 -4 -7 -4 2 9 12 12 8 3 -3 -6 -7 -3
20 26 27 24 17 7 -3 -11 -14 -12 -7 -1 2 2 -1 -5 -10 -12 -11 -7
20 24 24 20 13 3 -8 -17 -21 -20 -16 -12 -9 -9 -11 -14 -15 -15 -12 -6
16 18 17 14 6 -3 -13 -20 -24 -25 -23 -21 -20 -19 -21 -21 -18 -15 -10 -3
10 10 8 4 -1 -8 -14 -20 -23 -25 -25 -26 -27 -28 -28 -25 -21 -14 -5 3
4 2 -1 -4 -7 -9 -12 -15 -18 -19 -23 -26 -29 -31 -31 -28 -21 -11 -1 8
0 -4 -7 -9 -9 -8 -7 -7 -8 -11 -16 -20 -26 -30 -31 -28 -20 -8 2 12
0 -6 -9 -10 -7 -3 1 3 3 -1 -7 -13 -20 -26 -29 -27 -20 -9 2 13
4 -3 -6 -6 -3 3 9 12 12 9 3 -5 -12 -20 -25 -26 -21 -12 -1 9

Sample Output 1

+10
R
+4
R
R
R
R
R
R
R
+50
R
R
R
R
-7
D
-13
L
-44