ABC222D - Between Two Arrays
【必要知識】
DPの基本的な遷移イメージ
特に2次元ナップサックDPを知っているとイメージしやすい
累積和
mod
数A程度の数学知識（=場合の数）
基本的な言語仕様（Python基準のおはなし）
リストのスライス取得にはO(k)かかる
通常のPython3では、計算回数10^6ちょうど辺りが限界（実行制限時間が2secの場合）
10^6を超える場合はPyPy3で提出するのが無難
【ざっくりとした思考の流れ】
うーん、これ典型的なDPっぽいな。とりあえず遷移の流れを絵にしてみよ。
描いた。これ、愚直に遷移させるとO(N*M^2)になっちゃうな。
sum(dp[i-1][:j])をO(1)で取りたいな。
あー、これは先に累積和取っとけばO(1)で値取れるな。そうすればO(MN)になるので通りそう。
通った。
【基本的な遷移イメージ】
遷移イメージ（入力例3の最初の3クエリ）
https://scrapbox.io/files/6163c0a2a102d000200010b6.png
前提：
dp[i][j]には、dp[i][j]までの経路数を格納する。
遷移式：
dp[i][j] = sum(dp[i-1][:j]) となる。
厳密かつ正確な遷移式が知りたい場合は公式解説にて説明されている。 遷移式を噛み砕くと...
「クエリi番目の、左からj番目に至る経路数」は、
「クエリi-1番目の、左からj個目以下の経路数の和」 となる。
この辺りの場合の数については、樹形図を書くとイメージしやすい。
本イメージの問題点：
考え方の骨格は合っているが、現状は遷移数が多すぎる。
図を見ても分かる通り、遷移の線が沢山ある。この遷移の線数はすなわち計算回数に含まれる。
計算量オーダー：M=3001とした場合、O(N*M^2)となる
具体的な計算回数：N*(bi-ai+1)*j (bi-ai+1≦M, j≦M)
つまりsum(dp[i-1][:j])には、j回の計算が必要となる。
この「j回の計算」が無駄そう。
改善テーマ：
dp[i][j]を1回の遷移で求めれば（＝O(1)で取得できれば）、O(NM)となって間に合いそう。
上記問題点を孕んだ状態での実装（TLE解）
code: Python
N = int(input())
LA = list(map(int, input().split()))
LB = list(map(int, input().split()))
MOD = 998244353
dp = [0 * 3001 for _ in range(N)] for i in range(N):
for j in range(LAi, LBi + 1): if i == 0:
continue
# スライスの計算量を意識できるよう、あえてこう書いてみる
dpij = sum(dpi - 1k for k in range(j + 1)) print(res)
累積和を使った改善結果
https://scrapbox.io/files/6163d6c6704ab4001d54c721.png
累積和の利用
予め累積和を計算しておくことで、dp[i][j]の値が一発（=O(1)）で求まるようになる。
dpAccumを累積和のリストだとすると、sum(dp[i-1][:j) = dpAccum[j]となる。
改善後の計算量（M=3001とする）
オーダー：O(MN)
実際の計算回数：Σ(N, i=1) bi-ai+3002
最悪ケースだと、3000*6002≒1.8*10^7
PyPyなら通るが、通常のPythonでは特別な工夫がない限り通らないので注意