Median Sum [AtCoder Grand Contest 020 C]

https://beta.atcoder.jp/contests/agc020/tasks/agc020_c

前提知識

• bitsetによる64倍高速化
• 動的計画法

解法

https://beta.atcoder.jp/contests/agc020/submissions/1980996

解説放送を見ると、取りうる部分列の総和のなかで、全体の総和/2以上の最小値が答えになる。
取りうる部分列の総和のなかで、全体の総和/2以上の最小値を求めていこう。
このために動的計画法を使う。
「dp[i][j] := i番目までの要素を使って総和をjにできるか」
これをそのまま実装すると状態数だけでO(N^3)くらいかかる。
この高速化のためにbitsetを用いる。
bitsetはシフトやor計算がO(N/64)で出来るため、yes/noの動的計画法では良く高速化に用いられる。
「dp[i] := i番目までの要素を使って総和をjに出来る場合は下j桁目が1となっているビット列」
この更新は以下のようになる
dp[i + 1] = dp[i] or (dp[i] << A[i])
or計算の前半部分は要素A[i]を利用しない場合で後半部分はA[i]を利用して全ての1となっている要素に+A[i]することになる。
このようにシフトを上手く利用することで全体に+xする総和を実現する。
下の実装ではdp配列をswapを使うことで実現している。

あとは、sm/2を下から見ていって最初にビットが1になっている数が答え

int N, A[2020];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    
    int sm = 0;
    rep(i, 0, N) sm += A[i];
 
    bitset<4000001> dp;
    dp.set(0);
    rep(i, 0, N) {
        bitset<4000001> pd;
        pd |= dp;
        pd |= dp << A[i];
        swap(dp, pd);
    }
 
    rep(i, (sm + 1) / 2, 4000001) if (dp[i]) {
        printf("%d\n", i);
        return;
    }
}