/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
(, ), o, x からなる文字列 S が与えられます．
あなたは，S の隣接する 2 文字をswapする操作を好きな回数行うことができます．
次の条件を達成するために必要な最小の操作回数を求めてください．
- S に登場するすべての
oを()で，xを)(で置き換え，(と)のみからなる文字列 S' を作る． この時，S' は括弧の対応が取れている文字列である．
括弧の対応が取れている文字列の定義
括弧の対応が取れている文字列とは，次のうちいずれかの条件を満たす文字列です．
- 空文字列
- ある括弧の対応が取れている空でない文字列 s, t が存在し，s, t をこの順に連結した文字列
- ある括弧の対応が取れている文字列 s が存在し、
(, s,)をこの順に連結した文字列
なお，この問題の制約より，目標を達成することは必ず可能です．
制約
- S は
(,),o,xからなる文字列 - S は 1 つ以上の
(と)を含み，またそれらの個数は等しい - |S| \leq 8000
入力
入力は以下の形式で標準入力から与えられる．
S
出力
答えを出力せよ．
入力例 1
)x(
出力例 1
3
)x( → x)( → x() → (x) と操作すればよいです．
このとき，S'=()() であり，これは括弧の対応の取れている文字列です．
入力例 2
()ox
出力例 2
2
入力例 3
()oxo(xxx))))oox((oooxxoxo)oxo)ooo(xxx(oox(x)(x()x
出力例 3
68
Score : 1000 points
Problem Statement
Given is a string S consisting of (, ), o, and x.
You can swap two adjacent characters in S any number of times.
Find the minimum number of swaps needed to satisfy the following condition.
- Let us make a string S' consisting of
(and)by replacing every occurrence ofowith()and every occurrence ofxwith)(in S. Then, S' is a balanced parenthesis string.
Definition of a balanced parenthesis string
A balanced parenthesis string is a string that is one of the following:
- an empty string;
- a string that is a concatenation of s, t in this order, where s and t are some non-empty balanced parenthesis strings;
- a string that is a concatenation of
(, s,)in this order, where s is some balanced parenthesis string.
Under the Constraints of this problem, it is always possible to achieve the objective.
Constraints
- S is a string consisting of
(,),o, andx. - S contains the same non-zero number of
(s and)s. - |S| \leq 8000
Input
Input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
)x(
Sample Output 1
3
We should do as follows: )x( → x)( → x() → (x).
Here, we have S'=()(), which is a balanced parenthesis string.
Sample Input 2
()ox
Sample Output 2
2
Sample Input 3
()oxo(xxx))))oox((oooxxoxo)oxo)ooo(xxx(oox(x)(x()x
Sample Output 3
68