ARC070 D No Need
問題
[改訂第3版]C++ポケットリファレンス (POCKET REFERENCE)
- 作者: 高橋晶,安藤敏彦,一戸優介,楠田真矢,湯朝剛介
- 出版社/メーカー: 技術評論社
- 発売日: 2018/02/15
- メディア: 単行本(ソフトカバー)
- この商品を含むブログを見る
解法
解説の解法。
まず、「カードが(不)必要」がどういう状況か?を考える。
「カードが不必要」とは、カードを含む全てのよい集合が、どれもその総和がとなる場合である。なぜならこの場合、を引いてもを超えるのでよい集合のままだからである。
逆に、「カードが必要」というのはを含む良い集合にその総和が未満のものが存在するということである。この場合、を引けばその良い集合は良い集合でなくなる。
これをまとめると、を含まない部分集合にその総和がのものがある場合、は必要なカードになる。そうでない場合、不必要なカードになる。
DPの部分については典型的なDPなので省略(このDPはTypical DP contest A問題の簡易版)。
解説PDFの「カードiが不要な時、を満たすカードjも不要である」という部分が個人的に引っかかった。
あまり直感的じゃない。
直感的に捉えるなら、「カードjが必要なときとなるカードiも必要である」と考える。
こう考えると、カードjを含む良い集合のうちカードjを抜くと良い集合でなくなる集合においてカードjをカードiに置き換えることで、カードiが必要な気がする。
(例えば和がとなる良い集合にが入っていればを取り除くと良い集合でなくなるし、がなければのかわりにを使えばが必要であることがわかる)
証明すると次のようになる
命題 : が必要 が必要(ただし )
(証明)
前提 :: が必要であることから、ある集合 (Aには含まれない)が存在しその和xはを満たす。
もし、の場合、Aをそのまま用いればよりも必要であることが示せる。
逆に、の場合、Aからを取り除き、を追加すればその集合の和は
となるのでが必要なカードであることがわかる。
(証明終了)
この証明は直感的であるが、解説PDFのように「不必要」ベースで考えた場合の証明も載せておく
命題: が不必要 も不必要 (ただし)
(証明)
前提 :: が不必要であるので、任意のを含まない集合Aとその和xがかのどちらかを満たす。
この前提から「任意のを含まない集合の和が未満か以上である」ことを示せば良い。
を含まない任意の集合のうち、も含まない集合は前提より自明。を含まない任意の集合のうち、を含むものについて考える。を含まず、を含む集合はを含まない集合にを追加したものである。
ここでを含まない集合の制約について考える。
まず前提よりかを満たす。
もし、xがよりも大きい場合、その集合にを追加した集合はになりうる。この集合はを含まない集合なので前提をみたすはずだがとなりうることは前提と矛盾する。
従って、を含まない集合はより小さい。
よって、を含まない集合は未満か以上となる。
これにを追加した集合は未満か以上となる。
故に、を含まない集合は未満か以上となるのでは不要であることがわかる。
(証明終了)
これが証明できればコードは自明
bool need(int index,int N,int K,const vector<ll>& a){ vector<bool> e(K+1,false); e[0] = true; for(int i=0;i<N;i++){ if(i==index) continue; for(int j=K;j>=0;j--){ if(e[j] and j+a[i]<=K) e[j+a[i]]=true; } } for(int i=max<ll>(0,K-a[index]);i<K;i++) if(e[i]) return true; return false; } int main(){ int N,K; cin >> N >> K; vector<ll> a(N); rep(i,N) cin >> a[i]; sort(all(a)); if(need(0,N,K,a)){ cout << 0 << endl; return 0; } if(!need(N-1,N,K,a)){ cout << N << endl; return 0; } int l,r; // l : NG , r : OK l = -1; // NG r = N-1; // OK while(r-l>1){ int mid=(l+r)/2; bool ret = need(mid,N,K,a); if(ret){ r = mid; }else{ l = mid; } } cout << l+1 << endl; }