Codeforces #594 Div1 B. The World Is Just a Programming Task (Hard Version)

えらく苦戦。
https://codeforces.com/contest/1239/problem/B

問題

カッコ列Sが与えられる。
このうち2文字を入れ変えた文字列をS'とする。
S'をローテーションしてできる文字列のうち、カッコの対応が矛盾なくつくものを最大化したい。

入れ替える位置と、矛盾ないローテーション数の最大値を答えよ。

解法

まず閉じカッコと開きカッコの数が等しいことは確認しておく。
開きカッコを+1、閉じカッコを-1として、prefix i文字の数値の合計S[i]を(i,S[i])に置く作業を繰り返し、それらを線でつないでみる。
閉じカッコと開きカッコの入れ替えは、ある区間を+2持ち上げるか-2下げることに相当する。
その後、最下段にある頂点数を最大化したい。
よって各位置を持ち上げ場所にしたとき、どこを持ち下げ場所にするかをSegTreeで求めればよい。

int N;
string S;

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=1<<30;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=comp(v,val[entry]); //上書きかチェック
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<20> st;
int T[702020],P[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	
	S+=S;
	FOR(i,2*N) {
		T[i+1]=T[i];
		if(S[i]=='(') T[i+1]++;
		else T[i+1]--;
		st.update(i+1,T[i+1]);
	}
	
	if(T[2*N]!=0) {
		cout<<0<<endl;
		cout<<"1 1"<<endl;
		return;
	}
	
	int C[4]={};
	vector<int> neg,zero,pp;
	FOR(i,N) {
		x=st.getval(i,i+N);
		if(x==T[i]) {
			P[i]=1;
			zero.push_back(i);
			zero.push_back(i+N);
		}
		if(x==T[i]-1) {
			P[i]=2;
			neg.push_back(i);
			neg.push_back(i+N);
		}
		if(x==T[i]-2) {
			pp.push_back(i);
			pp.push_back(i+N);
		}
		C[P[i]]++;
	}
	sort(ALL(zero));
	sort(ALL(neg));
	sort(ALL(pp));
	int ma=C[1],L=0,R=0;
	FOR(i,zero.size()/2) {
		int lt=zero[i],rt=zero[i+zero.size()/2-1];
		int cnt=lower_bound(ALL(neg),rt)-lower_bound(ALL(neg),lt);
		
		//cout<<lt<<" "<<rt<<" "<<cnt<<" "<<C[1]+C[3]-cnt<<endl;
		if(C[2]-cnt>ma) {
			ma=C[2]-cnt;
			L=(lt+N-1)%N;
			R=(rt+1+N-1)%N;
		}
	}
	FORR(n,neg) zero.push_back(n);
	sort(ALL(zero));
	FOR(i,zero.size()-1) {
		int lt=zero[i],rt=zero[i+1];
		if(l>=N) break;
	
		int cnt=lower_bound(ALL(pp),zero[i+1])-lower_bound(ALL(pp),zero[i]);
		if(C[1]+cnt>ma) {
			ma=C[1]+cnt;
			L=(lt+N)%N;
			R=(rt+N-1)%N;
		}
		
	}
	
	cout<<ma<<endl;
	cout<<(L+1)<<" "<<(R+1)<<endl;
	
	
}

まとめ

Bの割にコード量多いな。