コンテスト中に真剣に考えて解けなかった 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;
}

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

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

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

問題概要

制約

考えたこと

さらに