[yukicoder] No. 1238 選抜クラス

2020年9月27日2020年12月12日

問題

方針

動的計画法を使って考えます。\( A_i \) の平均が \( K \) 以上ということは、\( A_i – K \) の総和が \( 0 \) 以上ということなので、\( d(i, j) \) を \( i \) 人まで生徒を調べたとき、総和が \( j \) となる組み合わせの数とします。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll mod = pow(10, 9) + 7;
const int l = 2 * 100 * 100 + 1;
const int m = 100 * 100;
ll dp[101][l + 1]{};

int main() {
    int N, K;
    cin >> N >> K;
    ll A[N];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        A[i] -= K;
    }
    dp[0][m] = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < l; j++) {
            dp[i + 1][j] += dp[i][j];
            dp[i + 1][j] %= mod;
            if (j + A[i] < 0 || j + A[i] >= l) continue;
            dp[i + 1][j + A[i]] += dp[i][j];
            dp[i + 1][j + A[i]] %= mod;
        }
    }
    ll s = 0;
    for (int i = m; i < l; i++) {
        s += dp[N][i];
        s %= mod;
    }
    cout << s - 1<< "\n";
    return 0;
}

参考