kmjp's blog

競技プログラミング参加記です

yukicoder : No.287 場合の数

★2.5位?
http://yukicoder.me/problems/763

問題

正整数Nが与えられる。
a+b+c+d+e+f+g+h=6Nとなるよう、各変数a~hに0~Nの範囲の整数を割り当てる組みわせは何通りあるか答えよ。

解法

dp[処理した変数の数][変数の和] := 組み合わせ数
としてDPしていけばよい。

ll dp[10][6001];
int N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	dp[0][0]=1;
	FOR(i,8) FOR(j,6*N+1) FOR(x,N+1) if(j+x<=6*N) dp[i+1][j+x] += dp[i][j];
	cout<<dp[8][6*N]<<endl;
}

まとめ

問題文も解法もえらくシンプルだけど、何を意図した問題だったんだろう?
和が7Nだったら重複組み合わせの問題になったのだけど。