問題一覧 > 通常問題

No.1650 Moving Coins

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 153
作問者 : 👑 chocoruskchocorusk / テスター : KazunKazun
6 ProblemId : 6723 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-16 07:53:47

問題文

$10^6$ 個のマスが横一列に並んでいます。マスは左から順に $1, 2, \ldots , 10^6$ と番号が振られています。

$N$ 枚のコインがマス目の上に置かれています。はじめ、コインはマス $A_1, A_2, \ldots , A_N$ に $1$ 枚ずつ置かれています。ラスク君は、コインを $1$ つ選び、左隣または右隣のマスに動かす操作を何度でも行うことができます。ただし、同じマスに $2$ 枚以上のコインが置かれるような操作や、コインをマス目の外に移動させる操作を行うことはできません。

ラスク君の目標は、マス $B_1, B_2, \ldots , B_N$ にコインが $1$ 枚ずつ置かれている状態にすることです。これに必要な操作回数の最小値を求め、最小値を達成する操作手順を $1$ つ求めてください。

入力

$N$
$A_1\ A_2\ \ldots \ A_N$
$B_1\ B_2\ \ldots \ B_N$

  • $1\leq N\leq 2\times 10^5$
  • $1\leq A_1 < A_2 < \ldots < A_N\leq 10^6$
  • $1\leq B_1 < B_2 < \ldots < B_N\leq 10^6$
  • $2\times 10^5$ 回以下の操作で目標を達成することができる。
  • 入力はすべて整数である。

出力

以下の形式で出力してください。

$M$
$k_1\ c_1$
$k_2\ c_2$
$:$
$k_M\ c_M$
$1$ 行目には、操作回数の最小値 $M$ を出力してください。

続く $M$ 行には、操作回数の最小値を達成する操作手順を出力してください。$i+1$ 行目 ($1\leq i\leq M$) には、$i$ 回目の操作を表す整数 $k_i$ ($1\leq k_i\leq N$) と文字 $c_i$ (L または R) を空白区切りで出力してください。これは、$c_i$ が L なら左から $k_i$ 番目のコインを左隣のマスに動かすこと、R なら左から $k_i$ 番目のコインを右隣のマスに動かすことを表します。

条件を満たす操作手順が複数考えられる場合、どれを出力しても構いません。

サンプル

サンプル1
入力
2
1 2
2 4
出力
3
2 R
1 R
2 R

  • $1$ 回目の操作では、左から $2$ 番目のコインを右隣のマスに動かす。マス $1$, $3$ にコインが $1$ 枚ずつ置かれている状態になる。
  • $2$ 回目の操作では、左から $1$ 番目のコインを右隣のマスに動かす。マス $2$, $3$ にコインが $1$ 枚ずつ置かれている状態になる。
  • $3$ 回目の操作では、左から $2$ 番目のコインを右隣のマスに動かす。マス $2$, $4$ にコインが $1$ 枚ずつ置かれている状態になる。
$2$ 回以下の操作で目標を達成することはできないので、この出力は正解となります。

一方、次の出力は、$1$ 回目の操作後、マス $2$ にコインが $2$ 枚ある状態になってしまうため、不正解となります。

不正解の出力
3
1 R
2 R
2 R
サンプル2
入力
3
999998 999999 1000000
999998 999999 1000000
出力
0

全く操作を行わなくてよい場合もあります。

サンプル3
入力
4
2 4 7 8
3 4 5 6
出力
5
3 L
1 R
4 L
3 L
4 L

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。