Codeforces #568 Div2 G. Playlist for Polycarp

配点は高いんだけどね。
http://codeforces.com/contest/1185/problem/G2
　

問題

N種類の曲があり、各長さとジャンルが与えられる。
ジャンルは3種類ある。

これらの曲のうち一部を１回ずつ音楽プレイヤーで聞くとき、総時間をT以下にしたい。
また、同じジャンルの曲が２回並ぶことは避けたい。
条件を満たす曲の選択と並び順は何通りか。

解法

並びと長さに関する条件を別々に解き、最後に合わせる。
まず並びを考えよう。
f(a,b,c,x) := 各ジャンルの曲をa,b,c回聞いており、最後に聞いたジャンルがxであるような並び順。同ジャンル内の並びは無視する。

次に、各ジャンル長さの条件に関する準備をする。
g(a,p,q) :=ジャンルaの曲のうち、p曲の合計の長さがqとなる組み合わせ

次に複数ジャンル合計の長さを考える。
h(x,y) := ジャンル1と2の曲で計x曲歌うときの総長がyになるときの組み合わせで、同ジャンル内の並びは区別するがジャンル間の並びは区別しない
k(x,y) := ジャンル1と2と3の曲で計x曲歌うときの総長がyになるときの組み合わせで、同ジャンル内の並びも区別するがジャンル間の並びは区別しない

h(x,y)はg(1,p,q)*g(2,x-p,y-q)*(p!)*(x-p)!だし、k(x,y)はh(p,q)*g(3,x-p,y-q)*(x-p)!である。

最後にジャンル間の並びと長さを考える。
m(x,y) :=ジャンル1と2と3の曲で計x曲歌うときの総長がyになるときの組み合わせで、並びも区別する
m(x,y) = k(x,y) * (f(a,b,c,1)+f(a,b,c,2)+f(a,b,c,3)) (a+b+c=x)で計算していけばよい。

int N,T;
vector<int> L[3];

ll dp[52][52][52][52];
ll dp2[3][52][2505];
ll dp3[52][52][2505];
ll mo=1000000007;
ll fact[55];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>T;
	FOR(i,N) {
		cin>>x>>y;
		L[y-1].push_back(x);
	}
	dp[1][0][0][0]=1;
	dp[0][1][0][1]=1;
	dp[0][0][1][2]=1;
	FOR(i,51) FOR(j,51) FOR(k,51) {
		FOR(x,3) FOR(y,3) if(x!=y) {
			if(y==0) (dp[i+1][j][k][0]+=dp[i][j][k][x])%=mo;
			if(y==1) (dp[i][j+1][k][1]+=dp[i][j][k][x])%=mo;
			if(y==2) (dp[i][j][k+1][2]+=dp[i][j][k][x])%=mo;
		}
	}
	FOR(i,3) {
		dp2[i][0][0]=1;
		FOR(j,L[i].size()) {
			for(x=j;x>=0;x--) for(y=x*50;y>=0;y--) if(dp2[i][x][y]) {
				(dp2[i][x+1][y+L[i][j]]+=dp2[i][x][y])%=mo;
			}
		}
	}
	
	fact[0]=1;
	for(i=1;i<=50;i++) fact[i]=fact[i-1]*i%mo;
	
	int xc,yc,z;
	ll ret=0;
	for(x=0;x<=L[0].size();x++) for(xc=x;xc<=x*50;xc++) if(dp2[0][x][xc]) {
		for(y=0;y<=L[1].size();y++) for(yc=y;yc<=y*50;yc++) if(dp2[1][y][yc]) {
			(dp3[x][y][xc+yc]+=fact[x]*fact[y]%mo*dp2[0][x][xc]%mo*dp2[1][y][yc])%=mo;
		}
	}
	for(x=0;x<=L[0].size();x++) for(y=0;y<=L[1].size();y++) for(xc=0;xc<=50*(x+y);xc++) if(dp3[x][y][xc]) {
		for(z=0;z<=L[2].size();z++) {
			int le=T-xc;
			if(le>=0 && dp2[2][z][le]) {
				ret+=dp3[x][y][xc]*fact[z]%mo*dp2[2][z][le]%mo*(dp[x][y][z][0]+dp[x][y][z][1]+dp[x][y][z][2]);
				ret%=mo;
			}
		}
	}
	cout<<ret<<endl;
}

まとめ

似たようなDPを繰り返すので、ややこしいけど難しくはない。