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

hamayanhamayan's blog

エレベーター [yukicoder No.801]

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

解法

https://yukicoder.me/submissions/325930

dp[k][floor] := k回移動後にfloor回にいる組合せ
でDPしよう。
dp[k][???]からdp[k+1][???]を高速に更新することを考えよう。
 
まずは、愚直解から作る。
あるエレベータmを使うとしたときに、
dp[k+1][x] += sum{y=L[m]...R[m]}dp[k][y]
L[m]≦x≦R[m]
という遷移となることが分かる。
これを高速化したいのだが、sum{y=L[m]...R[m]}dp[k][y]の部分は慣れていると、累積和でいけるなと気づく。
しかも重要なことに、この値は、あるエレベータmによって固定の値になっている。
つまり、sumの値をdp[k + 1][L[m]], dp[k + 1][L[m]+1], ..., dp[k + 1][R[m]]に一律足していることになる。
この一律に足す操作はimos法を使えば、O(M+N)で実現できる。
 
移動はK回行われるので、O(K(M+N) )となり、これは間に合う。

int N, M, K, L[3010], R[3010];
mint dp[3010][3010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K;
    rep(m, 0, M) {
        cin >> L[m] >> R[m];
    }

    dp[0][1] = 1;
    rep(k, 0, K) {
        rep(i, 1, N + 1) dp[k][i] += dp[k][i - 1];
        
        rep(m, 0, M) {
            int l = L[m], r = R[m];
            
            mint sm = dp[k][r] - dp[k][l - 1];

            dp[k + 1][l] += sm;
            dp[k + 1][r + 1] -= sm;
        }

        rep(i, 1, N + 1) dp[k + 1][i] += dp[k + 1][i - 1];
    }

    cout << dp[K][N] << endl;
}