ARC056-D No Need
概要
長さN(N <= 5000)の数列を与えられる。それぞれの要素は[1, 10^9]。
入力されるある整数K(1 <= K <= 5000)について、Nの数列の要素で作るすべての部分集合において、部分集合の要素の和がK以上となるのを「良い集合」とします。
- ある数Xを含む部分集合のうちのすべての「良い集合」で、X自身を除いても「良い集合」となるとき、Xは「「良い集合」を作るのに不必要」と言います。
さて、「不必要」な要素はいくつあるでしょう？ちなみに、不必要は独立して判定され、ある数Xが不必要だからと言って、Yが必要かどうかを判定するときにXも部分集合に含めることができます。
ACするまで
1. Kが小さいので、A_iがKよりも大きいときは絶対に必要なので考えなくてよい。
2. A_iが必要のとき、A_iを除いて和が]にある集合は、A_iを加えればよい集合なので、A_iを除いてその区間に和を取れる集合が一つもなければ不必要。 これを愚直に書くと部分点
3. ある数が不必要だとする。それより小さい数もまた不必要。なぜなら、Xが不必要のとき、全体的には]に部分集合の和がないということ。この時、X > YのYに該当する区間
]も当然ない。
4. これって単調性そのものなので二分探索でオーダーが落ちるAC!
考察
この問題には僕の知る限り3~4通り以上の解法がある。まずは最初に書いた単調性を利用した二分探索の説明をする。
ACするまでに書いてあるように、どこが必要不必要の境目なのかはO(log N)回で判別できる。
一回の判別は、
dp[i][j] := i個目の数字まで見て、それらからいくつか選んで和がjになるか？
とbool値のDPをすればいい。ついでにbitsetで高速化しよう。
これはO(NK)なので、全体では
ソースコード：
Submission #7920043 - AtCoder Beginner Contest 056
しかし、上の解法はたまたま単調性があったから使用できただけでいつでもできるわけではない。
次の二つの解法を紹介する。
ある要素だけを抜いたものを大量に求めるとき、次の二つが使われる。
1. DP計算の差し戻し
2. 両側からDP
DPの差し戻し解法
最終的な計算結果から、その要素分だけいい感じに差し戻せば、その要素を抜いた計算結果となる。
今回の場合、最終的な計算結果dp[N]の配列からA[i]を抜いた計算結果を考える。
また、差し戻しを考えるにあたって、それぞれのdp[i][j]は存在しうるだけでなく、何通りの選び方が存在するを記録する！
j >= A[i]の時は、dp[N][j]はdp[N - 1][j - A[i]]の分を足されていて、これがA[i]を使うということなので、さし戻すときはその逆をすればよい。
両側からDP解法
あるA_iを抜いた結果というのは、]の結果と
の結果を使って計算できる。事前に計算すれば、毎回計算しなおさなくて済む。
この問題の場合は、あらかじめ左から、右から順にDPをしてそれをまずメモする。
そして、A_iが不必要というのは]に和をもつ集合がないということを言い換えると、
xを0からK - 1までループを回して、左のDPの結果の和がxになるようなとき、右側のDPで - x, K - 1 - x]]の範囲内に存在するかならば必要と判定できる。これはあらかじめ累積和を計算しておけばO(1)で判別できる。
区間をデリケートに扱う実装法のため実装に気を付けるべし
一言
一粒で三度おいしい
