CodeForces Round #302 Div2 C - Writing Code

問題 : http://codeforces.com/contest/544/problem/C

内容

プログラマーがn人居る．一人行書くことによって，全員でm行書きたい． プログラマーiは１行書くたびに のバグを生み出すので，それを最大b個におさえつつ，m行書くことの出来るパターン数を答える問題．

解法

制約が多くて最初どうしたらいいか面食らったけど，よく考えると個数制限付きの複数ナップサック問題だった． DP[バグの個数][書いた行数]で，前からループを回していけばバグがb個までに書けるコードの行数を列挙することが出来る．最終的には，各バグの個数に対してm行書いた位置，DP[0-b][m]の個数を足し合わせることで答えが出る．

500³になるので，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;
}