ARC070 D - No Need
解法(証明?)
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; }