AGC020 C. Median Sum

問題

N個の整数A_iが与えられる。
空でない部分列のそれぞれの和をすべて考える。これは2^N-1個存在していて、奇数個ある。
この和を昇順で並べたものの中央値を求めよ。

制約

• 1 <= N <= 2000
• 1 <= A_i <= 2000

解法

実は「選んだ部分列」と「選ばなかった部分列」が対応関係になっている。
全部の和をSとし、選んだ部分列の和をaとすると、選ばなかった部分列はS-aになるが、部分列の和をソートしたとき、aが中央より左になるなら、S-aは中央より右になるような対応になる(逆も)。

この対応関係を考えると、中央値は「S/2以上で一番小さい値」であることがわかる(Sが奇数の場合は、S/2を超える最小の整数で考えればよい)。

これを求めるには、値が作れるか見ればいいので、「dp[s] := 部分列の和がsのものが作れるか否か(0/1)」を作って、上記の条件を満たす値を探せばよい。
dpは最大4,000,000で、bitsetを使って以下のようにシフト演算すると高速に計算できる。

dp[0] = 1;
rep(i,N){
  dp |= dp << A[i];
}