TopCoder SRM 709 Div1 Hard ColorfulParentheses

定数倍が意外に厳しい。
https://community.topcoder.com/stat?c=problem_statement&pm=14434

問題

N文字の括弧からなる文字列Sを考える。
i番目の文字には色C[i]が塗られているとする。
各色の文字に開き括弧か閉じかっこを割り当てたとき、S全体が整合性のとれた括弧列を成すような組み合わせは何通りあるか。

解法

半分全列挙で解く。
まず前半後半両方に登場する色を覚えておこう。

次に前半分について登場する色の種類cに対し2^c通り括弧の割り当てを総当たりし、開き括弧の余剰分と、前後半両方に登場する色の括弧の割り当て方を覚えておく。
続けて同様に、後ろ半分について、文字列の後ろから開き括弧と閉じかっこを逆にみなして、やはり同様に2^c通り括弧の割り当てを総当たりし、開き括弧の余剰分と、前後半両方に登場する色の括弧の割り当て方を覚えておく。

あとは両者開き括弧の余剰分の数が等しく、色に対する括弧の割り当てが等しいケースを前後半掛け合わせて総和を取ればよい。
意外にTLEが厳しく、若干枝刈りを頑張る必要があるようだ。

vector<int> S[2][26];
int mask[1<<25];
int rev[51];
int NB;

class ColorfulParentheses {
	public:
	int N;
	ll B;
	vector<int> C;
	
	void dfs(int cur,int cnt,int id,ll open,ll close) {
		if(cur==N) {
			S[id][cnt].push_back(open&((1<<NB)-1));
		}
		else {
			if(id==0) {
				int c=rev[C[cur]];
				if(!(close & (1LL<<c))) dfs(cur+1,cnt+1,id,open|(1<<c),close);
				if(!(open & (1LL<<c)) && cnt) dfs(cur+1,cnt-1,id,open,close|(1<<c));
			}
			else {
				int c=rev[C[2*N-1-cur]];
				if(!(open & (1LL<<c))) dfs(cur+1,cnt+1,id,open,close|(1<<c));
				if(!(close & (1LL<<c)) && cnt) dfs(cur+1,cnt-1,id,open|(1<<c),close);
			}
			
		}
	}
	
	long long count(vector <int> C) {
		int i,j;
		int cnt[2][52]={};
		
		this->C=C;
		N=C.size()/2;
		FOR(i,26) S[0][i].clear(), S[1][i].clear();
		
		FOR(i,N) cnt[0][C[i]]++, cnt[1][C[i+N]]++;
		
		B=0;
		NB=0;
		FOR(i,51) if(cnt[0][i] && cnt[1][i]) rev[i]=NB, NB++;
		int x=0,y=0;
		FOR(i,51) if(cnt[0][i] && cnt[1][i]==0) rev[i]=NB+x, x++;
		FOR(i,51) if(cnt[0][i]==0 && cnt[1][i]) rev[i]=NB+y, y++;
		
		B |= 1LL<<i, 
		dfs(0,0,0,0,0);
		dfs(0,0,1,0,0);
		
		ll ret=0;
		FOR(i,26) {
			FORR(r,S[0][i]) mask[r]++;
			FORR(r,S[1][i]) ret+=mask[r];
			FORR(r,S[0][i]) mask[r]--;
		}
		return ret;
		
	}
}

まとめ

最初再帰なしで解いたら1.2sかかった。
なんでDFSで速くなったかよくわからない…。そこそこ枝刈りが効いたのかなぁ。