2020-10-06

AtCoder ABC 056 D - No Need (ARC 070 D) (2D, 黄色, 600 点)

AtCoder AtCoder600点 ABC-D 累積和テク:左右両端からの累積和や累積結果を前処理累積和各kに対して N個のものうち1個を変更・削除したものを解く戻すDP DP データ構造テク：前処理条件の言い換え二分探索 bitベクター高速化単調性に着目する数列シーケンシャルDP 部分和極大なものを考える黄色diff ARC-D 累積和テク:累積和や累積結果を前処理しておく NoviSteps2D

めっちゃいろんな解法がある！

各 i に対して i 番目を抜いた部分の解を求める系
- 左右から累積和
- 戻す DP
単調性を見抜いて二分探索

問題へのリンク

問題概要

$N$ 個の整数 $a_{1}, \dots, a_{N}$ がある。これらの整数の部分集合のうち、数の総和が $K$ 以上になるものをよい集合と呼びます。

各カード $i$ に対して、そのカードが不必要であるとは、「カード $i$ を含む任意のよい集合に対して、その集合からカード $i$ を除いたものもよい集合」であることを指すものとする。

不必要なカードの枚数を求めよ。

制約

$1 \le N, K \le 5000$

考えたこと

「不必要」という条件がわかりにくいので、まずはこれをわかりやすく言い換える！！そうするとこうなる

整数 $a_{i}$ が不必要であることは、次の条件と同値。

それ以外の $N-1$ 個の整数の部分集合であって
総和が $K-a_{i}$ 以上 $K$ 未満となるものが存在しない

このように言い換えると、「部分和問題に対するよくある DP」が適用できそうな気持ちになってくる。しかし、愚直にやると

各 $i$ に対して
それ以外の個の整数に関する部分和問題を解く
- 「dp[ v ] := 整数 v を作れるか」としてそれを更新していく DP

という風になる。しかしこれでは $O(N^{2}K)$ の計算量となって間に合わない (bit ベクター高速化で間に合わせることはできる)。そこで、さまざまな工夫を行う。

解法 (1)：左右両端から累積した結果を得る

一般に $N$ 個の対象物に対して $i$ 番目の要素を除いた $N-1$ 個についての解を得たいとき

左右両端からの累積結果を前処理で求めておく
全体についての結果から $i$ 番目の結果を引く (DP でこれをやるのが「戻す DP」)

まずは、左右両端から累積結果を求めるのをやってみる。

left[ i ][ v ] := 左から i 個について、総和を v にできるかどうか
right[ i ][ v ] := 右から i 個について、総和を v にできるかどうか

を DP によって求めておく。これを用いることで、問題は次のようになる。

各 i に対して
left[ i ][ u ] が True であるような任意の u (< K) について
v = K - u - a[ i ], ..., K - u - 1 のいずれについても、right[ N - i - 1 ][ v ] が False であるかどうかを判定する

v = K - u - a[ i ], ..., K - u - 1 のいずれについても、right[ N - i - 1 ][ v ] が False であるかどうかを判定する部分については、配列 right[ N - i - 1 ] の累積和を求めておくことで高速に判定できる。

全体の計算量は

前処理： $O(NK)$
各 i に対する判定は、各 u について $O(1)$ でできるので、 $O(NK)$

よって、 $O(NK)$ で求められる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    vector<vector<bool>> left(N+1, vector<bool>(K+1, false)), right = left;
    left[0][0] = right[0][0] = true;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= K; ++j) {
            if (left[i][j]) {
                left[i+1][j] = true;
                if (j+a[i] <= K) left[i+1][j+a[i]] = true;
            }
            if (right[i][j]) {
                right[i+1][j] = right[i][j];
                if (j+a[N-i-1] <= K) right[i+1][j+a[N-i-1]] = true;
            }
        }
    }

    int res = 0;
    for (int i = 0; i < N; ++i) {
        vector<int> sum(K+2, 0);
        for (int j = 0; j <= K; ++j) sum[j+1] = sum[j] + right[N-i-1][j];
        bool ok = true;
        for (int u = 0; u < K; ++u) {
            if (!left[i][u]) continue;
            if (sum[K-u] - sum[max(0, K-u-a[i])] > 0) ok = false;
        }
        if (ok) ++res;
    }
    cout << res << endl;
}

解法 (2)：戻す DP

戻す DP をやってみる。

dp[ i ] := i を作る方法が何通りあるか

という配列に対して、以下の操作を定義する。なお、配列 dp は bool 配列ではなく「何通りあるか」という風にすることで、戻す DP ができるようにする。

値 v を追加する (add)

配列 dp から配列 ndp への更新は次のように表せる。

ndp[ i ] = dp[ i ] + dp[ i - v ]

この処理は in-place に実装することもできる。

値 v を削除する (sub)

上の操作の逆変換をとると次のようになる。

dp[ i ] = ndp[ i ] - dp[ i - v ]

この処理も in-place に実装することもできる。

まとめ

以上の操作を実装しておけば、

add(dp, a[i]) を各 i に対して実施する
各 i に対して sub(dp, a[i]) を実施して判定し、add(dp, a[i]) して戻す

という風にできる。計算量は $O(NK)$ となる。

#include <bits/stdc++.h>
using namespace std;

template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() const { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr istream& operator >> (istream &is, Fp<MOD>& x) noexcept {
        is >> x.val;
        x.val %= MOD;
        if (x.val < 0) x.val += MOD;
        return is;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

const int MOD = 1000000007;
using mint = Fp<MOD>;

void add(vector<mint> &dp, int v, int K) {
    for (int i = K; i >= v; --i) dp[i] += dp[i-v];
}

void sub(vector<mint> &dp, int v, int K) {
    for (int i = v; i <= K; ++i) dp[i] -= dp[i-v];
}

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    vector<mint> dp(K+1, 0);
    dp[0] = 1;
    for (int i = 0; i < N; ++i) add(dp, a[i], K);

    int res = 0;
    for (int i = 0; i < N; ++i) {
        sub(dp, a[i], K);
        bool ok = true;
        for (int j = K-1; j >= 0 && j >= K-a[i]; --j) if (dp[j] != 0) ok = false;
        if (ok) ++res;
        add(dp, a[i], K);
    }
    cout << res << endl;
}