yukicoder 269 見栄っ張りの募金活動
問題
方針
$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$ の組は互いに素)
みたいに.
かなり汎用的な上位概念のような気がするので,問題には関係ないところだけど,このような気付きが得られて勉強になった.