No.3142 Balancing with O=>X Flip
問題文最終更新日: 2025-05-15 08:30:50
English (AI translation)
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
nauclhlt