Kodamanと愉快な仲間たち : S - 五等分の分銅

最初だいぶ遠回りしちゃった。
https://www.hackerrank.com/contests/kodamanwithothers/challenges/1of5-weight

問題

重さ1/1,1/2,1/3,1/4,1/5の重りがa,b,c,d,e個ある。
これらの一部を使い、重さの合計をp/qにしたい。
各重さの選び方の組み合わせは何通りか。

解法

p/qをまず分母60に通分してしまおう。
あとは単なる個数制限付きナップサック問題になる。

int C[5],p,q;
ll dp[6][6100000];
ll S[6100000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,5) cin>>C[i];
	cin>>p>>q;
	if(60%q) return _P("0\n");
	p*=60/q;
	
	dp[0][0]=1;
	FOR(i,5) {
		x=60/(i+1);
		for(j=0;j<=6000000;j++) {
			S[j]=dp[i][j];
			if(j>=x) S[j]+=S[j-x];
			y=j-x*C[i];
			if(y-x<0) dp[i+1][j]=S[j];
			else dp[i+1][j]=S[j]-S[y-x];
		}
	}
	cout<<dp[5][p]<<endl;
	
	
	
}

まとめ

最初色々場合分けで解こうとしてしまった。