問題一覧 > 通常問題

No.1961 Clear Brackets

レベル : / AI推定難易度 : 2675 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 9
作問者 : 👑 tute7627 / テスター : PCTprobability
お気に入りにしたユーザー ProblemId : 7835 / 自分の提出
問題文最終更新日: 2022-05-27 20:17:24
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 345 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。