Codeforces ECR #115 : F. RBS

この回は不参加でした。
https://codeforces.com/contest/1598/problem/F

問題

N個の括弧からなる文字列S[i]が与えられる。
これらの(各文字列はそのままで)文字列同士の並び順を任意に入れ替えられるとする。
その時、これらを連結したときにprefixがregular bracket sequenceになるものの最大数を求めよ。

解法

各文字列に対し、閉じ括弧数が開き括弧以上になり、かつその超過分がprefixのうち最大数と一致する回数を求めておく。

あとはbitdpの要領で、すでに連結順を定めた場合文字列群に対し、新規にS[i]を末尾に加えるとregular bracket sequenceとなるprefix数がどうなるか、上記前処理で求めた回数をもとに計算していこう。

int N;
int S[20];
int dp[1<<20];
vector<int> cand[20];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>s;
		cand[i].push_back(0);
		FORR(c,s) {
			if(c=='(') S[i]++;
			else S[i]--;
			
			if(S[i]<-((int)cand[i].size()-1)) cand[i].push_back(0);
			if(S[i]==-((int)cand[i].size()-1)) cand[i].back()++;
		}
	}
	int mask;
	FOR(mask,1<<N) dp[mask]=-(1<<20);
	dp[0]=0;
	int ret=0;
	FOR(mask,1<<N) if(dp[mask]>=0) {
		int sum=0;
		FOR(i,N) if(mask&(1<<i)) sum+=S[i];
		FOR(i,N) if((mask&(1<<i))==0) {
			int mi=((int)cand[i].size()-1);
			if(sum-mi>0) {
				dp[mask|(1<<i)]=max(dp[mask|(1<<i)],dp[mask]);
			}
			else if(sum-mi==0) {
				dp[mask|(1<<i)]=max(dp[mask|(1<<i)],dp[mask]+cand[i].back());
			}
			
			if(sum<=mi) ret=max(ret,dp[mask]+cand[i][sum]);
		}
		ret=max(ret,dp[mask]);
	}
	
	cout<<ret<<endl;
	
}

まとめ

ECRのF問題にしては単純？