No.684 Prefix Parenthesis

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 16
作問者 : PulmnPulmn / テスター : WA_TLEWA_TLE

2 ProblemId : 2258 / 出題時の順位表

問題文

正しい括弧列を以下のように定義します。

・空文字列は正しい括弧列である。
・文字列 $s$ が正しい括弧列であるとき、'(' $+\ s\ +$ ')' は正しい括弧列である。
・文字列 $s,t$ が正しい括弧列であるとき、$s+t$ は正しい括弧列である。

例えば、"(())()"、"(((())))" などが正しい括弧列です。

長さ $N$ の '(' と ')' で構成された文字列 $S$ が与えられます。$1\le i\le N$ について $S$ の $1$ 文字目から $i$ 文字目までの連続した部分列を $S_i$ と表すことにします。$S_1,S_2,\cdots ,S_N$ を好きな順番で連結して得られる文字列を $T$ とします。$T$ の部分列であり正しい括弧列であるような文字列の長さの最大値を $f(T)$ としたとき、$f(T)$ の最大値を求めてください。

※$S$ の部分列とは、$S$ からいくつかの文字を削除した後、残った文字列の順番を変えないでつなげたものを意味します。

入力

$N$
$S$

$1\le N\le 10^5$
$S$ は '(' と ')' で構成された長さ $N$ の文字列

出力

$f(T)$ の最大値を求めてください。最後に改行してください。

サンプル

サンプル1
入力
3
)((
出力
4

$S_1=$ ")" $,$ $S_2=$ ")(" $,$ $S_3=$ ")(("
$S_2+S_1+S_3$ の順に連結すると $T=$")())((" となり $T$ の部分列で正しい括弧列である長さが最大の文字列は "()" です。よって $f(T)=2$ になります。
$S_3+S_1+S_2$ の順に連結すると $T=$")(())(" となり $T$ の部分列で正しい括弧列である長さが最大の文字列は "(())" です。よって $f(T)=4$ になります。
$f(T)\gt 4$ となる $T$ は存在しないので、$f(T)$ の最大値は $4$ となります。

サンプル2
入力
5
)))))
出力
0

$T$ として考えられる文字列は ")))))))))))))))" だけであり、$f(T)=0$ になります。

サンプル3
入力
10
(((()))()(
出力
34

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。