はまやんはまやんはまやん

hamayanhamayan's blog

自然数の収納方法 [yukicoder No.535]

https://yukicoder.me/problems/no/535

解法

https://yukicoder.me/submissions/183394

まず、この問題を見てまず思いつくのが、O(N^3)のDPかなと思う。
dp[i][j][k] := A[0]=iでA[j]まで埋まってて、A[j] = kの組合せ
これだと、間に合わないのでなんとかしたい。

制約の中で重要な制約がある。
A[N-1] - (N-1) < A[N]
この制約を満たさないのは、A[N]=1,A[N-1]=Nだけであり、それ以外は全て満たす。
つまり、A[N-1]はA[N]によってダメなのは一通りだけでそれ以外は特に考えなくて良いということ。
これを上手く利用する。

dp[i][j] := A[i]=jである組合せ(A[0]はA[N]と考える)
dp[i][j] = sum_{k=1..min(N, j + max(1, i - 1))}dp[i-1][k]
このようなdpが考えられる。
この時、sumを累積和で事前に求めておくと、このDPは空間、時間ともに計算量O(N^2)となる。

このDPを上手く使って、数え上げるが、2回に分ける。

dp1 : A[N] = any -> 配置 -> A[N-1] = any
最初と最後が何でも良い配置の数え上げ。
dp[0][1]~dp[0][N]を1で初期化して、dp処理後にdp[N-1][1]~dp[N-1][N]の総和をとる

dp2: A[N] = 1 -> 配置 -> A[N-1] = N
これはダメなパターン。
dp[0][1]のみ1で初期化して、dp処理後にdp[N-1][N]を答えから引く。

これで答えが得られる。

int N;
//---------------------------------------------------------------------------------------------------
mint dp[2020][2020];
mint sm[2020][2020];
void dodp() {
    rep(i, 1, N) {
        sm[i - 1][0] = 0;
        rep(j, 1, N + 1) sm[i - 1][j] = sm[i - 1][j - 1] + dp[i - 1][j];
        rep(j, 1, N + 1) dp[i][j] = sm[i - 1][min(N, j + max(1, i - 1) - 1)];
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    
    // dp1: An = any -> ... -> An-1 = any
    rep(i, 0, 2020) rep(j, 0, 2020) dp[i][j] = 0;
    rep(j, 1, N + 1) dp[0][j] = 1;
    dodp();

    mint ans = 0;
    rep(j, 1, N + 1) ans += dp[N - 1][j];

    // dp2: An = 1 -> ... -> An-1 = N
    rep(i, 0, 2020) rep(j, 0, 2020) dp[i][j] = 0;
    dp[0][1] = 1;
    dodp();

    ans -= dp[N - 1][N];

    cout << ans.get() << endl;
}