yukicoder : No.3058 Deque and Brackets

なるほど。
https://yukicoder.me/problems/no/3058

問題

2N個のクエリが与えられる。
各クエリiは、文字の種別(開き括弧か閉じ括弧)、2つの整数値L[i],R[i]からなる。

文字列Sに対し、各クエリに対してその文字をSの先頭または末尾に追加していくものとする。
その際、先頭ならL[i]、末尾ならR[i]のスコアを得る。
最終的にSが正しい括弧列となるように文字を追加したとき、得られる総スコアの最大値を求めよ。

解法

基本的に開き括弧は先頭、閉じ括弧は末尾に持っていくものとする。
ここで、いくつかその反対にすることで、スコアを増やすことを考える。
逆にクエリを外側から見て行くと、反対にできる個数の上限がわかるので、反対にすることで得られるスコア差分の大きい順に反対のままに残すようにしていこう。

int N;
int C[202020],L[202020],R[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,2*N) {
		cin>>s>>L[i]>>R[i];
		C[i]=s==")";
	}
	int ng=0;
	multiset<int> cand;
	int cnt[2]={};
	ll sum=0;
	for(i=2*N-1;i>=0;i--) {
		cnt[C[i]]++;
		if(C[i]==0) {
			sum+=L[i];
			cand.insert(R[i]-L[i]);
		}
		else {
			sum+=R[i];
			cand.insert(L[i]-R[i]);
		}
		while(cand.size()>min(cnt[0],cnt[1])) cand.erase(cand.begin());
	}
	FORR(c,cand) if(c>=0) sum+=c;
	cout<<sum<<endl;
}

まとめ

結構シンプルに書けるもんだ。