読者です 読者をやめる 読者になる 読者になる

ARC060 C - 高橋君とカード / Tak and Cards

AtCoder 競プロ

問題

arc060.contest.atcoder.jp

考察

まず、「平均がA」というのは「j枚取り出した時、合計がj*A」と言い換えられます。
これにより、各種状態を覚えやすくなりました。
制約が小さいので、必要な要素を覚える以下のようなDPをすれば良さそうです。

dp[i][j][k] := i枚目まで見てj枚取り出した時、合計がk

遷移は素直にカードを取る場合と取らない場合を計算するので、以下のようになります。

 dp[i+1][j+1][k + x[i]] += dp[i][j][k]

 dp[i+1][j][k] += dp[i][j][k]

あとは、1枚以上引いた場合で合計がi*Aとなるパターン数を合計すれば求まります。

コード

int main() {
    int N, A;
    cin >> N >> A;
    vi x(N);
    rep(i, N)cin >> x[i];

    vector<vvll> dp(N + 1, vvll(N + 1, vll(N*A + 10, 0)));
    dp[0][0][0] = 1;
    rep(i, N) {
        rep(j, N) {
            rep(k, N * A) {
                if (k + x[i] <= N * A)
                    dp[i + 1][j + 1][k + x[i]] += dp[i][j][k];
                dp[i + 1][j][k] += dp[i][j][k];
            }
        }
    }

    ll ans = 0;
    REP(i, 1, N+1)
        ans += dp[N][i][i*A];

    cout << ans << endl;

    return 0;
}