A – コンテスト 解説 (Typical DP Contest)

2020年3月10日2020年9月2日AtCoder数え上げ,DP,競プロ,ナップサック,合計得点が何通りか

問題へのリンク

問題概要

N 問の問題があるコンテストがあり、i 問目の問題の配点は p_i 点である。合計得点は何通り考えられるか？

制約

• 1 ≤ N ≤ 100
• 1 ≤ p_i ≤ 100

考え方

単純に考えると、正解する問題の選び方で \(2^N\) の全探索をして、合計得点が何種類生じるか探索する方法があります。しかし、これでは \(O(2^N)\) の計算時間になって間に合いません。

p_i や N が小さいことに注目すると、この問題はナップサック問題と同様のDPを用いることで、高速に計算することができます。

i+1 番目の問題を使用して合計得点が sum になるかを考えてみましょう。これは、

• i 番目までの問題によって合計得点が \(sum-p_i\) になり、i+1 番目が解ける
• i 番目までの問題によって合計得点が \(sum\) になり、i+1 番目が解けない

のどちらかが成立すれば成り立ちます。この性質をもちいれば、以下のようなDPで計算することが可能です。

初期化

• dp[ i ][ 0 ] := true

更新

配るDP を用いると以下の通りになります。

• dp[ i ][ sum ] が true なら、dp[ i+1 ][ sum+p[ i ] ] は true
• dp[ i ][ sum ] が true なら、dp[ i+1 ][ sum ] は true

貰うDP を用いると以下の通りです。

• dp[ i ][ sum-p[ i ] ] が true なら、dp[ i+1 ][ sum ] は true
• dp[ i ][ sum ] が true なら、dp[ i+1 ][ sum ] は true

合計得点は最大でも 10000 までにしかなりません。よって、10000×N の計算時間なので十分に間に合います。

実装例

#include <bits/stdc++.h>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;

int N, K;
bool dp[105][11000];
int main() {
    cin >> N;
    vector<int> p(N);
    REP(i, N) cin >> p.at(i);

    REP(i, N + 1) { dp[i][0] = true; }

    REP(i, N) {
        REP(j, 10000) {
            if (dp[i][j]) {  // 配るDP
                dp[i + 1][j] = true;
                dp[i + 1][j + p[i]] = true;
            }
        }
    }

    int ans = 0;
    REP(j, 10000) {
        if (dp[N][j]) ans++;
    }
    cout << ans << endl;
    return 0;
}