Codeforces #302 Div1 A. Writing Code

CF302に参加。Dで典型的なミスをやらかしてレート微減。
http://codeforces.com/contest/543/problem/A

問題

N人のプログラマで合計M行のプログラムを組む。
各プログラマは1行あたりA[i]個のバグを生成する。

合計バグがB個以下となるようなプログラマの作成行数の組み合わせを求めよ。

解法

典型的なDP。
dp[人][残り作成行数][残り許容バグ数]=組み合わせ数、としてDPを行うとO(NMB)に収まる。
DPはdp[i][m][b]=dp[i-1][m][b]+dp[i][m-1][b-A[i]]で更新していくだけ。

int N,M,B;
ll V;
int A[1010],Z;

ll dp[510][510];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>B>>V;
	FOR(i,N) cin>>A[i];
	
	int m,b;
	dp[M][B]=1;
	FOR(i,N) {
		for(m=M;m>=1;m--) {
			for(b=B;b>=A[i];b--) if(dp[m][b]) {
				dp[m-1][b-A[i]] += dp[m][b];
				if(dp[m-1][b-A[i]]>=V) dp[m-1][b-A[i]]-=V;
			}
		}
	}
	
	ll ret=0;
	FOR(b,B+1) ret+=dp[0][b];
	cout<<ret%V<<endl;
	
}

まとめ

O(NM^2B)の人がいることを期待したけど、pretestが強くてそこは皆対策済みであり、Hackは狙えなかった。