yukicoder : No.269 見栄っ張りの募金活動
感動しました。
解法
想定解法とアイデアは変わりませんが, 計算量的に怪しい解法で通しました。
一番大事なアイデアは, 「n 人目の人が前の人に比べて i 円支払うお金を増やしたら, それ以降の人はその i 円の分は絶対に増やさないといけないので, 全体としては (N-n)*i 円払うのと同じじゃん」ということです。
dp[n][y] = (n 人目で残額が y 円になっているような場合の数)とします。このとき, 上の考えを使うと,
dp[n][y] は, dp[n+1][y-i*(N-n)] (0 <= i*(UN-n) <= y) の和になります。ということで, これをメモ化再帰で計算しました。
計算量なんですが, になると思っていますがかかった時間からして多分違いますね…誰か教えて欲しいです。
int N, S, K; const ll MOD = 1e9+7; const int MAXN = 101, MAXS = 20010; ll dp[MAXN][MAXS]; ll dfs(int n, int y) { if (y < 0) return 0; if (n == N-1) return 1; ll& ret = dp[n][y]; if (ret >= 0) return ret; ret = 0; for (int i = 0; i*(N-n) <= y; i++) { ret += dfs(n+1, y-i*(N-n)); } ret %= MOD; return ret; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> S >> K; S -= N*(N-1)/2 * K; memset(dp, -1, sizeof(dp)); cout << dfs(0, S) << endl; return 0; }