AGC 020 C - Median Sum (700)

• 問題

問題概要

N個の自然数から成る数列a[i] (1<=i<=N) が与えられる.
a[i] の部分列の和 S_1, S_2, ... , S((2^N)-1) の中央値(すなわち{S}を昇順に並べた時のS(2^N-1)を求めよ.
1 <= N, a_i <= 2*10³

解法

S_0 = 0 として考える.
ある S_j がいくつかの a_i を含んでいるとする.
このS_j に関して,上記の a_i 以外の全ての {a} を含んでいる和を考えると, {S}を2^N-1組として考えることができる.
また, S_all = S_((2^N)-1) , ペアのうち小さい方をS_small, 大きい方をS_largeとして,
S_small + S_large = S_all , S_small <= S_largeから, S_small <= floor(S_all / 2), S_large >= ceil(S_all / 2) ... (*)となる.
全てのペアについてS_small, S_largeの数は2^N-1であり,S_smallにS_0が含まれることを考えれば,
求めるべきはS_largeのうち最小のものであることがわかる.

また,和をある値にするような部分列は存在するか？というのは典型的なDPの問題であり,
dp[i][j] := (a_k(1 <= k <= i)までを用いて和をjにできるか) とおけば組める.
が,N³では間に合わないので,bitsetを用いて高速化すればO(N³/64)で間に合う.

メモ

Sを二組に分ける考察ができなかった.

追記
べき集合 ( 2^N ) について,
A or B = 2^N (全体) , A and B = φ(空集合) であるようなものを考えると良い感じの不変条件が出ることがあるみたいだ.
今回は和が一定だった.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 2003;
const ll lmod = 1e9+7;

bitset<MAX_N * MAX_N> dp;
int a[MAX_N];

int main(){
  int N; cin >> N ;
  rep(i,N) scanf("%d",a+i);
  int _sum = 0;
  rep(i,N) _sum += a[i];
  dp[0] = 1; 
  rep(i,N) dp |= (dp << a[i]);
  REP(i,(_sum+1)/2,_sum+1){
    if(dp[i]){
      cout << i << endl;
      return 0;
    }
  }
  return 0;
}