全国統一プログラミング王決定戦本戦 E問題：Erasure

問題. Erasure

左から 1 から $n$ までの番号が付いた $n$ 個のブロックが一列に並んでいる．長さ $k + 1$ 以上の連続する区間のブロックを削除という操作をすべてのブロックが無くなるまで繰返し行う．そのような操作の集合が何通りあるのかを求めよ．

制約： $1 \le n \le 5,000$ ，　 $0 \le k \le n - 1$

解法．動的計画法

解くことが出来なかったので想定解法を参考にした．
　　全国統一プログラミング王決定戦本戦解説 @maroonrk

dp[l][r] を各操作の左端が $l$ 以下で $[0, r]$ までのブロックがすべて削除されるような操作の集合の数，として動的計画法を行う．このとき，答えは dp[n - 1][n - 1] となる．ここで，dp[l][r] の値を求めることを考える．まず初めに $l + k > r$ の場合は，操作の左端が $l$ となるような操作を行うことができないので，dp[l][r] = dp[l - 1][r] となる．
次に $l + k \le r$ の場合は，操作の左端が $l$ となるいくつかの操作を操作の集合に加えることを考慮して，
　dp[l][r] $=$ dp[l - 1][r] $+ (2^{r - (l + k) + 1} - 1)$ dp[l - 1][r] $+ \sum_{i = l - 1}^{r - 1} 2^{r - (l + k)}$ dp[l - 1][i]

となる．右辺の第1項目は操作の左端が $l$ よりも小さい操作からなる集合の数で，第2項目は既に $[0, r]$ のすべてのブロックが消されている集合に左端が $l$ となる操作を加えた集合の数である．左端が $l$ で右端が $r$ 以下の操作は $r - (l + k) + 1$ 通りあり，条件を満たす操作の加え方は空集合を除いた $2^{r - (l + k) + 1} - 1$ 通りある．第1項目と第2項目を合わせて $2^{r - (l + k) + 1}$ dp[l - 1][r] としてもよいが説明のために別々にしている．第3項目は左端が $l$ で右端が $r$ となる操作を加えることによって初めて $[0, r]$ のすべてのブロックが削除される集合の数を考えている．
上の漸化式を愚直に計算すると $O(n^3)$ 時間必要だが，2 の冪乗を前もって求め，第3項目は各 $l$ に対して累積和を更新しながら計算することによって $O(n^2)$ 時間で求めることができる．

計算時間： $O(n^2)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    ll n, k;
    cin >> n >> k;

    constexpr ll MOD = 1e9 + 7;
    vector<ll> pow2(n + 1);
    pow2[0] = 1;
    for (ll i = 1; i <= n; ++i)
        (pow2[i] = 2ll * pow2[i - 1]) %= MOD;

    vector<vector<ll>> dp(n, vector<ll>(n));
    for (ll r = k; r < n; ++r) dp[0][r] = pow2[r - k];

    for (ll l = 1; l < n; ++l) {
        ll sum = dp[l - 1][l - 1];
        for (ll r = l; r < n; ++r) {
            if (r < l + k) {
                (dp[l][r] += dp[l - 1][r]) %= MOD;
            }
            else {
                (dp[l][r] += (pow2[r - l - k + 1] * dp[l - 1][r]) % MOD) %= MOD;
                (dp[l][r] += (pow2[r - l - k] * sum) % MOD) %= MOD;
            }
            (sum += dp[l - 1][r]) %= MOD;
        }
    }
    cout << dp[n - 1][n - 1] << endl;

    return 0;
}