問題一覧 > 通常問題

No.3141 Balancing with X=>O Flip

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

問題文

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

文字列 $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
)))(((
出力
Yes

例えば、)))((($\rightarrow$))()(($\rightarrow$)())(($\rightarrow$()))(($\rightarrow$())()($\rightarrow$()())($\rightarrow$()()()と操作すると、$S$を対応が取れた括弧列にできます。

他にも、操作の手順によっては(())()などの最終形もあり得ます。

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

どのように操作しても不可能です。

サンプル3
入力
8
)()()()(
出力
Yes

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