UTPC 2014 : G - 唯一の組み合わせ

本番かなり苦労したけど何とか通せた。
http://utpc2014.contest.atcoder.jp/tasks/utpc2014_g

問題

N人のアイドルがそれぞれP球バッティングした。
一部のアイドルは成功した数A[i]が判明しており、残りは不明である。

N人のアイドルのうち、バッティング成功数合計がXとなるようなアイドルの組み合わせが1通りとなるような（未判明の）アイドルバッティング成功数は何通りあるか求めよ。

解法

A[i]=0のアイドルがいると、アイドルの組み合わせが常に複数になりうるので解は0。

まず、判明分アイドルについてDPで処理する。
合計得点0～P点すべてについて、(0通り,1通り,2通り以上)でのいずれであるかを3^(P+1)のマスクで処理、組み合わせが何通りあるか求めていく。

この状態で、同様に未判明分アイドルについて順に0～P点を割り当て、同様に3^(P+1)通りの状態ごとにそれを実現する組み合わせが何通りあるか求めていく。
ただ、毎回0～P点を総当たりするとTLEするので、0点が何人、1点が何人…と求めていくと良い。

int N,X,P;
ll mo=1000000007;
map<int,ll> memo[52][11][55];
int A[55],F;
int p3[15];

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

ll dfs(int cur,int mask,int pre,int fr) {
	int i,n;
	
	if((mask / p3[X])>1) return 0;
	if(memo[cur][pre][fr].count(mask)) return memo[cur][pre][fr][mask];
	if(cur==N) return (mask / p3[X])==1;
	ll ret = 0;
	
	if(A[cur]!=100) {
		int nmask=0;
		FOR(i,X+1) {
			int keep=(mask/p3[i])%3;
			int take=(i-A[cur]<0)?0:((mask/p3[i-A[cur]])%3);
			nmask += min(keep+take,2)*p3[i];
		}
		ret += dfs(cur+1,nmask,1,fr);
	}
	else {
		for(n=pre;n<=P;n++) {
			int nmask=0;
			FOR(i,X+1) {
				int keep=(mask/p3[i])%3;
				int take=(i-n<0)?0:((mask/p3[i-n])%3);
				nmask += min(keep+take,2)*p3[i];
			}
			if(n==pre) ret += dfs(cur+1,nmask,n,fr);
			else ret += dfs(cur+1,nmask,n,N-cur)*C[fr][N-cur] % mo;
		}
	}
	
	return memo[cur][pre][fr][mask] = ret%mo;
}



void solve() {
	int i,j,k,l,r,x,y,t; string s;
	
	FOR(i,CN) for(j=0;j<=i;j++) C[i][j]=(j==0||j==i)?1:(C[i-1][j-1]+C[i-1][j])%mo;
	p3[0]=1;
	FOR(i,12) p3[i+1]=p3[i]*3;
	
	cin>>N>>X>>P;
	
	FOR(i,N) {
		cin>>s;
		if(s=="0") {
			cout<<0<<endl;
			return;
		}
		if(s=="?") A[i]=100, F++;
		else A[i] = atoi(s.c_str());
	}
	sort(A,A+N);
	
	cout<<dfs(0,1,1,F)<<endl;
	
}

まとめ

ずいぶんややこしい状態遷移で、かなり手こずった。