読者です 読者をやめる 読者になる 読者になる

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

競プロ yukicoder

yukicoderは解説に溢れているので書く必要はあまり無いような気もします。

問題

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

考察

普通のDPのようですが、払わないといけない金額が前の人に依存するため、この制約では計算量が大きくなりすぎます。

dp[i][j][k] := i-1番目の人がj円払い、合計金額がkの時のパターン数 とすると、 O(N*S^{2})となりメモリが足りません。
iとi+1で配列の再利用をしても、 O(S^{2})で厳しそうです。

ここで、i番目の人が払った際の全体の動きに目を向けます。
K=1の時、i番目の人が1円を払うと、残りの人は最低でも2円以上を払わないといけません。
そのため、合計金額は 1 + (N-i)*2円増加します。

一般にt円払ったとすると t * (N-i)*(t+k)円増加します。
全体の金額のみを保存すれば事足りるので、tを保存せずに漸化式が作れます。
よって、メモリ消費は  O(N * S) で済み、なんとかなりそうです。

普通に配るDPをするとTLEしそうですが、 O(N*S^{2})
要らないループをスキップすると間に合ってしまいました。

TLEしそうだけど通ったコード

int main() {
    int N, S, K;
    cin >> N >> S >> K;

    vvll dp(N+1, vll(S+10,  0));
    dp[0][0] = 1;

    rep(i, N) {
        REP(j, 0, S+1) {
            if(dp[i][j] == 0)
                continue;

            int rem = N - i - 1;
            REP(k, 0, S+1) {
                if ((ll) j + k + rem * (k+K) > S)
                    break;
                dp[i + 1][j + k + rem * (k+K)] += dp[i][j];
                dp[i + 1][j + k + rem * (k+K)] %= MOD;
            }
        }
    }

    cout << dp[N][S] << endl;

    return 0;
}

TLEしないために

蟻本にもありますが、k-1円払った時の結果に、さらに1円払えばk円払ったことになるので、これを利用して計算量を落とします。

実装としては、i番目の人がK円ぴったり払った時と、それを利用して追加で1円ずつ払っていくイメージです。
処理の都合上、最初の人だけは初期化時に入れてしまいます。
なお、「ある人がk円払った時は、残りの人もとりあえずk円払う」とすることで処理が簡単になっています。

int main() {
    int N, S, K;
    cin >> N >> S >> K;

    vvll dp(N+1, vll(S+10,  0));
    for(int i=0; i<S+10; i+=N)
        dp[0][i] = 1;

    rep(i, N-1) {
        REP(j, 0, S+1) {
            int rem = N - i - 1;

            if(0 <= j - K*rem)
                dp[i + 1][j] += dp[i][j - K * rem];
            if(0 <= j - rem)
                dp[i + 1][j] += dp[i + 1][j - rem];

            dp[i+1][j] %= MOD;
        }
    }

    cout << dp[N-1][S] << endl;
    
    return 0;
}

感想

熟考が必要で結果のコードは短い、とても良い問題でした。