主食は米

主に競プロ備忘録

AGC 020 C - Median Sum

問題概要

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

解法

S_0 = 0 として考える.
ある S_j がいくつかの a_i を含んでいるとする.
このS_j に関して,上記の a_i 以外の全ての {a} を含んでいる和を考えると, {S}を2N-1組として考えることができる.
また, S_all = S_((2N)-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の数は2N-1であり,S_smallにS_0が含まれることを考えれば,
求めるべきはS_largeのうち最小のものであることがわかる.

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

メモ

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

コード

#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;
}