No.50

箱は降順にソートしておく.

$i$ 番目の箱までを使って, $p$ のおもちゃの集合を入れられるかどうかを $B(i, p)$ とし, $q$ のおもちゃの集合を $i$ 番目の箱に入れられるかどうかを $C(i, q)$ とすると,

$$B(i + 1, p \cup q) = B(i, p) \lor C(i + 1, q)$$

となる. ただし, $p \cap q = \emptyset$ である. これを DP で計算し, $B(k, P)$ が真となっている最小の $k$ を求める. ただし, $P$ はすべてのおもちゃの集合である.

集合をビットで表現すると $p$ も $q$ も数字で表せる.