問題
提出コード
サンプル3についてなんとなく考えると、不必要なカードは2,3,4の3つであり、これはすべてのカードの中で小さい3つを選ぶ形になります。
ということで、なんとなく、昇順にソートすると前の方が不必要、後ろの方が必要なカードになりそうなことがわかります。このことが正しいことを示します。
今、が必要なカードだったとします。すると、次の条件を満たす、
番目のカードを含む部分集合
が存在します。
に含まれるカードの数の総和は
以上で、そこから
を引いたものが
このとき、に含まれる、
以上の数字のカードはすべて必要なカードになります。なぜなら、
の総和から
を引いたものが
未満になるので、
以上の数字を引いた際ももちろん
未満になります。
そして、に含まれない、
以上の数字が書かれているカードは、
とそのカードを置き換えてあげると、
の総和が
以上、そこから置き換えたカードの数字を引いてあげると
未満になります。
ということで、を昇順でソートしてあげれば、前半が不必要なカード、後半が必要なカードに綺麗にわかれます。
とすると、二分探索で、不必要なカードのうち最大のものの場所がわかれば、答えをすぐに求めることができます。
あとは、番目のカードが必要であるかどうかを調べればいいのですが、DPを用いて求めることができます。
番目のカードを含む部分集合
について、その総和が
以上
未満になるような部分集合がつくれた場合、
番目のカードは必要なカードになります。これを利用します。
番目までのカードを用いて、総和が
となるような部分集合をつくれるかどうか
としておけば、番目のカードを必ず使用するように工夫しつつこのDPをとくことで(あらかじめ足しておいて、
番目だけDPの遷移をスキップすればよいです)、
ただし
は
を満たす
の部分で、作成できるという情報が存在していれば、番目のカードは必要なカードになります。
とここで、は
まで制約があるのですが、
となる
番目のカードはすべて必要なカードとなるので、
の
の部分は、
だけ用意しておけば大丈夫です。なぜなら、そして
番目のカード1枚の部分集合はどちらもよい集合となるため、
番目のカードを捨てると、これは空集合となり、よい集合ではなくなってしまいます。よって、
となる
番目のカードはDPをせずとも必要なカードになります。
ということで、このDPを解きつつ二分探索することで、この問題の答えをで求めることができます。
