一見すると計算量が厳しい問題にも見える。ちょっとした発想の転換が必要になる。

問題へのリンク

問題概要

正の整数 $N, M, S$ が与えられる。次の条件を満たす $N^{2}$ 個の整数 $x_{1}, x_{2}, \dots, x_{N^{2}}$ の組が何個あるかを 100000 で割った値を求めよ。

$1 \le x_{1} \lt x_{2} \lt \dots \lt x_{N^{2}} \le M$
$x_{1} + x_{2} + \dots + x_{N^{2}} = S$

制約

[tex 1 \le N \le 7]
$1 \le M \le 2000$
$1 \le S \le 3000$

考えたこと

安直に考えると、次のような DP をしたくなる。

dp[i][j][s]：数列 $x$ の最初の $i$ 個について、末尾の値が $j$ ( $x_{i} = j$ ) であり、総和が $s$ であるような場合の数

しかし、これだと $O(N^{2}M^{2}S)$ の計算量とな理、間に合わない。ここでは発想を変えて、問題を次のように言い換えてみよう。

$1, 2, \dots, M$ の中から、 $N^{2}$ 個の整数を選んで、総和を $S$ にする方法が何通りあるか

これは、ごく標準的な部分和問題であり、次のような DP で解ける。

dp[v][k][s]： $1, 2, \dots, v$ の中から $k$ 個選んで、総和を $s$ にする方法の個数

$O(N^{2}MS)$ の計算量となり、これならば間に合う。

コード

#include <bits/stdc++.h>
using namespace std;
const int MOD = 100000;

int main() {
    int N, M, S;
    cin >> N >> M >> S;

    // 1, 2, ..., M から N^2 個選んで総和を S にする方法の数え上げ
    vector dp(N*N+1, vector(S+1, 0LL));
    dp[0][0] = 1;
    for (int v = 1; v <= M; v++) {
        vector nex(N*N+1, vector(S+1, 0LL));
        for (int k = 0; k <= N*N; k++) {
            for (int s = 0; s <= S; s++) {
                // v を選ばない
                nex[k][s] += dp[k][s], nex[k][s] %= MOD;

                // v を選ぶ
                if (k+1 <= N*N && s+v <= S) {
                    nex[k+1][s+v] += dp[k][s], nex[k+1][s+v] %= MOD;
                }
            }
        }
        swap(dp, nex);
    }
    cout << dp[N*N][S] << endl;
}

別解

この問題は分割数を用いることで、より高速な $O(N^{2}S)$ の計算量で解くこともできる。詳しくは次の記事を参照。

drken1215.hatenablog.com

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

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

JOI 予選 2009 F - ビンゴ (AOJ 0537) (1D, 難易度 7)

問題概要

制約

考えたこと

コード

別解