ひらめの日常

日常のメモをつらつらと

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

問題はこちら

atcoder.jp

長さ  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