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

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

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

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

  • 各 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 に対して
  • それ以外の  N-1 個の整数に関する部分和問題を解く
    • 「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;
}

 

解法 (3):単調性を利用して二分探索

次のことが成立する


  •  v が不必要ならば、 v 以上の数はすべて不必要
  •  v が必要ならば、 v 以下の数はすべて必要

よって、二分探索できる。計算量は  O(NK \log N) となる。