No.3779 L or R
タグ : / 解いたユーザー数 38
作問者 :
問題文
$N$ 個のランプが横一列に並んでいます。 $1\le i\le N$ について、左から $i$ 番目のランプをランプ $i$ と呼びます。 各ランプは消灯状態と点灯状態という $2$ つの状態を持ちます。 また、各ランプにはボタンがついており、ボタンを押すたびにそのランプの状態が切り替わります。
ランプの初期状態が文字列 $S$ として与えられます。 $S$ は o と x からなる長さ $N$ の文字列であり、
$S$ の $i$ 文字目が o であるとき初期状態でランプ $i$ が点灯状態であることを、
x であるとき初期状態でランプ $i$ が消灯状態であることを表します。
これから $N$ 回の操作を行います。 $i$ 回目 $(1\le i\le N)$ の操作では、以下の $2$ 種類の操作からちょうどどちらか一方を選んで行います。
-
操作 $L$
$j=1,2,\cdots ,i$ について、ランプ $j$ のボタンを $1$ 回ずつ押す。
-
操作 $R$
$j=i,i+1,\cdots ,N$ について、ランプ $j$ のボタンを $1$ 回ずつ押す。
どちらの操作を選択してもランプ $i$ のボタンは必ず押されることに注意してください。
$N$ 回の操作を適切に行うことで、全ての操作が終了した時点で全てのランプが点灯状態であるようにできるかどうかを判定し、できるならばそのような操作列を $1$ つ出力してください。
制約
- $1\le N\le 2\times 10^5$
- $S$ は
oとxからなる長さ $N$ の文字列 - $N$ は整数
入力
入力は以下の形式で与えられます。
$N$ $S$
出力
問題文中の条件を満たす操作列が存在しない場合、 No と一行に出力してください。
存在する場合、 $1$ 行目に Yes と出力し、 $2$ 行目に操作列を表す文字列 $T$ を出力してください。
ここで $T$ は L と R からなる長さ $N$ の文字列であり、 $T$ の $i$ 文字目が L であるとき $i$ 回目の操作で操作 $L$ を行うことを、
R であるとき $i$ 回目の操作で操作 $R$ を行うことを表します。
最後に改行してください。
サンプル
サンプル1
入力
4 oxox
出力
Yes LLLL
$4$ 回の操作によって、ランプの状態は oxox $\rightarrow$ xxox $\rightarrow$ ooox $\rightarrow$ xxxx $\rightarrow$ oooo
と変化します。
サンプル2
入力
1 o
出力
No
サンプル3
入力
10 ooxxxoxoxo
出力
Yes LRRLRRRRRR
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。