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

yukicoder.me

概要

以下の条件を満たす数列\((A_1, \ldots, A_N)\)は何通りあるでしょうか。\(10 ^ 9 + 7\)で割った余りを求めてください。

• \(A_1 + \ldots + A_N = S\)
• 任意の\(i(1 \le i \le N - 1)\)に対して\(A_i + K \le A_{i + 1}\)

制約：\(2 \le N \le 100\)、\(0 \le S \le 20000\)、\(0 \le K \le 100\)

考察

はじめに思いつくDPは、「\(dp[i][j][k] :=\)\(i\)番目まで確定させ、次に選べる整数が\(j\)以上のときに、合計が\(k\)となるものの通り数」ですが、これだと状態数が\(O(NS ^ 2)\)、各状態について\(O(S)\)通りの選び方があり、全体で\(O(NS ^ 3)\)なので間に合いません。なんとかして状態数を減らす必要があります。

実は\(j\)はなくすことができます。「\(f(i, k) :=\)\(i\)番目まで確定させ、合計が\(k\)となるものの通り数」とおきます。暗黙のルールとして、次に選べる整数は\(0\)以上とします。すると、\(i+1\)番目に\(x\)を選んだときの通り数は\(f(i + 1, k - (x + (K + x)(N - i)))\)と表せます。

数式だとなかなかイメージしづらいので、図を掲載します。

これで状態数を\(O(NS)\)に減らせましたが、各状態について\(O(S)\)通りの選び方があるため、まだ間に合いません。

実は選び方は\(O(S)\)から\(2\)に減らせます。ひとつは「\(0\)を選択する」で、もうひとつは「選択しない」です。選択しないというのは、下の領域を切り取るイメージです。

切り取る操作と\(0\)を選択する操作を繰り返すことで、いずれ\(f(N, S)\)、\(f(N, k)(k \ne S)\)、\(f(i, k)(i \lt N, k \gt S)\)のうちのどれかになります。\(f(N, S)\)のときは数え上げて、それ以外のときは数え上げないようにします。遷移は以下です。

\(f(i, k) = f(i + 1, k + K(N - i) ) + f(i, k + N - i + 1)\)

これで遷移が\(O(1)\)となり、全体が\(O(NS)\)となって間に合います。

実装

int N, S, K;
int dp[110][20010];

int f(int i, int k) {
  if (k > S) return 0;
  if (dp[i][k] != -1) return dp[i][k];
  if (i == N) {
    return dp[i][k] = (k == S);
  }
  int ret = f(i + 1, k + K * (N - i - 1)) + f(i, k + N - i);
  return dp[i][k] = ret % 1000000007;
}

int main() {
  cin >> N >> S >> K;
  for (int i = 0; i < 110; i++) {
    for (int j = 0; j < 20010; j++) {
      dp[i][j] = -1;
    }
  }
  cout << f(0, 0) << '\n';
  return 0;
}

感想

数え上げのための漸化式を立てる系の問題でした。この系統は大好きなので、ぜひとも自力で解けるようになりたいです（解説ACでした）。こういった系統の問題として、他にはベル数やスターリング数、分割数を数え上げる問題などがありますね。