問題一覧 > 通常問題

No.1961 Clear Brackets

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 9
作問者 : 👑 tute7627tute7627 / テスター : PCTprobabilityPCTprobability
0 ProblemId : 7835 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-27 20:17:24

問題文

以下のいずれかの条件を満たす文字列を正しい括弧列と定義します。

  • 空文字列
  • ある正しい括弧列 $A$ が存在して、(, $A$, ) をこの順に連結した文字列
  • ある空でない正しい括弧列 $A$, $B$ が存在して、$A$, $B$ をこの順に連結した文字列

ある(, )からなる文字列について、スコアを以下のように定義します。

  • 以下の操作をその文字列に対して操作が行えなくなるまで行う場合に、操作を行う回数として考えられる最小値
    • 文字列の空でない連続した部分文字列であって、正しい括弧列であるものを一つ選び、取り除く。操作によって二つの文字列に分かれた場合、元の順番通りに文字列を連結する。

長さ $N$ の (, ), ?からなる文字列 $S$ が与えられます。

$S$ の?をそれぞれ(または)に置き換えることによって得られる文字列のスコアとして考えられる最大値を求めてください。

入力

$N$
$S$

  • $1 \le N \le 2 \times 10^5$
  • $S$ は (, ), ? のみからなる長さ $N$ の文字列

出力

$S$ の?をそれぞれ(または)に置き換えることによって得られる文字列のスコアとして考えられる最大値を求めてください。 最後に改行してください。

サンプル

サンプル1
入力
8
((??)(?)
出力
2

例えば、(()()())と置き換えた場合、文字列全体が正しい括弧列となるため、スコアは $1$ となります。

一方、(()))())と置き換えた場合、$7$ 文字目から $8$ 文字目を削除すると (()))) となり、その後 $1$ 文字目から $4$ 文字目を削除すると )) となり、 これ以上操作が行えなくなります。$1$ 回以下の操作で操作が行えなくなることはないため、スコアは $2$ となります。

サンプル2
入力
2
??
出力
1

サンプル3
入力
27
(()((?)))?)?????(()))?(()))
出力
5

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