No.3143 Colorless Green Parentheses Sleep Furiously
タグ : / 解いたユーザー数 57
作問者 :

ストーリー
((()))
)()()(
括弧列(1)も(2)も $1$ を表す数式にかつて現れたことはないと仮定することは妥当であろう。しかし、(1)は数式に現れないものの正しく、一方で(2)は正しくない。
問題文
1
に1個以上の任意の個数+1
を結合した文字列を単純な足し算と呼びます。
次のいずれかを満たすような文字列 $X$ を式といいます
- $X$ は
1
である - $X$ は
1
でない。かつ「 $X$ に連続部分列として含まれる、ある単純な足し算 $Y$ が存在して(
$Y$)
となっている部分を1
で置き換える」という操作を可能な限り繰り返した後 $X$ が単純な足し算となる
式であるものの例: (1+1)+(1+1)
, ((1+1)+1)+1
式でないものの例: (1)
, ((1+1))+1
また、式 $T$ に対してその数式としての評価を $f(T)$ とします。
例えば、$f($1+(1+1)
$)=3$、$f($1+((1+1)+1)
$)=4$ です。
$g(T)$ を $T$ から(
と)
以外の文字をすべて削除して順番を保ったまま残った文字を結合した文字列とします。
例えば、$g($1+(1+1)
$)=$()
、$g($1+((1+1)+1)
$)=$(())
です。
正整数 $N, K$ と(
および)
からなる長さ $N$ の文字列 $S$ が与えられます。
$f(E)=K$ かつ $g(E)=S$ を満たすような式 $E$ が存在するかを判定してください。存在するなら1つ出力してください。
入力
$N\ K$ $S$
- $1\leq N\leq 10^5$
- $1\leq K\leq 10^5$
- $S$は
(
および)
からなる長さ$N$の文字列
出力
条件を満たす式$E$が存在するならYes
を、そうでないならNo
を1行目に出力してください。
もしYes
が答えなら、条件を満たす $E$ のうち1つを続けて2行目に出力してください。No
なら1行のみを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
6 5 ()(())
出力
Yes (1+1)+(1+(1+1))
$f($(1+1)+(1+(1+1))
$)=5$ であり、$g($(1+1)+(1+(1+1))
$)=$()(())
なので、(1+1)+(1+(1+1))
は確かに条件を満たします。
他にも(1+1)+((1+1)+1)
を出力しても良いです。
サンプル2
入力
4 2 ()()
出力
No
条件を満たすような式 $E$ は存在しません。
サンプル3
入力
8 9 ()()()()
出力
Yes (1+1)+(1+1)+(1+1)+(1+1)+1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。