yukicoder 269 見栄っ張りの募金活動

2015/08/21 (Fri) yukicoder DP 分割数

問題

問題文

方針

$a_i$ を $i$ 番目の人が入れる金額とする. 条件を式で書くと $a_1+K \leq a_2, a_2+K \leq a_3, \cdots , a_{n-1}+K \leq a_{n}$ となるが,これは $a_1$ を基準に見ると $a_1+K \leq a_2, a_1+2K \leq a_3, \cdots , a_1+NK \leq a_{n}$ となる.

ここで $b_i = a_i - iK$ と置き換えると, $b_1 \leq b_2 \leq \cdots \leq b_n$ と,かなり見通しが良くなる. このとき $a_1 + \cdots + a_n = S$ という条件は, $b_1 + \cdots + b_n = S-(K+2K+ \cdots + NK)$ になる.

$b_i$ のパターンは $a_i$ に一意に復元できるので一対一対応する. なので $b_i$ のパターン数を数える. この数え上げは分割数といい、DP で解ける.蟻本などを参考に実装する. 下のコードは蟻本からコピペした.

実装

ll const mod = 1000000007;

int const MAX_N = 30000;
int const MAX_M = 200;
int n, m;
ll dp[MAX_M + 1][MAX_N + 1];
int solve() {
    dp[0][0] = 1;
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (j - i >= 0) {
                dp[i][j] = (dp[i - 1][j] + dp[i][j - i]) % mod;
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[m][n];
}

signed main(){
    int N,S,K;
    while(cin >> N >> S >> K){
        ::n = S-N*(N-1)/2*K;
        ::m = N;
        cout << solve() << endl;
    }
}

数学っぽく書くと,集合 $A$ に対して $|A|$ が知りたいときに $|A|=|B|$ となる $B$ とその間の全単射を構成して,$|B|$ を数える, というテクなんだろか…

よく考えたら任意の数え上げ DP がこの考え方に基づいているとも言える気がする. rep(i,n) dp[x] += dp[i] は $|A| = |B| = |\bigcup b_i| = \bigcup |b_i|$ (ただし $b_i \subset B$ かつ任意の異なる $b_i$ の組は互いに素) みたいに.

かなり汎用的な上位概念のような気がするので,問題には関係ないところだけど,このような気付きが得られて勉強になった.