問題一覧 > 通常問題

No.3141 Balancing with X=>O Flip

レベル : / AI推定難易度 : 400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 133
作問者 : nauclhlt / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 12046 / 自分の提出
問題文最終更新日: 2025-05-15 08:31:00
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 467 (順位表) の他の問題:

Problem Statement

Definition of a balanced bracket sequence

A string $X$ is called a balanced bracket sequence if it satisfies the following.

  • $X$ can be turned into the empty string by repeating, 0 or more times, the operation of deleting a () contained in $X$ as a substring

For example, ()(()) and ()()()() are balanced bracket sequences, but ))(( and )()()( are not balanced bracket sequences.


There is a string $S$ of length $N$ consisting of ( and ).

Determine whether $S$ can be turned into a balanced bracket sequence by repeating the following operation any number of times, possibly 0.

  • Replace a )( contained in $S$ as a substring with (). More precisely, choose one $i(1\leq i\leq N - 1)$ satisfying $S_i=$), $S_{i+1}=$(, then replace $S_i$ with ( and $S_{i+1}$ with )
Notation for strings For a string $A$, let $|A|$ be the length of $A$. Then $A_i(1\leq i\leq |A|)$ denotes the $i$-th character of $A$.

Input

$N$
$S$
  • $1\leq N\leq 10^5$
  • $S$ is a string of length $N$ consisting of (, )

Output

Print Yes if $S$ can be turned into a balanced bracket sequence by 0 or more operations, and No otherwise.

Sample

Sample 1
Input
6
)))(((
Output
Yes

For example, performing the operations as )))((($\rightarrow$))()(($\rightarrow$)())(($\rightarrow$()))(($\rightarrow$())()($\rightarrow$()())($\rightarrow$()()() turns $S$ into a balanced bracket sequence.

Depending on the sequence of operations, other final forms such as (())() are also possible.

Sample 2
Input
5
()()(
Output
No

It is impossible no matter how the operations are performed.

Sample 3
Input
8
)()()()(
Output
Yes

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