この問題は、まずサンプルケース、特にSample 3の
6 20
10 4 3 10 25 2
を見て実験すると、どうやら要らなくなるのは2,3,4の3つだということがわかります。
ここで、直観的に「不要な数がk個存在するなら、それは小さい順からk個である」という仮説が立ちます。(この仮説はSample 1で1,4,3のうちの1が不要になっていることからも補強されます。)
この仮説は正しいのですが、それを証明していきます。
この仮説を示すには、ある数が必要になるとき、それ以上の数は必要になることを示します。厳密には、ある数a,b(a<=b)が存在するとき、「aが必要」⇒「bが必要」を示します。
ここで、Sをある集合で、Sは良い集合ではないものの、S+aはよい集合になるものとします。aが必要であることから、このような集合は存在します。
(i)bがSに含まれない場合
この場合は、良い集合ではないSにbを加えることで良い集合になるので、bは必要です。
(ii)bがSに含まれる場合
Sからbを除いた集合をS'とします。
すると、S'+a+bがよい集合であり、S'+b(=S)がよい集合ではないことがわかります。ここで、S'+aの要素の総和はS'+bの要素の総和以下であることはa<=bより明らかなので、S'+aは良い集合ではないことが示せます。あとは、この集合にbを加えるとS'+a+bの良い集合になることが分かるので、bは必要です。
これで、先ほどの仮説は証明できました。
ここまで来ると、ある数が必要か不必要かのボーダーラインを二分探索することができます。
ある数xが必要になるかどうかは、その数を除いた数の集合からいくつか要素を選んで、総和がK-x以上K未満である集合を作れるかどうか判定すればO(NK)で判定可能です。(dp[i]={総和がiである部分集合が存在するか})
先ほどの仮説より、ある数tが必要ならt以上の要素全てが必要、逆にtが不要ならt以下の要素全てが不要(先ほどの対偶、「bが不要」⇒「aが不要」)ということがわかります。
なのでtがどこから必要なのかは二分探索することができ、この問題をO(NK log N)で解くことができました。
昨日のばちゃで久々に解いたらすらっと解けたのが嬉しかったのと、理詰めの流れが好きだったので。
初めての記事なのでまだ不慣れな部分もあると思いますが、こんな感じでしょうか…?
