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

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

AtCoder ABC 281 D - Max Multiple (緑色, 400 点)

AtCoder AtCoder400点 ABC-D 緑色diff DP 部分和 ナップサックDP N個からK個を選ぶ設定の問題 DP状態:あまり DP状態:個数 制約条件:ちょうどK個 数列 総和を求める 最大スコア 最適化問題

部分和問題の応用問題！

問題概要

N 個の非負整数 A_{0}, A_{1}, \dots, A_{N-1} が与えられれる。

これらの整数から K 個選んで、総和が D の倍数となるようにする。その値として考えられる最大値を答えよ。 D の倍数にするのが不可能な場合は -1 を答えよ。

制約

  • 1 \le K \le N \le 100
  • 1 \le D \le 100
  • 0 \le A_{i} \le 10^{9}

前提知識

この問題を解く前に、次の問題を解けるかどうかを確認しておこう！！

N 個の非負整数 A_{0}, A_{1}, \dots, A_{N-1} が与えられれる。

これらの整数からいくつか選んだ総和を T にすることが可能かどうかを判定してください。

この問題は部分和問題と呼ばれる有名問題で、DP で O(NT) の計算量で解けます。この問題に馴染みのない方は、まずは部分和問題を解く DP を勉強しましょう！！

次のような配列 dp を考えます。

dp[i][v] ← 数列 A の最初の i 個を使って v を作れるかどうか

そして次の遷移式で解けます。計算量は O(NT) です。

  • dp[i+1][v] |= dp[i][v] ( A_{i} を選ばない場合)
  • dp[i+1][v+A[i]] |= dp[i][v] ( A_{i} を選ぶ場合)

詳細については、たとえば次の記事で解説しています。

qiita.com

制約条件 (1)： D の倍数

部分和問題に「総和が D の倍数」という制約をつけて、さらに最大値を求める問題にすると、次のようになります。

N 個の非負整数 A_{0}, A_{1}, \dots, A_{N-1} が与えられれる。

これらの整数からいくつか選んだ総和が D の倍数となるようにする。その値として考えられる最大値を答えよ。 D の倍数にするのが不可能な場合は -1 を答えよ。

さて、「 D の倍数である」という制約は「 D で割ったあまりが 0」と言い換えられます。これに基づいて、次の配列 dp を考えましょう。このように、DP 配列に "あまり" という情報を付与する方法は典型的です。

dp[i][d] ← 数列 A の最初の i 個を使って作れる「 D で割って d あまる数」の最大値 (不可能な場合は -1)

答えは dp[N][0] です。最初はこの配列全体を -1 で初期化しておきます。さらに、初期条件は dp[0][0] = 0 と表せます。

遷移式は次のように表せます。ただし、dp[i][d] の値が -1 の場合はこの遷移を実行しないようにします。

  • dp[i+1][d] = max(dp[i+1][d], dp[i][d]) ( A_{i} を選ばない場合)
  • dp[i+1][(d+A[i])%D] = max(dp[i+1][(d+A[i])%D], dp[i][d]) ( A_{i} を選ぶ場合)

計算量は O(ND) となります。

制約条件 (2)： K 個

最後に「選ぶ数の個数が K 個」という制約条件を加味します。そうすると元の問題と同一となります。配列 dp に添字をさらに付加して、次のように定義してみましょう。

dp[i][k][d] ← 数列 A の最初の i 個の中から、 k 個を選んで作れる「 D で割って d あまる数」の最大値 (不可能な場合は -1)

遷移式は次のように表せます。ただし、dp[i][j][d] の値が -1 の場合はこの遷移を実行しないようにします。

  • dp[i+1][j][d] = max(dp[i+1][j][d], dp[i][j][d]) ( A_{i} を選ばない場合)
  • dp[i+1][j+1][(d+A[i])%D] = max(dp[i+1][j+1][(d+A[i])%D], dp[i][j][d]) ( A_{i} を選ぶ場合)

計算量は O(NKD) となります。

コード

#include <bits/stdc++.h>
using namespace std;
void chmax(long long &a, long long b) { a = max(a, b); }

int main() {
    // 入力
    long long N, K, D;
    cin >> N >> K >> D;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    // DP
    long long dp[110][110][110];
    memset(dp, -1, sizeof(dp));  // 配列全体を -1 で初期化
    dp[0][0][0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= N; ++j) {
            for (int d = 0; d < D; ++d) {
                if (dp[i][j][d] == -1) continue;
                
                // 選ばない場合
                chmax(dp[i+1][j][d], dp[i][j][d]);

                // 選ぶ場合
                chmax(dp[i+1][j+1][(d+A[i])%D], dp[i][j][d] + A[i]);
            }
        }
    }
    cout << dp[N][K][0] << endl;
}