けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder TDPC A - コンテスト

部分和問題とほとんど一緒なのだけど、意外と詰まるかもしれない。

問題概要

 N 個の正の整数  a_{0}, \dots, a_{N-1} の中からいくつか選んで総和をとる。作ることのできる整数が何通りあるか求めよ。

制約

  •  1 \le N \le 100
  •  1 \le a_{i} \le 100

考えたこと

この問題とよく似た部分和問題とは次のような問題である。


 N 個の正の整数  a_{0}, \dots, a_{N-1} の中からいくつか選んで総和をとった値を  W にできるかどうかを判定せよ


この問題に対しては次のような配列 dp を定義することで解くことができる。

  •  {\rm dp}\lbrack i \rbrack \lbrack j \rbrack N 個の整数のうち最初の  i 個の整数の中からいくつか選んだ総和を  j にできるかどうか

遷移はこんな感じにできる ( j の範囲に注意)。

dp[i][j] = true のとき
dp[i+1][j] = true;
dp[i+1][j+a[i]] = true;

今回の問題

今回の問題は、具体的な整数  W を作れるかどうかを問うのではなく、作れる整数の個数を求める問題となっている。しかし部分和問題が解けていればほとんど解決済みである。なぜなら、部分和問題を解いて得られた配列 dp を用いることで、次の情報が得られる。


dp[N][j] をみることで、整数  j を作れるかどうかがわかる。


よって、 j = 1, 2, \dots, 10000 について dp[N][j] が True であるような  j の個数を調べればよい。 j の範囲を 10000 までとしたのは、 N \le 100,  p_{i} \le 100 という制約から。

計算量は、作りうる最大の整数を  W (\le 10000) として、 O(NW) となる。

コード

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 入力
    int N; 
    cin >> N;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    // DP テーブル
    int W = 10000;
    vector<vector<bool>> dp(N+1, vector<bool>(W+1, false));
    dp[0][0] = true;

    // ループ
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= W; ++j) {
            if (!dp[i][j]) continue;
            dp[i+1][j] = true;
            if (j+a[i] <= W) dp[i+1][j+a[i]] = true;
        }
    }

    // 答え
    int res = 0;
    for (int j = 0; j <= W; ++j) {
        if (dp[N][j]) ++res;
    }
    cout << res << endl;
}