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

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