問題概要

$N$ 枚のカードがあり，カード $i$ には正の整数 $a_i$ が書かれている．以下の条件を満たす $i~(1\leq i\leq N)$ の個数を求めよ．

条件

カード$i$以外の$N-1$枚のカードの部分集合で，書かれている数の総和Sumが$K-a_i \leq Sum\leq K-{1}$となる部分集合は存在しない．

制約

$1\leq N,K\leq 5000$
$1 \leq a_i \leq 10^9$

解法

集合$A\subseteq\{1,\ldots,n\}$に対して

$S_{{A}}$:$A$の部分集合のカードに書かれた総和として作ることができるK未満の数の集合

とする．$S_{\{1,\ldots,n\}-\{i\}}$をすべての$i$について求めれば，判定は$O(NK)$で可能．

一般に$S_{A}$と$S_{B}$から$S_{A\cup B}$を求める操作は$O(K^2)$の計算量のDPとなるが，$S_{A}$と$S_{\{j\}}$から$S_{A\cup\{j\}}$を求めることは$O(K)$で可能である．この性質から，$S_{\{1,\ldots,n\}-\{i\}}$たちは平方分割により$O(N^{1.5}K)$で計算できる．bitsetのおかげでいわゆる$"O(N^{1.5}K/64)"$となり間に合う．