問題一覧 > 通常問題

No.3142 Balancing with O=>X Flip

レベル : / AI推定難易度 : 600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 125
作問者 : nauclhlt / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 12053 / 自分の提出
問題文最終更新日: 2025-05-15 08:30:50
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 parenthesis sequence

A string $X$ is called a balanced parenthesis 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 contiguous substring

For example, ()(()) and ()()()() are balanced parenthesis sequences, but ))((, )()()(, and so on are not balanced parenthesis sequences.


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

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

  • Replace a () contained in $S$ as a contiguous substring with )(. More precisely, choose one $i(1\leq i\leq N - 1)$ satisfying $S_i=$(, $S_{i+1}=$), and replace $S_i$ with ) and $S_{i+1}$ with (
Notation for strings For a string $A$, with $|A|$ denoting the length of $A$, $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 ( and )

Output

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

Sample

Sample 1
Input
6
)())()
Output
No

No matter how the operations are performed, it is impossible to make $S$ a balanced parenthesis sequence.

Sample 2
Input
5
()()(
Output
No

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