今日の精進-DP（AtCoder ABC222-D）

今日、解き直した問題は AtCoder ABC222-D「Between Two Arrays」です。DPはいつまでも苦手です。

問題

D - Between Two Arrays

ポイント

• 適当な例（ $${N=3}$$ くらいで）を作って、実際に整数列 $${C}$$ を作ってみると、1個前の数字によりけりだなと思い、DPを検討する。

• dp[ i ][ j ] を i 個目までみていて、i 個目が j の時に作れる整数列の数が入ると定義する。

• という感じで、二次元のDPでいけそうなので、紙に表を書いてみる。

ACしたコード

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 62;
// const int INF = 1001001001;


int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  rep(i, N) { cin >> a[i]; }
  vector<int> b(N);
  rep(i, N) { cin >> b[i]; }

  vector<vector<mint>> dp(N+1, vector<mint>(3001, 0));
  dp[0][0] = 1;
  rep(i, N) {
    if (i == 0) {
      for(int j = a[0]; j <= b[0]; ++j) {
        dp[1][j] = 1;
      }
    } else {
      for(int j = 0; j < 3000; ++j) {
        dp[i][j+1] += dp[i][j];
      }
      for(int j = a[i]; j <= b[i]; ++j) {
        dp[i+1][j] += dp[i][j];
      }
    }
  }

  mint ans = 0;
  rep(i, 3001) {
    ans += dp[N][i];
  }

  cout << ans.val() << endl;
  return 0;
}

提出 #49842906 - AtCoder Daily Training MEDIUM 2023/10/25 16:00start

上のコードの dp[ i ][ j + 1 ] += dp[ i ][ j ] は累積和っぽい感じ。
1つ前の行の累積和をとってから、次の行に渡すというイメージ。
なかなか難しいな。