ABC222D - Between Two Arrays

考え方

dp[i][j]=「$c_{i} = j$となる方法の数」がわかれば，

\begin{aligned}
&\mathrm{dp}[i+1][j] \\
& =
\begin{cases}
\, \displaystyle
\sum_{k\leq j} \mathrm{dp}[i][k] & (A_{i + 1} \leq j \leq B_{i+1}) \\
\, 0 & (\text{otherwise})
\end{cases}
\end{aligned}

と求めることができる．

回答例

特に工夫をしない書き方．

配列再利用や，累積和のとり方には工夫の余地がある（Editorial - Exawizards Programming Contest 2021（AtCoder Beginner Contest 222））．

import itertools

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

M = 998244353

dp = [[0] * 3001 for _ in range(N)]
dp[0] = [1 if A[0] <= i <= B[0] else 0 for i in range(3001)]

for i in range(N - 1):
  a, b = A[i + 1], B[i + 1]
  acc = list(itertools.accumulate(dp[i]))
  for j in range(a, b + 1):
    dp[i + 1][j] = acc[j] % M
    
print(sum(dp[-1]) % M)