CodeForces Round #302 Div2 C - Writing Code
問題 : http://codeforces.com/contest/544/problem/C
内容
プログラマーがn人居る.一人行書くことによって,全員でm行書きたい. プログラマーiは1行書くたびに のバグを生み出すので,それを最大b個におさえつつ,m行書くことの出来るパターン数を答える問題.
解法
制約が多くて最初どうしたらいいか面食らったけど,よく考えると個数制限付きの複数ナップサック問題だった. DP[バグの個数][書いた行数]で,前からループを回していけばバグがb個までに書けるコードの行数を列挙することが出来る.最終的には,各バグの個数に対してm行書いた位置,DP[0-b][m]の個数を足し合わせることで答えが出る.
5003になるので,PyPyでもしかしたら・・・とおもって提出してみたけど無理だったのでC++で書きなおした.整数の範囲に制限があるのでちゃんとmodをとってあげないと答えが合わず少しハマったのと, 個までのループでいけるかとおもったけど,は0を含むのでb個まで回さないといけないとこにはまった.範囲をちゃんと確認できるようにしたい.
Python版:
#!/usr/bin/env python # -*- coding: utf-8 -*- n,m,b,mod = map(int,input().split()) A = list(map(int,input().split())) dp = [[False for i in range(501)] for j in range(501)] dp[0][0] = 1 for p in range(n): for bug in range(b+1): for write in range(m): if dp[bug][write] is not False: if bug + A[p] <= b: dp[bug + A[p]][write+1] += dp[bug][write] ans = 0 for bug in range(b+1): ans += dp[bug][m] print(ans) print(ans%mod)
C++で通った版:
#include <bits/stdc++.h> using namespace std; typedef vector<int> vi; typedef pair<int, int> pii; typedef long long ll; #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define INF 1e9 int main(){ int n,m,b,mod; cin >> n >> m >> b >> mod ; vector<int> A(n,0); FOR(i,0,n){ cin >> A[i] ; } vector<vector<int> > dp(501,vector<int>(501,0)); dp[0][0] = 1; FOR(p,0,n){ FOR(bug,0,b+1){ FOR(write,0,m){ if(bug + A[p] <= b && dp[bug][write] > 0){ dp[bug+A[p]][write+1] = (dp[bug+A[p]][write+1] + dp[bug][write]) % mod; } } } } int ans = 0; FOR(i,0,b+1) ans = (ans + dp[i][m])%mod; cout << (ans%mod) << endl; return 0; }