予鈴

アウトプットとメモ書きの中間みたいな記事がたくさん出ます。

D - Redistribution

問題

整数 $S$ が与えられる。総和が $S$ となる数列の個数を求めよ.
ただし、すべての項は3以上の整数である.

解法

・ $S \leq 2000$ であるから、数え上げる数列の最大の長さは $S$ を超えない.
・また、ある項 $u$ を使うとすると、 $S - u$ までの長さが求まっていれば良い.
・動的計画法.
1. $u$ をなめながら $dp$ の全状態を更新していくver
2.ある状態 $s$ から $u$ を使う推移を考えるver
後者のほうが好きです
・時間計算量は $O(S^2)$

スマートな方法

式変形を考えると計算量が改善できるらしい.すごい.
以下では、下のコードから計算量の改善を考えてみる.
$dp[i + s]$ は $dp[s]$ からの推移で求まることがわかる.
したがって、 $dp[i + s] = \displaystyle {\sum^{i + s - 3}_{ j = 0}}dp[j]$
これより
$dp[i + s] - dp[i + s - 1] = dp[i + s - 3]$
が導ける.つまり、シグマが消えて計算量が改善できる.
$j \leq s$ までのすべての $j$ を用いて更新する必要はなく、直前のやつだけを使うと十分であることがわかる.
改善したやつ

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
constexpr Int mod = 1e9 + 7;
int main(){
    Int S; cin >> S;
    vector<Int>dp(S+1,0LL);
    dp[0] = 1;
    for(int s = 0; s <= S; ++s){
        for(int i = 3; i <= S; ++i){
            if(dp[s] == 0)continue;
            if(s + i <= S)
                dp[i + s] += dp[s], dp[i + s] %= mod;
        }
    }
    cout << dp[S] << endl;
}

参考

けんちょんさんの記事を参考にしました。感謝です。
drken1215.hatenablog.com