Codeforces ECR #147 : E. Rearrange Brackets

6問回の割に5問目まで簡単だった。
https://codeforces.com/contest/1821/problem/E

問題

括弧列が与えられる。
この括弧列のコストは以下のように定義する。

• "()"となっている箇所を削除し、間を詰める。その際、かかるコストはその右側にある閉じ括弧の数である。
• 最適な順で括弧を削除したとき、そのコストの総和の最小値が、括弧列のコストだとする。

最大K回まで、既存の文字を1つ選んで任意の場所に動かせるとする。
括弧列のコストの最小値を求めよ。

解法

コストは言い換えると、開き括弧と閉じ括弧の間にある括弧のペアの数といえる。
文字を動かすと、1つの括弧列のコストを0にできる。
よって各括弧対のコストを求め、大きい順にK個を0に置き換えればよい。

int T,N,K;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>K>>S;
		N=S.size();
		vector<int> pat,cur;
		FOR(i,N) {
			if(S[i]=='(') pat.push_back(i);
			else {
				cur.push_back((i-pat.back())/2);
				pat.pop_back();
			}
		}
		sort(ALL(cur));
		while(cur.size()&&K) {
			K--;
			cur.pop_back();
		}
		ll sum=0;
		FORR(c,cur) sum+=c;
		cout<<sum<<endl;
		
	}
}

まとめ

これなんでKの上限こんな小さかったんだろ。
想定解違ったのかな。