mayoko’s diary

プロコンとかいろいろ。

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) の和になります。ということで, これをメモ化再帰で計算しました。

計算量なんですが,  O(NS\log S)になると思っていますがかかった時間からして多分違いますね…誰か教えて欲しいです。

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;
}