問題一覧 > 通常問題

No.3143 Colorless Green Parentheses Sleep Furiously

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 57
作問者 : Nauclhlt🪷 / テスター : 👑 p-adic
2 ProblemId : 12066 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-05-11 23:50:17

ストーリー

  1. ((()))
  2. )()()(

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