問題一覧 > 通常問題

No.684 Prefix Parenthesis

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 27
作問者 : PulmnPulmn / テスター : WA_TLEWA_TLE
3 ProblemId : 2258 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-05-12 00:33:44

問題文

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

・空文字列は正しい括弧列である。
・文字列 $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

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