CF 773-D. Two Arrays
解法
集合$ Sについて、$ \sum_{T \subset S} (-1)^{|T|}は$ S = \emptyのとき$ 1、そうでないとき$ 0である。
集合$ A, Bの要素が distinct であることは$ \sum_{T \subset A \cap B} (-1)^{|T|} = 1と同値である。
これを用いると、複数の集合$ A_1, \dots, A_nに対し、集合$ Bが与えられたときに$ A_i \cap B = \emptyとなるような$ A_iが存在するかどうかを高速に判定することができる。
$ A_iの部分集合を全て列挙しておく。$ Bの全ての部分集合$ Tについて、列挙した集合において$ Tが登場する回数に$ (-1)^{T}をかけたものを足し合わせる。これが正なら$ A_i \cap B = \emptyとなるような$ A_iが存在し、$ 0なら存在しない。
尺取り法で最小値が求められる。
重みの小さい順にソートする。$ r = n - 1として、$ l = 0, 1 \dotsの順に次を行う。
$ A_{l + 1, \dots, r}の中に$ A_lと distinct なものがあるなら、そのような条件が保たれる間$ rを$ 1ずつ減らす。減らしきれなくなったときの$ W_l + W_rが答えの候補である。
$ (l, r)が条件を満たすとき、$ l < l'であるような$ l'に対しては$ r' < rとなるような$ (l', r')の組しか考慮しなくてもよいので、上記の方法がうまくいく。