TopCoder SRM 528 Div1 Medium SPartition

これは割とすんなりだった。
http://community.topcoder.com/stat?c=problem_statement&pm=11634

問題

oとxで構成されたN文字の文字列が与えられる。
この文字列を2つに分割(分割の詳細な定義は問題文参照)したとき、両文字列が一致するような分割の仕方を列挙せよ。

解法

N<=40なので、分割後の文字列は20文字以下である。
よって分割後の文字列の候補を2^20通り列挙し、各候補文字列を生成する分割法をDPで数え上げればよい。

これだけだとO(2^N * N^3)かかるが、分割後候補の2^20通りの文字列のうち、oとxの数は元文字列の半分でないといけないのでDPを行う回数はもっと絞り込める。

ll dpdp[2][41][41];

class SPartition {
	public:
	long long getCount(string s) {
		int L=s.size();
		int i,x,y,mask;
		ll ret=0;
		
		FOR(mask,1<<(L/2)) {
			if(__builtin_popcount(mask)*2!=count(s.begin(),s.end(),'o')) continue;
			ZERO(dpdp);
			dpdp[0][0][0]=1;
			ll tot=0;
			FOR(i,L) {
				int cur=i%2,tar=cur^1;
				ZERO(dpdp[tar]);
				tot=0;
				FOR(x,min(i+1,L/2+1)) FOR(y,min(i+1,L/2+1)) if(dpdp[cur][x][y]) {
					tot+=dpdp[cur][x][y];
					if(x<L/2 && ((mask>>x)&1)==(s[i]=='o')) dpdp[tar][x+1][y]+=dpdp[cur][x][y];
					if(y<L/2 && ((mask>>y)&1)==(s[i]=='o')) dpdp[tar][x][y+1]+=dpdp[cur][x][y];
				}
				if(tot==0) break;
			}
			if(tot) ret += dpdp[L%2][L/2][L/2];
		}
		return ret;
	}
}

まとめ

今回はすんなり。