AtCoder-ABC222 D - Between Two Arrays【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

AtCoder Beginner Contest222のC問題についてPythonの解答例を記事にしていきます。
Exawizards Programming Contest 2021（AtCoder Beginner Contest 222） - AtCoder

AtCoder Beginner Contest222 D - Between Two Arrays

D - Between Two Arrays

問題文

長さ n の数列 S=(s 1 ,s 2 ,…,s n ) がすべての i (1≤i≤n−1) に対して s i ≤s i+1 を満たすとき、かつそのときに限り「数列 S は広義単調増加である」と呼びます。

広義単調増加な長さ N の整数列 A=(a 1 ,a 2 ,…,a N ),B=(b 1 ,b 2 ,…,b N ) が与えられます。
このとき、次の条件を満たす広義単調増加な長さ N の整数列 C=(c 1 ,c 2 ,…,c N ) を考えます。

・すべての i (1≤i≤N) に対して a i ≤c i ≤b i が成り立つ。
整数列 C としてあり得る数列の個数を 998244353 で割ったあまりを求めてください。

制約

・1 ≤ N ≤ 3000
・0 ≤ a i ≤ b i ≤ 3000 (1 ≤ i ≤ N)
・整数列 A,B は広義単調増加である。
・入力はすべて整数である。

解答例

mod = 998244353

n = int(input())
m = 3005

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

dp = [[0]*m for _ in range(n)]

for j in range(A[0], B[0]+1):
    dp[0][j] += 1

for i in range(n):
    for j in range(A[i],B[i]+1):
        if i > 0:
            dp[i][j] = dp[i-1][j]
    for j in range(m-1):
        dp[i][j+1] += dp[i][j]
        dp[i][j+1] %= mod

print(dp[n-1][B[n-1]])