読者です 読者をやめる 読者になる 読者になる

ARC070 D - No Need

競プロ AtCoder

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_i)が降順にソートされていることに注目すると,ある  j があって  \displaystyle t + \sum_{k=j}^{i}a_k >= K かつ  \displaystyle t + \sum_{k=j+1}^{i} < K がなりたつ.この時, a_i > a_j だから, \displaystyle t + \sum_{k=j}^{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;
}