A - Macro Controller Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

ストーリー

AtCoder 社の高橋社長は球技が好きである。 しかし、仕事の合間にさまざまなボールで遊んでいるうちに、オフィス中にボールを散らかしてしまった。

それを見た青木副社長は大変怒り、高橋社長にすぐ片付けるよう命じた。 困った高橋社長は、最近購入したお片付けロボットを使ってボールを片付けることにした。

このロボットは、前進・右折・左折・交換という基本操作によって、オフィス内を移動しながらボールを拾ったり置いたりできる。 さらに、付属のコントローラーにはマクロ機能があり、一連の操作を記録して後から再生することもできる。

高橋社長の代わりに、できるだけ短い操作列で、すべてのボールを対応するかごに片付けてほしい。

問題文

N\times N マスの盤面がある。 左上のマスの座標を (0,0) とし、下方向に i、右方向に j 進んだ位置の座標を (i,j) とする。

盤面の外周は壁で囲まれており、隣接するマス間にも壁が存在する場合がある。 すべてのマスは、壁を越えずに上下左右の移動を繰り返すことで互いに到達可能であることが保証されている。

盤面上には、M 種類のボールと、M 種類のかごが置かれている。 各種類 k\ (0\leq k<M) について、種類 k のボールが 1 個、種類 k のかごが 1 個存在する。 初期状態において、各マスには高々 1 つのボールまたはかごが置かれている。

ロボットは初期状態でマス (0,0) におり、右を向いている。 また、初期状態ではボールを持っていない。

ロボットに対して、以下の 4 種類の基本操作を行うことができる。

  • 前進 F： 現在向いている向きに 1 マス進む。 移動先のマスとの間に壁がある場合は移動せず、その場に留まる。

  • 右折 R： 現在位置から動かずに、時計回りに 90 度向きを変える。

  • 左折 L： 現在位置から動かずに、反時計回りに 90 度向きを変える。

  • 交換 S： 現在手に持っているボールと、現在位置に置かれているボールを入れ替える。 手にボールを持っておらず、現在位置にボールがある場合、そのボールを拾い、現在位置はボールのない状態になる。 手にボールを持っており、現在位置にボールがない場合、そのボールを現在位置に置き、手には何も持っていない状態になる。 手にボールを持っており、現在位置にもボールがある場合、手に持っているボールと現在位置のボールを入れ替える。 手にボールを持っておらず、現在位置にもボールがない場合、何も起こらない。 かごのあるマスに置かれたボールも、交換操作により交換される。

高橋くんのコントローラーには、さらに以下の 2 種類の操作がある。

  • マクロ M： 現在、マクロの記録中でない場合、マクロの記録を開始する。 現在、マクロの記録中である場合、記録を終了し、記録された操作列を新しいマクロとして登録する。

  • 再生 P： 最後に登録が完了したマクロを再生する。 登録済みのマクロが存在しない場合は何も起こらない。

マクロの記録中に基本操作 F, R, L, S を行った場合、その操作は実行されるとともに、記録中のマクロの末尾に追加される。

マクロの記録中に P を行った場合、現在記録中のマクロではなく、最後に登録が完了したマクロが再生される。 このとき、実際に再生された基本操作列が、記録中のマクロの末尾に追加される。

例えば、登録済みのマクロが RFF である状態で、操作列 MFPM を実行した場合を考える。 まず M によりマクロの記録を開始し、次に F を実行して記録する。 その後、P により登録済みのマクロ RFF が再生され、これも記録中のマクロに追加される。 最後に M により記録を終了する。 この間に実行された基本操作列は FRFF であり、新たに登録されるマクロも FRFF である。

初期状態ではマクロは登録されていない。 また、初期状態ではマクロの記録は行われていない。

入力として基本操作回数の上限 T が与えられる。 マクロ展開後の基本操作は最長で T 回まで実行され、T+1 回目の基本操作は実行されずに打ち切られる。 できるだけ短い操作列で、すべてのボールを対応するかごに入れることを目指せ。

得点

出力した操作列の長さを A とする。 ここで、M および P もそれぞれ 1 回のボタン操作として数える。

シミュレーション終了時に、対応するかごのマスに置かれているボールの個数を V とする。

このとき、各テストケースに対して以下の絶対スコアが得られる。

  • V=M の場合、A
  • V<M の場合、T\times (M-V)

絶対スコアは小さければ小さいほど良い。

各テストケースごとに、\mathrm{round}(10^9\times \frac{全参加者中の最小絶対スコア}{自身の絶対スコア}) の相対評価スコアが得られ、その和が提出の得点となる。

最終順位はコンテスト終了後に実施される、より多くの入力に対するシステムテストにおける得点で決定される。 暫定テスト、システムテストともに、一部のテストケースで不正な出力や制限時間超過をした場合、そのテストケースの相対評価スコアは 0 点となり、そのテストケースにおいては「全参加者中の最小絶対スコア」の計算から除外される。 システムテストはCE 以外の結果を得た一番最後の提出に対してのみ行われるため、最終的に提出する解答を間違えないよう注意せよ。

テストケース数

  • 暫定テスト: 50 個
  • システムテスト: 2000 個、コンテスト終了後に seeds.txt (sha256=d88ec61a00aa2dfb0be89801a7320e56550cf9c71cc2e6959f79c5eb057cf9ae) を公開

相対評価システムについて

暫定テスト、システムテストともに、CE 以外の結果を得た一番最後の提出のみが順位表に反映される。 相対評価スコアの計算に用いられる各テストケースごとの全参加者中の最小絶対スコアの算出においても、順位表に反映されている最終提出のみが用いられる。

順位表に表示されているスコアは相対評価スコアであり、新規提出があるたびに、相対評価スコアが再計算される。 一方、提出一覧から確認できる各提出のスコアは各テストケースごとの絶対スコアをそのまま足し合わせたものであり、相対評価スコアは表示されない。 最新以外の提出について、現在の順位表における相対評価スコアを知るためには、再提出が必要である。 不正な出力や制限時間超過をした場合、提出一覧から確認できるスコアは 0 となるが、順位表には正解したテストケースに対する相対スコアの和が表示される。

実行時間について

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

入力

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

N M T
v_0
\vdots
v_{N-1}
h_0
\vdots
h_{N-2}
b_0 c_0 d_0 e_0
\vdots
b_{M-1} c_{M-1} d_{M-1} e_{M-1}

ここで、(b_k,c_k) は種類 k のボールの初期位置を表し、(d_k,e_k) は種類 k のかごの位置を表す。

各値は以下の制約を満たす。

  • 10\leq N\leq 20
  • N/2\leq M\leq 2N
  • 1\leq T\leq 2N^2 M
  • v_{i,0} \cdots v_{i,N-2} は長さ N-1 の 01 からなる文字列であり、j 文字目 v_{i,j} はマス (i, j) とマス (i, j+1) の間に壁がある（1）かない（0）かを表す。
  • h_{i,0} \cdots h_{i,N-1} は長さ N の 01 からなる文字列であり、j 文字目 h_{i,j} はマス (i, j) とマス (i+1, j) の間に壁がある（1）かない（0）かを表す。
  • すべてのマスは互いに到達可能であることが保証されている。
  • ボールの初期位置とかごの位置はすべて相異なる。

出力

操作列の長さを A、t 回目の操作を表す文字 (F, R, L, S, M, P) を a_t としたとき、以下の形式で標準出力に出力せよ。

a_0
\vdots
a_{A-1}

出力する操作列の長さ A は T 以下でなければならない。

例を見る

入力生成方法

L 以上 U 以下の整数値を一様ランダムに生成する関数を \mathrm{rand}(L, U)、 L 以上 U 以下の実数値を一様ランダムに生成する関数を \mathrm{rand\_double}(L, U) とする。

盤面の生成

マスの角にあたる点を「頂点」と呼ぶことにする。

N=\mathrm{rand}(10,20) により盤面サイズを決定する。 壁の本数を W=\mathrm{rand}(0,N-1) により決定し、マス間に壁がない状態から開始して、以下を W 回繰り返す。

頂点のうち、既存の壁に接していないものから一様ランダムに 1 つを選び、その頂点から上下左右のいずれかの方向を選んで、他の壁に接するまで壁を伸ばす。

ボールの初期位置とかごの位置の生成

M=\mathrm{round}(N/2\times 4^{\mathrm{rand\_double}(0,1)}) を生成する。

N^2 個のマスを一様ランダムな順に並び替え、その最初の M 個をボールの初期位置、次の M 個をかごの位置として採用する。

T の生成

座標列 (i_0,j_0),\cdots,(i_{2M},j_{2M}) を以下のように設定する。

  • (i_0,j_0)=(0,0)
  • (i_{2k+1},j_{2k+1})=(b_k,c_k)
  • (i_{2k+2},j_{2k+2})=(d_k,e_k)

上下左右の移動を 1 手として、これらの座標列を順に訪れる最小手数 X を計算する。 r=\mathrm{rand\_double}(0,1) を生成し、 T=\mathrm{round}((2X+4M)^r\times (2N^2M)^{1-r}) により基本操作回数の上限 T を決定する。

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

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

Story

CEO Takahashi of AtCoder Inc. likes ball games. However, while playing with various balls during breaks from work, he scattered balls all over the office.

Seeing this, Vice President Aoki became very angry and ordered Takahashi to clean them up immediately. At a loss, Takahashi decided to use the cleaning robot he had recently purchased to put away the balls.

This robot can move around the office and pick up or put down balls using the basic operations of moving forward, turning right, turning left, and swapping. Furthermore, the included controller has a macro function, which can record a sequence of operations and play it back later.

Instead of Takahashi, put all the balls into their corresponding baskets using as short a sequence of operations as possible.

Problem Statement

There is an N\times N grid. Let the coordinates of the top-left cell be (0,0), and let the coordinates of the cell i cells downward and j cells to the right be (i,j).

The outer boundary of the grid is surrounded by walls, and there may also be walls between adjacent cells. It is guaranteed that every cell is reachable from every other cell by repeatedly moving up, down, left, and right without crossing walls.

On the grid, there are M types of balls and M types of baskets. For each type k\ (0\leq k<M), there is one ball of type k and one basket of type k. In the initial state, each cell contains at most one ball or basket.

The robot is initially at cell (0,0) and facing right. It is not holding any ball initially.

You can perform the following four types of basic operations on the robot.

  • Move forward F: Move one cell in the direction the robot is currently facing. If there is a wall between the current cell and the destination cell, the robot does not move and remains in place.

  • Turn right R: Turn 90 degrees clockwise without moving from the current position.

  • Turn left L: Turn 90 degrees counterclockwise without moving from the current position.

  • Swap S: Swap the ball currently held by the robot with the ball placed at the current position. If the robot is not holding a ball and there is a ball at the current position, it picks up that ball, and the current position becomes empty of balls. If the robot is holding a ball and there is no ball at the current position, it places that ball at the current position, and the robot becomes empty-handed. If the robot is holding a ball and there is also a ball at the current position, the robot swaps the ball it is holding with the ball at the current position. If the robot is not holding a ball and there is no ball at the current position, nothing happens. A ball placed on a cell with a basket is also swapped by the swap operation.

Takahashi's controller also has the following two types of operations.

  • Macro M: If a macro is not currently being recorded, start recording a macro. If a macro is currently being recorded, stop recording and register the recorded sequence of operations as a new macro.

  • Play P: Play back the most recently registered macro. If no macro has been registered, nothing happens.

If a basic operation F, R, L, or S is performed while recording a macro, that operation is executed and appended to the end of the macro being recorded.

If P is performed while recording a macro, the most recently registered macro is played back, not the macro currently being recorded. At this time, the sequence of basic operations that is actually played back is appended to the end of the macro being recorded.

For example, consider the case where the registered macro is RFF and the operation sequence MFPM is executed. First, M starts recording a macro, and then F is executed and recorded. Next, P plays back the registered macro RFF, which is also appended to the macro being recorded. Finally, M stops recording. The sequence of basic operations executed during this period is FRFF, and the newly registered macro is also FRFF.

Initially, no macro is registered. Also, no macro is being recorded initially.

The upper limit T on the number of basic operations is given as input. After macro expansion, at most T basic operations are executed; the (T+1)-st basic operation is not executed, and execution is terminated. Aim to put all balls into their corresponding baskets using as short an operation sequence as possible.

Scoring

Let A be the length of the output operation sequence. Here, M and P are each counted as one button operation.

Let V be the number of balls placed on the cells of their corresponding baskets at the end of the simulation.

For each test case, the following absolute score is obtained.

  • If V=M, A
  • If V<M, T\times (M-V)

The lower the absolute score, the better.

For each test case, we compute the relative score \mathrm{round}(10^9\times \frac{\mathrm{MIN}}{\mathrm{YOUR}}), where YOUR is your absolute score and MIN is the lowest absolute score among all competitors obtained on that test case. The score of the submission is the sum of the relative scores.

The final ranking will be determined by the system test with more inputs which will be run after the contest is over. In both the provisional/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, and your submission will be excluded from the MIN calculation for those test cases.

The system test will be performed only for the last submission which received a result other than CE . Be careful not to make a mistake in the final submission.

Number of test cases

  • Provisional test: 50
  • System test: 2000. We will publish seeds.txt (sha256=d88ec61a00aa2dfb0be89801a7320e56550cf9c71cc2e6959f79c5eb057cf9ae) after the contest is over.

About relative evaluation system

In both the provisional/system test, the standings will be calculated using only the last submission which received a result other than CE. Only the last submissions are used to calculate the MIN for each test case when calculating the relative scores.

The scores shown in the standings are relative, and whenever a new submission arrives, all relative scores are recalculated. On the other hand, the score for each submission shown on the submissions page is the sum of the absolute score for each test case, and the relative scores are not shown. In order to know the relative score of submission other than the latest one in the current standings, you need to resubmit it. If your submission produces illegal output or exceeds the time limit for some test cases, the score shown on the submissions page will be 0, but the standings show the sum of the relative scores for the test cases that were answered correctly.

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 system 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 M T
v_0
\vdots
v_{N-1}
h_0
\vdots
h_{N-2}
b_0 c_0 d_0 e_0
\vdots
b_{M-1} c_{M-1} d_{M-1} e_{M-1}

Here, (b_k,c_k) represents the initial position of the ball of type k, and (d_k,e_k) represents the position of the basket of type k.

Each value satisfies the following constraints.

  • 10\leq N\leq 20
  • N/2\leq M\leq 2N
  • 1\leq T\leq 2N^2 M
  • v_{i,0} \cdots v_{i,N-2} is a string of length N-1 consisting of 0 and 1; its j-th character v_{i,j} indicates whether there is (1) or is not (0) a wall between cell (i, j) and cell (i, j+1).
  • h_{i,0} \cdots h_{i,N-1} is a string of length N consisting of 0 and 1; its j-th character h_{i,j} indicates whether there is (1) or is not (0) a wall between cell (i, j) and cell (i+1, j).
  • It is guaranteed that every cell is reachable from every other cell.
  • All initial positions of balls and positions of baskets are distinct.

Output

Let A be the length of the operation sequence, and let a_t be the character (F, R, L, S, M, P) representing the t-th operation. Output to Standard Output in the following format.

a_0
\vdots
a_{A-1}

The length A of the output operation sequence must be at most T.

View an example

Input Generation

Let \mathrm{rand}(L, U) be a function that generates an integer uniformly at random between L and U, inclusive, and let \mathrm{rand\_double}(L, U) be a function that generates a real number uniformly at random between L and U, inclusive.

Grid Generation

We call the points corresponding to the corners of cells "vertices".

The grid size is determined by N=\mathrm{rand}(10,20). The number of walls is determined by W=\mathrm{rand}(0,N-1), and starting from a state with no walls between cells, the following procedure is repeated W times.

Choose one vertex uniformly at random from those not adjacent to any existing wall, choose one of the four directions from that vertex, and extend a wall until it becomes adjacent to another wall.

Generation of Initial Ball Positions and Basket Positions

Generate M=\mathrm{round}(N/2\times 4^{\mathrm{rand\_double}(0,1)}).

Shuffle the N^2 cells uniformly at random, and use the first M cells as the initial positions of the balls and the next M cells as the positions of the baskets.

Generation of T

Set the coordinate sequence (i_0,j_0),\cdots,(i_{2M},j_{2M}) as follows.

  • (i_0,j_0)=(0,0)
  • (i_{2k+1},j_{2k+1})=(b_k,c_k)
  • (i_{2k+2},j_{2k+2})=(d_k,e_k)

Compute X, the minimum number of moves required to visit these coordinates in order, where one move is a move to an adjacent cell in one of the four cardinal directions. Generate r=\mathrm{rand\_double}(0,1), and determine the upper limit T on the number of basic operations by T=\mathrm{round}((2X+4M)^r\times (2N^2M)^{1-r}).

Tools (Input Generator and Visualizer)

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