No.1961 Clear Brackets
タグ : / 解いたユーザー数 9
作問者 : 👑
tute7627
/ テスター :
PCTprobability
Problem Statement
A string satisfying any of the following conditions is defined as a correct bracket sequence.
- The empty string
- A string obtained by concatenating
(, $A$,)in this order, for some correct bracket sequence $A$ - A string obtained by concatenating $A$, $B$ in this order, for some non-empty correct bracket sequences $A$, $B$
For a string consisting of (, ), its score is defined as follows.
- The minimum possible number of operations performed when the following operation is applied to the string until no more operations can be performed
- Choose one non-empty contiguous substring of the string that is a correct bracket sequence, and remove it. If the operation splits the string into two strings, concatenate them in their original order.
You are given a string $S$ of length $N$ consisting of (, ), ?.
Find the maximum possible score of a string obtained by replacing each ? in $S$ with ( or ).
Input
$N$ $S$
- $1 \le N \le 2 \times 10^5$
- $S$ is a string of length $N$ consisting only of
(,),?
Output
Find the maximum possible score of a string obtained by replacing each ? in $S$ with ( or ).
Print a newline at the end.
Sample
Sample 1
Input
8 ((??)(?)
Output
2
For example, if it is replaced with (()()()), the whole string is a correct bracket sequence, so the score is $1$.
On the other hand, if it is replaced with (()))()), deleting the $7$-th through $8$-th characters gives (()))), and then deleting the $1$-st through $4$-th characters gives )),
after which no more operations can be performed. Since it is impossible to reach a state where no more operations can be performed with $1$ or fewer operations, the score is $2$.
Sample 2
Input
2 ??
Output
1
Sample 3
Input
27 (()((?)))?)?????(()))?(()))
Output
5
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。