TopCoder SRM 613 Div2 Hard TaroCards

また無駄オーバーフローで苦戦してしまった…。
http://community.topcoder.com/stat?c=problem_statement&pm=13015

問題

N枚のカードがあり、それぞれ2種類の数字が書かれている。
1つ目の数字は、各カード1～Nの異なる数字が書かれている。
2つ目の数字は、各カード1～10の数字が書かれており、こちらは同じ数字が複数カードに書かれていても良い。

これらのカードの部分集合のうち、カードに書かれた数字の数がK以下であるものの数を答えよ。

解法

2つ目の数字が10までという時点で、bitDPが思いつく。

以下の手順では、bitmaskを定め、2番目の数字がbitmask中立っているbitに対応する数字と一致するカードのみを対象にして数え上げていく。

各bitmaskにおいて以下を処理する。

• 2番目の数字のうちbitが立っているものを対象とする。
• その2番目の数字を持つカード群について、1つ目の数字がbitmaskに含まれるものと含まれないもので数え上げる。
• その2番目のカードを最低1枚選び、かつ合計で選ぶ数字の数がK以下になるようDPしていけばよい。

const int CN=55;
ll C[CN][CN];

class TaroCards {
	public:
	vector<int> V[10];
	int N;
	long long getNumber(vector <int> first, vector <int> second, int K) {
		N=first.size();
		int i,j,x,mask;
		
		FOR(x,CN) C[x][0]=C[x][x]=1;
		for(i=1;i<CN;i++) for(j=1;j<i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j]);
		if(K>=max(N,10)) return 1LL<<N;
		
		FOR(i,10) V[i].clear();
		FOR(i,N) V[second[i]-1].push_back(first[i]-1);
		
		ll ret=0;
		FOR(mask,1<<10) {
			if(K-__builtin_popcount(mask)<0) continue;
			
			int bi=0,kk;
			ll dp[11][51];
			ZERO(dp);
			dp[0][K-__builtin_popcount(mask)]=1;
			
			FOR(i,10) if(mask & (1<<i)) {
				int inc=0,exc=0;
				
				ITR(it,V[i]) if(*it<=10 && (mask & (1<<*it))) inc++;
				exc=V[i].size()-inc;
				
				FOR(x,exc+1) {
					FOR(kk,51) {
						if(x==0) dp[bi+1][kk]+=((1LL<<inc)-1)*dp[bi][kk];
						else if(x>0 && kk-x>=0) dp[bi+1][kk-x]+=(1LL<<inc)*C[exc][x]*dp[bi][kk];
					}
				}
				bi++;
			}
			FOR(x,51) ret+=dp[bi][x];
		}
		return ret;
	}
};

まとめ

途中、「bitmaskは10bitまでだ」と油断していたら1つ目のカードの数字分左シフトしたら32bit以上左シフトしたりして凡ミスしてしまった。