結果

問題 No.269 見栄っ張りの募金活動
ユーザー startcppstartcpp
提出日時 2015-08-22 12:55:16
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 10 ms / 5,000 ms
コード長 1,903 bytes
コンパイル時間 411 ms
コンパイル使用メモリ 56,148 KB
実行使用メモリ 18,896 KB
最終ジャッジ日時 2024-07-16 01:33:09
合計ジャッジ時間 1,189 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 4 ms
11,772 KB
testcase_04 AC 5 ms
10,344 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 4 ms
15,740 KB
testcase_07 AC 10 ms
18,896 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 1 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 1 ms
6,944 KB
testcase_13 AC 3 ms
8,004 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 3 ms
7,592 KB
testcase_16 AC 2 ms
6,944 KB
testcase_17 AC 2 ms
6,940 KB
testcase_18 AC 5 ms
14,480 KB
testcase_19 AC 3 ms
8,104 KB
testcase_20 AC 2 ms
6,944 KB
testcase_21 AC 2 ms
6,940 KB
testcase_22 AC 3 ms
7,688 KB
testcase_23 AC 2 ms
6,944 KB
testcase_24 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*考察フェーズ
・問題言い換え：A[1] + A[2] + … + A[N] = S, A[i+1] >= A[i] + K, A[0] >= 0を満たす整数列Aの個数を求めよ。
・同値な問題  ：A[1] + A[2] + … + A[N] = S - KN(N-1)/2, A[i+1] >= A[i], A[0] >= 0を満たす整数列Aの個数を求めよ。

・大きさNの広義単調増加な非負整数列のうち、合計値がMであるものの個数をF(N, M)とすると、
  F(N, M) = F(N-1, M) + F(N-1, M-1) + … + F(N-1, 0)
  とな…らないね！？（A[i+1] >= 0という条件なら簡単なのに…)
  
・A[i]を決める。A[i+1] >= 0という条件に変換したとき、同値な問題はどうなるか…
→A[i+1]～A[N]の値が全て-A[i]される
→(N - i - 1) * A[i]だけ合計値を減らしたものになる。
・A[i] + A[i+1] + … + A[N] = M, A[i+1] >= A[i], A[j+1] >= A[j]
  ⇔ A[i+1] + … + A[N] = M - (N - i) * A[i], A[i+1] >= 0, A[j+1] >= A[j]

・これより、
  F(N, M) = F(N-1, M) + F(N-1, M - N) + F(N-1, M - 2N) + … + F(N-1, M - CN) (Cは、M - CN >= 0を満たす整数の最大値)
  となる。

・さらに
  F(N, M) = F(N, M-N) + F(N-1, M)
  とでき、高速化が可能。
  
・「前に決めた値」を保持しなくても良くなった（「前に決めた値」が常に0だとした場合の問題に漸化式的に置換）
・状態数は、O(NS). 遷移は、O(1)→計算量O(NS).
*/

//実装フェーズ(→↓↑→→↓→→↑↑↓↓←→←→)
#include<iostream>
using namespace std;

int n, s, k;
long long f[101][20001];

long long F(int N, int M) {
	if (N < 0 || M < 0)
		return 0;
	return f[N][M];
}

int main() {
	cin >> n >> s >> k;
	s -= k * n * (n - 1)/2;
	
	f[0][0] = 1;
	for( int N = 1; N <= n; N++ ){	//残り項数
		for( int M = 0; M <= s; M++ ){	//残り値
			f[N][M] = F(N, M-N) + F(N-1, M);
			f[N][M] %= 1000000007;
		}
	}
	cout << F(n, s) << endl;
	return 0;
}
0