roiti46's blog

主に競プロ問題の解説を載せてます

Codeforces #302 Div1 A, Div2 C: Writing Code

CF302に参加。Aのみ提出failedで0完。1838 → 1770 (-68)。
前回のSRMといい今回のCFといい0完はつらい。

問題はこちら

問題

n人のプログラマがいてプログラマiはコード1行に必ずai個のバグを仕込む。このn人で合計m行のプログラムを書きたいがバグの総数をb個以下に抑えたい。コーディングの分担としてありうる組み合わせは何通りあるか答えよ。

解法

DPで解ける。
dp[0行目まで書いた][0個のバグ] = 1 として
dp[j行目まで書いた][k個のバグ] += dp[j - 1行目まで書いた][k - ai個のバグ]
という計算をループを回して各プログラマごとに計算していけばいい。
バグの総数がb個を超えないのなら1人のプログラマが書ける行数に制限はないからこれで正しい組み合わせの数が得られる。 最後にm行目書いたときの場合の数の総和を出力すればよい。

#include <iostream>
#define REP(i,a,b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) REP(i,0,a)
using namespace std;

int n, m, b, mod;
int a[501], dp[510][510];

int main(void){
    cin >> n >> m >> b >> mod;
    rep(i, n) cin >> a[i];

    dp[0][0] = 1;
    
    rep(i, n)
        REP(j, 1, m + 1)
            REP(k, a[i], b + 1)
                dp[j][k] = (dp[j][k] + dp[j - 1][k - a[i]]) % mod;

    int ans = 0;
    rep(i, b + 1) ans = (ans + dp[m][i]) % mod;
    cout << ans << endl;
    
    return 0;
}

まとめ

本番はメモ化再帰で書いたが探索漏れがあったため落ちてしまった。DPはまだまだ練習が必要だ。

広告を非表示にする