ABC056 D - No Need

問題
提出コード
サンプル3についてなんとなく考えると、不必要なカードは2,3,4の3つであり、これはすべてのカードの中で小さい3つを選ぶ形になります。
ということで、なんとなく、昇順にソートすると前の方が不必要、後ろの方が必要なカードになりそうなことがわかります。このことが正しいことを示します。
今、が必要なカードだったとします。すると、次の条件を満たす、番目のカードを含む部分集合が存在します。

• に含まれるカードの数の総和は以上で、そこからを引いたものが未満になる

このとき、に含まれる、以上の数字のカードはすべて必要なカードになります。なぜなら、の総和からを引いたものが未満になるので、以上の数字を引いた際ももちろん未満になります。
そして、に含まれない、以上の数字が書かれているカードは、とそのカードを置き換えてあげると、の総和が以上、そこから置き換えたカードの数字を引いてあげると未満になります。

ということで、を昇順でソートしてあげれば、前半が不必要なカード、後半が必要なカードに綺麗にわかれます。
とすると、二分探索で、不必要なカードのうち最大のものの場所がわかれば、答えをすぐに求めることができます。
あとは、番目のカードが必要であるかどうかを調べればいいのですが、DPを用いて求めることができます。
番目のカードを含む部分集合について、その総和が以上未満になるような部分集合がつくれた場合、番目のカードは必要なカードになります。これを利用します。
番目までのカードを用いて、総和がとなるような部分集合をつくれるかどうか
としておけば、番目のカードを必ず使用するように工夫しつつこのDPをとくことで(あらかじめ足しておいて、番目だけDPの遷移をスキップすればよいです)、
ただしは を満たす
の部分で、作成できるという情報が存在していれば、番目のカードは必要なカードになります。
とここで、はまで制約があるのですが、となる番目のカードはすべて必要なカードとなるので、のの部分は、だけ用意しておけば大丈夫です。なぜなら、そして番目のカード1枚の部分集合はどちらもよい集合となるため、番目のカードを捨てると、これは空集合となり、よい集合ではなくなってしまいます。よって、となる番目のカードはDPをせずとも必要なカードになります。

ということで、このDPを解きつつ二分探索することで、この問題の答えをで求めることができます。