ひらめの日常

日常のメモをつらつらと

AtCoder: ABC169-F Knapsack for All Subsets (600)

atcoder 数え上げ dp 集合競技プログラミング解法メモ

問題はこちら

長さ $N$ の正整数列 $A _ {1}, A _ {2}, ..., A _ {N}$ に対して、その部分集合 $T$ を考える。その部分集合に含まれる部分集合 $U$ の和が $S$ になるようなものの個数を求めよ。

考え方

集合単位でDPをしていくことを考える。部分集合に含まれる部分集合という考えが少し難しいが、入力例1を見れば概観が掴める。

dp[i + 1][j]：0-indexで $i$ 番目まで見たとき、和が $j$ となるような $U$ を含む $T$ の場合の数。
A[i] を $U$ に含めないとき、 $U$ の和は $j$ のまま。 $T$ に入れる or 入れないで二通りの可能性がある。よって、dp[i + 1][j] += dp[i][j] *2
A[i] を $U$ に含めるとき、 $U$ の和は $j + A _ {i}$ になる。よって、dp[i + 1][j + A[i]] += dp[i][j]

例えば、 $A$ が $\{4, 2, 1\}$ 、 $S=4$ のときを考えてみる。

dp[1][4]： $T = U$ で、 $\{4\}$ の1通り
dp[2][4]：dp[1][4] で題意を満たしているもの対して、 $T$ に 2を入れると $\{4, 2\}$ となる。入れないと $\{4\}$ となる。いずれも $U$ は $\{4\}$ のままなので題意を満たすが、dp[1][4] のときと違い、 $T$ に $2$ を入れる場合が増えるため、dp[2][4] += dp[1][4] * 2

解答

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const ll mod = 998244353;

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)

int main() {
    ll n, s;
    cin >> n >> s;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    vector<vector<ll>> dp(n + 1, vector<ll>(s + 1));
    dp[0][0] = 1;
    rep(i, n) {
        rep(j, s + 1) {
            dp[i + 1][j] += ((dp[i][j] * 2) % mod);
            dp[i + 1][j] %= mod;
            if (j + a[i] <= s) {
                dp[i + 1][j + a[i]] += dp[i][j];
                dp[i + 1][j + a[i]] %= mod;
            }
        }
    }
    cout << dp[n][s] << '\n';
    return 0;
}

Submission #13986313 - AtCoder Beginner Contest 169