ARC060 - C

高橋君とカード / Tak and Cards

問題ページ

精進再開
しばらくやってなかったけどすんなり DP が浮かんで安心

dp[i][n][S] : i 番目までの数から n 個選んで和を S にする方法の総数

とすれば配る DP で

dp[0][0][0] = 1
dp[i + 1][n][S] += dp[i][n][S]
dp[i + 1][n + 1][S + x[i + 1]] += dp[i][n][S]

最後に 1 <= n <= N に対して dp[N][n][n * A] の総和を求めれば，それが答え．

N = 50 だし O(N⁴) でいけるなと思って適当に書いたけどもっといい解法あるかな？と思って editorial 見たら O(N³) でもできるらしい．まだまだですね

ll dp[64][64][64 * 64];

int main() {

    cin.tie(0);
    ios::sync_with_stdio(false);

    int N, A;
    cin >> N >> A;

    vector<int> x(N + 1, 0);
    for (int i = 1; i <= N; i++) 
        cin >> x[i];

    sort(all(x));

    dp[0][0][0] = 1;
    for (int i = 0; i < N; i++) {
        for (int n = 0; n <= i; n++) {
            for (int S = 0; S <= 50 * 50; S++) {
                ll comb = dp[i][n][S];
                dp[i + 1][n][S] += comb;
                dp[i + 1][n + 1][S + x[i + 1]] += comb;
            }
        }
    }

    ll ans = 0;
    for (int n = 1; n <= N; n++)
        ans += dp[N][n][n * A];

    cout << ans << endl;

    return 0;
}