問題一覧 > 通常問題

No.3779 L or R

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 38
作問者 : askr58 / テスター : 👑 AngrySadEight
お気に入りにしたユーザー ProblemId : 13411 / 自分の提出
問題文最終更新日: 2026-09-21 05:55:41
yukicoder contest 520 (順位表) の他の問題:

問題文

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。