問題一覧 > 通常問題

No.3142 Balancing with O=>X Flip

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 114
作問者 : Nauclhlt🪷 / テスター : 👑 p-adic
1 ProblemId : 12053 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-05-15 08:30:50

問題文

対応が取れた括弧列の定義

文字列 $X$ が対応が取れた括弧列であるとは、次を満たすことをいいます。

  • $X$ に連続部分文字列として含まれる()を削除する操作を0回以上繰り返して $X$ を空文字列とすることができる

例えば()(())()()()()対応が取れた括弧列ですが、))(()()()(などは対応が取れた括弧列ではありません。


(および)からなる長さ $N$ の文字列 $S$ があります。

次の操作を0回以上、好きな回数繰り返して $S$ を対応が取れた括弧列にできるか判定してください。

  • $S$ に連続部分文字列として含まれる())(で置き換える。より厳密には $S_i=$(, $S_{i+1}=$)を満たす $i(1\leq i\leq N - 1)$ を1つ選び、$S_i$ を), $S_{i+1}$ を(で置き換える
文字列に関する表記 ある文字列 $A$ について、$A$ の長さを $|A|$ としたとき、$A_i(1\leq i\leq |A|)$ で $A$ の $i$ 文字目を表します。

入力

$N$
$S$
  • $1\leq N\leq 10^5$
  • $S$ は(, )からなる長さ $N$ の文字列

出力

0回以上の操作によって $S$ を対応が取れた括弧列にできるならYes、そうでないならNoを出力してください。

サンプル

サンプル1
入力
6
)())()
出力
No

どのように操作を行っても $S$ を対応が取れた括弧列とすることは不可能です。

サンプル2
入力
5
()()(
出力
No

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