DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 D - DDPC特別ビュッフェ

問題

discovery2016-qual.contest.atcoder.jp

解法

まず部分点解法を考えてみます。

K == 1 の場合は, O(NM) で処理すれば大丈夫です。
K > 1 の場合は,

• 2 回の操作で交換をなかったことにする
• 1 回の操作で交換をなかったことにする

というテクニックが使える(1 回の操作で交換をなかったことにするのは N=M=1 の時はダメだけど, その場合はどうせ値が一定にしかならないので気にしなくて良い)
なので, B がもともと持っていた料理を A が K 回の交換後に持っている個数は, min(K, N, M) であるとわかります。この問題では, A, B が持つ料理の美味しさの合計は一定なので, A がもつ料理の美味しさの合計がわかれば A, B 二人の幸福度もわかります。
あとは dp で, dp[i][j] = (A が i 個の料理を手放して, 美味しさの合計を j にすることは出来るか) という dp をやります。これは, 以下のようにして出来ます。

K = min(K, min(N, M));
dp[0][asum] = true;
for (int i = 0; i < N; i++) {
    for (int k = K-1; k >= 0; k--) for (int j = MAX_SUM-1; j >= A[i]; j--) {
        dp[k+1][j-A[i]] |= dp[k][j];
    }
}
for (int i = 0; i < M; i++) {
    for (int k = 1; k <= K; k++) for (int j = 0; j < MAX_SUM-B[i]; j++) {
        dp[k-1][j+B[i]] |= dp[k][j];
    }
}

交換回数を K に限定して, まず A の料理の数を減らしていき, 次に B の料理を使って料理の数を増やしていく, というようなイメージです。ここまでが部分点解法。

満点解法ではなにをするかというと, dp[j] = (美味しさの合計を j にするような, A が手放す料理の個数の集合) とします。
まず, 1 回も交換をしないと dp[asum] = 1 で, それ以外は 0 です(0 回交換は 1<<0 = 1 なので dp[asum] = 1)。

• A が料理を手放すフェイズでは, 美味しさの合計が j になるような数の集合{el}に対して, dp[j-A[i]] は, {el+1} という集合を手放しても 美味しさの合計が j-A[i] になるということなので, dp[j-A[i]] |= dp[j]<<1 となります。
• B が料理を A に渡すフェイズでは, K 回以上交換するのを許してはいけないので, 各 dp の値の, 1<<(K+1) 以上の部分は無視します。その上で, うえと同様に bit 演算をすれば良いです。dp[j+B[i]] |= (dp[j] & (2^(K+1)-1)) >> 1 ですね。

const int MAX_SUM = 60*22222;
int A[60], B[60];
ll dp[MAX_SUM];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M, K;
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < M; i++) cin >> B[i];
    int asum = 0, bsum = 0;
    for (int i = 0; i < N; i++) asum += A[i];
    for (int i = 0; i < M; i++) bsum += B[i];
    ll ans = 0;
    if (K == 1) {
        for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) {
            ans = max(ans, (ll)(asum-A[i]+B[j]) * (bsum-B[j]+A[i]));
        }
        cout << ans << endl;
        return 0;
    }
    K = min(K, min(N, M));
    dp[asum] = 1;
    for (int i = 0; i < N; i++) {
        for (int j = A[i]; j < MAX_SUM; j++) {
            dp[j-A[i]] |= dp[j]<<1;
        }
    }
    for (int i = 0; i < M; i++) {
        for (int j = MAX_SUM-B[i]; j >= 0; j--) {
            dp[j+B[i]] |= (dp[j] & ((1ll<<(K+1))-1)) >> 1;
        }
    }
    for (int i = 0; i < MAX_SUM; i++) {
        if (dp[i]&1) ans = max(ans, (ll)i*(asum+bsum-i));
    }
    cout << ans << endl;
    return 0;
}