No.056 D

まず $a_i \geq K$ の場合は $\{a_i\}$ がよい集合となるので, これを除いた空集合がよい集合とならず, $a_i$ は不必要でない.

$a_i \lt K$ の場合は, $a_j$ ($j \neq i$) の部分集合の和が区間 $[K-a_i, K-1]$ 内の値になる部分集合があれば $a_i$ は不必要でない. そうでなければ不必要.

さて, $a_j$ ($j \neq i$) の部分集合の和が区間 $[K-a_i, K-1]$ のどれかになるかどうかを求める方法であるが, まずはDPを使って前から見ていって $i$ 番まで見たときに和が $j$ になるかどうか $B(i, j)$ を求め, 後ろから見ていって $i$ 番まで見たときに和が $j$ になるかどうか $C(i, j)$ を求める.

これを求めておくと, $a_j$ ($j \neq i$) の部分集合の和が $x$ になるものがあるかどうかは,

$$(B(i-1, 0) \land (C(i+1, K-a_i) \lor C(i+1, K-a_i+1) \lor C(i+1, K-a_i+2) \lor \dots \lor C(i+1, K-1))) \lor \\ \quad (B(i-1, 0) \land (C(i+1, K-a_i-1) \lor C(i+1, K-a_i) \lor C(i+1, K-a_i+1) \lor \dots \lor C(i+1, K-2))) \lor \\ \quad \dots$$

で求めることができる. $C(i+1, K-a_i) \lor C(i+1, K-a_i+1) \lor C(i+1, K-a_i+2) \lor \dots \lor C(i+1, K-1)$ の部分であるが, $C(i, j)$ が true ならば $1$ として累積和を取っておくことで, $C(i+1, K-a_i-1) \lor C(i+1, K-a_i) \lor C(i+1, K-a_i+1) \lor \dots \lor C(i+1, K-2)$ は高速に計算できる.