AtCoder Grand Contest 020 C 「Median Sum」

問題文

C - Median Sum

 

(空の列も含む)Aの部分列Xと、AからXを取り除いて出来る部分列Yをペアにすると、ちょうど2^(N-1)ペアが出来る。例えば、A={1,2,3,4}の場合、{}と{1,2,3,4},{1}と{2,3,4},{2}と{1,3,4},{3}と{1,2,4},{4}と{1,2,3},{1,2}と{3,4},{1,3}と{2,4},{1,4}と{2,3}の8ペアが出来る。

Aの各要素の和をS、Xの各要素の和をSX、Yの各要素の和をSYと置く。一般性を失わずSX≦SYと仮定すると、S=SX+SYからSX≦S/2かつSY≧S/2が成り立つ。これがどのペアについても成り立つから、和がS/2以上の部分列と和がS/2以下の部分列は(和がちょうどS/2の部分列を均等に振り分けると)同数存在することがわかる。

よって、部分列の和のうちS/2以上で最小のものを求めればそれが答え。

dp[i][j]:=先頭i項の部分列で、和がjのものが存在するか というDPは2000^3で間に合わない気がするが、bitsetでまとめて更新すると定数倍高速化できて間に合う。