Codeforces #602 Div1 A. Messy

わりと調子のよかった回。
http://codeforces.com/contest/1261/problem/A

問題

同数の閉じカッコと開きカッコの数からなる文字列が与えられる。
この文字列を並べ替え、prefixのうち整合性のあるカッコ列となるものがK個となるようにせよ。

解法

後ろに(K-1)個「()」を並べ、残りを先頭に「((((...))))」としてくっつけよう。
例えばK=4ならこんな感じ。

(((())))()()()

>||cpp
int T;
int N,K;
string S;

void solve() {
int i,j,k,l,r,x,y; string s;

cin>>T;
while(T--) {
cin>>N>>K>>S;
string T;
vector> R;
K--;
FOR(i,N/2-K) {
T+='(';
}
FOR(i,N/2-K) {
T+=')';
}
while(T.size()=0;i--) {
if(S[i]!=T[i]){
for(x=i-1;x>=0;x--) {
if(S[x]!=S[i]) {
R.push_back({x,i});
for(y=x,r=i;y

まとめ

まぁこれは簡単かな…。