TopCoder SRM 688 Div1 Hard ParenthesesDiv1Hard

こんな簡単に解けるの…。
https://community.topcoder.com/stat?c=problem_statement&pm=14231

問題

括弧で構成された文字列Sがある。
この文字列を括弧の対応が取れた２つに分割する。
(両文字列中の文字の相対的な位置関係は変えてはならない)

括弧からなる文字列xに対し、深さD(x)とコストC(x)を次のように定義する。

• D("")=0, C("")=0
• D("("+x+")") = D(x) + 1, C("("+x+")") = C(x) + D("("+x+")")^2
• D(xy) = max(D(x), D(y)), C(xy) = C(x) + C(y)

２つの文字列のコストの和の最小値を求めよ。

解法

外側の括弧から内側に向けて深さが深くなっていくなら簡単だが、こちらは逆に内側から外側に向けて深くなる。
想定解はDPかもしれないが、以下を参考にすると２つの文字列の分解は容易にできる。
Algorithms Weekly by Petr Mitrichev: A greedy week

Sを２つの文字列A,Bに分解する際、先頭から１文字ずつA,Bのどちらに振り分けるか考える。
常にAにおける開き括弧の超過数がBと同等かBより1だけ大きくなるようにすると、結果的に開き括弧の超過数が両者で均等化され、結果的に各括弧の深さが浅くなってコストが下がるようだ。

A,Bに分解したら後はコストを求めるだけ。

int from[80][80];
int to[80][80];


class ParenthesesDiv1Hard {
	public:
	
	pair<int,int> score(string s) {
		int cur=0,i;
		if(s=="") return {0,0};
		FOR(i,s.size()) {
			if(s[i]=='(') cur++;
			else {
				cur--;
				if(cur==0) {
					auto rr=score(s.substr(1,i-1));
					rr.first++;
					rr.second+=rr.first*rr.first;
					auto r2=score(s.substr(i+1));
					rr.first=max(rr.first,r2.first);
					rr.second += r2.second;
					return rr;
				}
			}
		}
	}
	
	int minCost(string s) {
		string B,R;
		int NB=0, NR=0;
		FORR(r,s) {
			if(r=='(') {
				if(NB==NR) B+=r, NB++;
				else R+=r, NR++;
			}
			else {
				if(NB>NR) B+=r, NB--;
				else if(NR==0) return -1;
				else R+=r, NR--;
			}
		}
		if(NB || NR) return -1;
		return score(B).second+score(R).second;
	}
}

まとめ

キャラが全問同じなのはよくあるけど、題材が同じなのは珍しい。