ARC070 D - No Need

arc070.contest.atcoder.jp

解法（証明？）

a[i] を降順にソートする．
今，a[i] が不必要かどうかを判定したいとする．この時，Si := a[1] + a[2] + ... + a_[i] とおく．
また，a[n] から a[i + 1] までの和で表現できる K 未満の数がわかっているとする．（dpで保存）
その中の任意の数 t について，t + Si < K であるならば，それは不必要な数である．
必要条件は明らか．なぜなら，t + Si < K が成り立つならば，a[i] を用いた和で K 以上となるものは，存在しないか，あるいはもともと K 以上であるかのどちらかだからである．
十分条件について示す．これは対偶を取れば良い．つまり，「必要な数ならば t + Si >= K が成り立つ」を示せば良い．
t + a[i] >= K ならば，a[i] を取り除けば K 未満となる和の作り方が存在することになるので，t + a[i] < K であると考えて良い．
ここで，数列 a が降順にソートされていることに注目すると，ある j があって t + (a[j] + ... + a[i]) >= K かつ t + (a[j + 1] + ... + a[i]) < K がなりたつ．この時，a[i] > a[j] だから， t + (a[j] + ... + a[i - 1]) < K が成り立つ．これは a[i] が必要な数であることに他ならない．
以上より，示された．

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
using ll = long long;
 
int main() {
    int N, K;
    cin >> N >> K;
    vector<int> a(N);
    for(int i=0; i<N; ++i) {
        cin >> a[i];
    }
    ll sum = accumulate(a.begin(), a.end(), 0LL);
    sort(a.rbegin(), a.rend());
    int res = 0;
    vector<bool> dp(K);
    dp[0] = true;
    for(int i=0; i<N; ++i) {
        bool f = false;
        for(int j=0; j<K; ++j) {
            f |= dp[j] && j+sum >= K;
        }
        if(!f) {
            res++;
        }
        sum -= a[i];
        for(int j=K-1-a[i]; j>=0; --j) {
            dp[j+a[i]] = dp[j+a[i]] | dp[j];
        }
    }
    cout << res << endl;
}