AtCoder AGC #020 : C - Median Sum

いまいちな出来。
https://agc020.contest.atcoder.jp/tasks/agc020_c

問題

N個の正整数A[i]が与えられる。
これらの空でない部分集合の総和(2^N-1)通りを昇順に並べたとき、中心に来る要素はなにか。

解法

空集合も合わせると、(2^N)通りのうち(2^(N-1)+1)番目を答える問題となる。

全要素の和をSと置く。
いくつか選んだ和がaのとき、逆に残りの要素の和はS-aとなる。
よって、(2^N)個の値において、aが1個あればその分(S-a)も1個ある。
言い換えれば数列中においてSの半分以下の要素1個につき半分以上の要素が1個あることになる。

よって、(2^(N-1)+1)番目はあり得る総和aにおいて、Sの半分以上である最小値を求めればよい。
各総和の登場回数を求めるのはオーバーフローしてしまい時間内には無理だが、ある総和の存在チェックならbitsetで並列化し高速化できる。

int N;
int A[2020],S;
bitset<4400000> B;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	B[0]=1;
	FOR(i,N) {
		cin>>A[i];
		S+=A[i];
		B |= B<<A[i];
	}
	
	for(i=(S+1)/2;i<=S;i++) if(B[i]) return _P("%d\n",i);
	
}

まとめ

自分はbitsetによるビット並列化は嫌いでないしむしろ好きなんだけど、嫌がる人も多いのかな。