本番なんとかブザービートが決まった！

問題概要

赤いベリーと青いベリーとがある。
$N$ 組のビュッフェがあり、それぞれ赤いベリーが $a_{i}$ 個、青いベリーが $b_{i}$ 個入っている。

これらをカゴに詰めていきたい。1 つのカゴにはちょうど $K$ 個のベリーを入れたい。ただし、1 つのカゴには

同じビュッフェのベリー
同じ色のベリー

のどちらかの構成でなければならない。最多で何個のカゴが作れるか？

制約

$1 \le N, K \le 500$
$0 \le a_{i}, b_{i} \le 10^{9}$

考えたこと

直感的には、

赤いベリーだけでできるだけ $K$ 個ずつ詰める
青いベリーだけでできるだけ $K$ 個ずつ詰める

という風にした場合、ほとんどのベリーを詰めることができて、このとき残るのは

$a$ の総和を $K$ で割ったあまり $p$ 個の赤いベリー
$b$ の総和を $K$ で割ったあまり $q$ 個の青いベリー

である。 $p \lt K$ , $q \lt K$ なので、 $p + q \lt 2K$ 。よって、これ以上カゴを増やせるとしたら 1 個だけなのだ。

逆に、もし $s \le p$ , $K - s \le q$ を満たすような $s$ が存在して、ベリーの合計量が $K$ 以上であるようなカゴたちから

(赤いベリー $x$ 個、青いベリー $K-x$ 個)

という組を抽出していって、 $x$ の総和を $K$ で割ったあまりが $s$ になるようにできるならば、カゴを 1 個増やした解を構成できる！

DP へ

このままだと $a_{i} \le 10^{9}$ とかなので大変だ。だがよく考えると、

dp[ i ][ j ] := 最初の i 個のビュッフェからいくつか選んで、その中から適合する (赤いベリー, 青いベリー) を選んだときの、それまでに選んだ赤いベリーの個数の総和を割ったあまりが j にできるかどうか

という風にすればよいので、状態空間の大きさは $O(NK)$ で、計算量も $O(NK^{2})$ とかにできる。

#include <bits/stdc++.h>
using namespace std;

long long N, K;
vector<long long> a, b;
long long solve() {
    long long sa = 0, sb = 0;
    for (int i = 0; i < N; ++i) sa += a[i], sb += b[i];
    long long res = sa/K + sb/K;

    vector<vector<bool> > dp(N+1, vector<bool>(K+1, false));
    dp[0][0] = true;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < K; ++j) {
            if (!dp[i][j]) continue;
            dp[i+1][j] = true;
            for (int aj = 0; aj <= min(K-1, a[i]); ++aj) {
                if (K-aj <= b[i]) dp[i+1][(j+aj) % K] = true;
            }
        }
    }
    bool ok = false;
    for (long long x = 0; x <= K; ++x) {
        if (x <= sa%K && K-x <= sb%K && dp[N][x]) ok = true;
    }
    if (ok) ++res;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); 

    while (cin >> N >> K) {
        a.resize(N); b.resize(N);
        for (int i = 0; i < N; ++i) cin >> a[i] >> b[i];
        cout << solve() << endl;
    }
}

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

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

Codeforces Round #638 (Div. 2) E. Phoenix and Berries (R2400)

問題概要

制約

考えたこと

DP へ