けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 020 C - Median Sum (黄色, 700 点)

コンテスト中に真剣に考えて解けなかった 700 点問題!!!

問題へのリンク

問題概要

 N 個の整数  A_1, \dots, A_N があたえられる。 N 個の整数の部分和は空集合に対応するものを除くと  2^{N} - 1 個ある。

このうちの中央値を求めよ。

制約

  •  1 \le N \le 2000
  •  1 \le A_i \le 2000

考えたこと

とりあえず部分和問題みたいなことをしたくなる。すなわち

  • dp[ i ][ val ] := 最初の i 個のみを見て、val を作る方法が何通りあるか

というのを求めておいて、ここから中央値を探す方針が思い浮かぶ。しかし val は最悪で  O(NA) くらいの値になる。よってこの DP は  O(N^{2}A) の計算時間を必要としてしまう。。。

しかし dp の値が「v を作る方法が何通りあるか?」という形だと難しいけど、dp の値が「v を作ることができるか?」だったら bit ベクター高速化ができる。

さらに

そこでもう少し色々できないかと考えてみる。今回、すべての整数の総和を  S とすると、

  • 部分集合  A とその補集合  B のペアを考えたとき、 {\rm sum}(A) + {\rm sum}(B) = S である

ということがわかる。よって、

  • 上半分は  \frac{S}{2} 以上
  • 下半分は  \frac{S}{2} 以下

という感じになっていることがわかる。ここから言えることは

  • 求める値は、大きい方半分のうちの最小値
  • つまり、(S + 1)/2 以上の値の中での最小値

ということになる。こうして、当初の DP を

  • dp[ i ][ v ] := 最初の i 個の整数で v を作れるか?

とすればよいことがわかった。これを bitset を用いて高速化して求める。

#include <iostream>
#include <bitset>
#include <vector>
using namespace std;
const int MAX = 4040404;

int main() {
    int N; cin >> N;
    vector<int> A(N);
    long long sum = 0;
    for (int i = 0; i < N; ++i) cin >> A[i], sum += A[i];

    bitset<MAX> dp;
    dp[0] = 1;
    for (int i = 0; i < N; ++i) {
        dp |= (dp << A[i]);
    }
    long long res;
    for (res = (sum+1)/2; res < MAX; ++res) {
        if (dp[res]) break;
    }
    cout << res << endl;
}