ARC070 D No Need - ちゃっくのメモ帳

問題

作者: 高橋晶,安藤敏彦,一戸優介,楠田真矢,湯朝剛介
出版社/メーカー: 技術評論社
発売日: 2018/02/15
メディア: 単行本（ソフトカバー）
この商品を含むブログを見る

解法

解説の $O(NKlogN)$ 解法。

まず、「カードが(不)必要」がどういう状況か?を考える。
「カードが不必要」とは、カード $a_i$ を含む全てのよい集合が、どれもその総和が $K+a_i$ となる場合である。なぜならこの場合、 $a_i$ を引いても $K$ を超えるのでよい集合のままだからである。
逆に、「カードが必要」というのは $a_i$ を含む良い集合にその総和が $K+a_i$ 未満のものが存在するということである。この場合、 $a_i$ を引けばその良い集合は良い集合でなくなる。

これをまとめると、 $a_i$ を含まない部分集合にその総和 $x$ が $K-a_i \leq x < K$ のものがある場合、 $a_i$ は必要なカードになる。そうでない場合、不必要なカードになる。

DPの部分については典型的なDPなので省略(このDPはTypical DP contest A問題の簡易版)。

解説PDFの「カードiが不要な時、 $a_j \leq a_i$ を満たすカードjも不要である」という部分が個人的に引っかかった。
あまり直感的じゃない。

直感的に捉えるなら、「カードjが必要なとき $a_j \leq a_i$ となるカードiも必要である」と考える。
こう考えると、カードjを含む良い集合のうちカードjを抜くと良い集合でなくなる集合においてカードjをカードiに置き換えることで、カードiが必要な気がする。
(例えば和が $K+a_j-1$ となる良い集合に $a_i$ が入っていれば $a_i (> a_j)$ を取り除くと良い集合でなくなるし、 $a_i$ がなければ $a_j$ のかわりに $a_i$ を使えば $a_i$ が必要であることがわかる)

証明すると次のようになる
命題 : $a_j$ が必要 $\Rightarrow a_i$ が必要(ただし $a_j < a_i$ )
(証明)
前提 :: $a_j$ が必要であることから、ある集合 $A = \{a_{k_1},a_{k_2},...,a_{k_m}\}$ (Aに $a_j$ は含まれない)が存在しその和xは $K-a_j \leq x < K$ を満たす。

もし、 $a_i \not \in A$ の場合、Aをそのまま用いれば $K-a_i < K-a_j \leq x \leq K$ より $a_i$ も必要であることが示せる。
逆に、 $a_i \in A$ の場合、Aから $a_i$ を取り除き、 $a_j$ を追加すればその集合 $A'$ の和 $x'$ は
$K-a_i \leq x' < K - a_i + a_j < K$ となるので $a_i$ が必要なカードであることがわかる。
(証明終了)

この証明は直感的であるが、解説PDFのように「不必要」ベースで考えた場合の証明も載せておく
命題: $a_i$ が不必要 $\Rightarrow a_j$ も不必要 (ただし $a_j < a_i$ )
(証明)
前提 :: $a_i$ が不必要であるので、任意の $a_i$ を含まない集合Aとその和xが $x < K-a_i$ か $K \leq x$ のどちらかを満たす。
この前提から「任意の $a_j$ を含まない集合の和が $K-a_j$ 未満か $K$ 以上である」ことを示せば良い。

$a_j$ を含まない任意の集合のうち、 $a_i$ も含まない集合は前提より自明。 $a_j$ を含まない任意の集合のうち、 $a_i$ を含むものについて考える。 $a_j$ を含まず、 $a_i$ を含む集合は $a_i,a_j$ を含まない集合に $a_i$ を追加したものである。
ここで $a_i,a_j$ を含まない集合の制約について考える。
まず前提より $x < K-a_i$ か $K \leq x$ を満たす。
もし、xが $K-a_i-a_j$ よりも大きい場合、その集合に $a_j$ を追加した集合は $K-a_i <= x$ になりうる。この集合は $a_i$ を含まない集合なので前提をみたすはずだが $K-a_i<=x$ となりうることは前提と矛盾する。
従って、 $a_i,a_j$ を含まない集合は $K-a_i-a_j$ より小さい。
よって、 $a_i,a_j$ を含まない集合は $K-a_i-a_j$ 未満か $K$ 以上となる。
これに $a_i$ を追加した集合は $K-a_j$ 未満か $K+a_i>=K$ 以上となる。
故に、 $a_j$ を含まない集合は $K-a_j$ 未満か $K$ 以上となるので $a_j$ は不要であることがわかる。
(証明終了)

これが証明できればコードは自明

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;
}