Between Two Arrays [エクサウィザーズプログラミングコンテスト2021（AtCoder Beginner Contest 222） D]

https://atcoder.jp/contests/abc222/tasks/abc222_d

前提知識

• DP

解説

https://atcoder.jp/contests/abc222/submissions/26480980

問題を眺めるとかなりDPな感じがする。
具体的には

• mod 998244353
• 先頭から数を決めていくと広義単調増加は1つ前しか見なくていい
• 制約的に何となく

みたいな所からDP感を感じてDPで考えてみると解けると分かってくる感じ。

naive DP

※ lstはlast, nxtはnextのつもり。関数名とかと被ってしまうのでこんな表記にしてる

単純なDPから考えてみよう。
先ほども書いたが、先頭から数を決めていくと広義単調増加は1つ前しか見なくていいので、
DPの状態としては最後に何の数を選んだかという状態を含めておけばいいことになる。
なので、

dp[i][lst] := i番目まで数列が確定していて、最後の数がlstであるような条件を満たす組合せ

というのを計算すればいい。
dp[i][lst]からdp[i+1][nxt]に遷移を考えたときに、満たす条件は

• lst ≦ nxt
• a[i]≦nxt≦b[i]

の2つである。
これに気を付けながらDPを書いていくとO(N³)の解法が出来上がるはず。
https://atcoder.jp/contests/abc222/submissions/26480825
これが理解できるまでは最初の段階。

高速化

これを高速化していくことを考える。
前のnaive DPは遷移元を起点として遷移先に分配していくような「配るDP」から、
遷移先を起点として、遷移元を見ていくような「貰うDP」にまずは変化させよう。
一概には言えないが、この変換が高速化に役立つことが多々ある。
言葉では何とも説明しにくいのだが、以下のような実装に変化する。

https://atcoder.jp/contests/abc222/submissions/26480899

これを眺めると、最終的な更新で、[0,nxt]の区間和を取るような計算が要求されている。
これは累積和を作っておけば高速に処理することができる。
よって、別途累積和を作っておいて、毎回それを使うことにすれば大幅に計算量が改善でき、
O(N²)となって通る。

int N, a[3010], b[3010];
mint dp[3010][3010];
mint rui[3010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> a[i];
    rep(i, 0, N) cin >> b[i];

    dp[0][0] = 1;
    rep(i, 0, N) {
        rui[0] = dp[i][0];
        rep(lst, 1, 3001) rui[lst] = rui[lst - 1] + dp[i][lst];
        rep(nxt, a[i], b[i] + 1) dp[i + 1][nxt] += rui[nxt];
    }
    
    mint ans = 0;
    rep(lst, 0, 3001) ans += dp[N][lst];
    cout << ans << endl;
}