No.3142 Balancing with O=>X Flip
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 114
作問者 :
Nauclhlt🪷
/ テスター :
👑
p-adic
タグ : / 解いたユーザー数 114
作問者 :

問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。