DP遷移を因数分解・集約して加速する

概要

DP遷移の集約・高速化

DPの状態数が収まっていても、各状態の遷移元を毎回すべて調べると間に合わないことがある。このときは、複数の遷移先が同じ部分の和を何度も計算していないかを見る。共通部分を一度だけ集計すれば、元のDPと同じ値を少ない操作で求められる。

まず、ある時刻の状態を 0,…,m−10,\ldots,m-1 とし、その時刻のDP配列を old、次の時刻の配列を new と呼ぶ。一時刻分の配列を層(layer)とも呼ぶ。次の状態 ii へ移れる旧状態の集合を AiA_i とすると、個数を数えるDPの基本式は

new[i]=∑j∈Aiold[j]\mathrm{new}[i]=\sum_{j\in A_i}\mathrm{old}[j]

である。遷移先も mm 個あり、各集合が大きければ、一層に O(m2)O(m^2) 時間かかる。ここでは状態の意味と許可条件を保ったまま、この総和の求め方を変える。まず区間和と例外の減算を学び、その後で共通作用や少数の集計値を使う発展へ進もう。

遷移範囲をまとめる

許可される遷移元が連続していれば、総和を区間和として取得できる。例えば旧配列が (2,1,3,4)(2,1,3,4) なら、添字1以上3未満の和は 1+3=41+3=4、添字0以上3未満の和は 2+1+3=62+1+3=6。二つの問い合わせで 1+31+3 を足し直す必要はない。

先頭からの累積和を共有するのが基本である。ABC253 Eの一次元の区間和から、ABC282 Gの長方形和、ABC265 Fの対角線上の和へ広げられる。まず遷移元がどの範囲になるかを証明し、その範囲を速く取得する方法を選ぶ。

全体から例外を引く

許可集合が複雑でも、禁止集合が小さければ全体和から引けばよい。同じ旧配列で添字1だけが禁止なら、許可側を列挙した 2+3+42+3+4 は、全体和を使って 10−1=910-1=9 と求められる。

ABC212 Eでは禁止辺を個別に引き、ABC370 Eでは同じキーを持つ禁止状態をまとめて引く。ABC319 GはBFSで距離層を構成してから各層へこの減算を使う発展問題である。ただし、最小値・最大値から禁止項を「引く」ことは一般にはできない。

共通作用を外へ出す

和をまとめるだけでなく、全状態へ同じ操作をする費用も省けることがある。ABC372 Fの循環移動、ABC457 Fの全体倍率、ABC435 Gのアフィン作用(同じ倍率を掛けて同じ値を足す操作)と少数の集合変更へ進む。配列の読み方や共通係数を持ち、実際の書換えを例外だけに絞る。その表現が元の同時更新と一致する理由が必要になる。

少数の集計値・隣接状態の式・閉形式の後半

さらに、行別最大などの属性別の値や少数の重み付き和だけで次の値を決められる場合がある。隣接する出力の和が似ていれば、出入りする項だけで次の出力を求められる。巨大歩数の問題では、後半を同じ操作の反復へ置き換えられると証明し、短い前半だけDPする方法もある。どの場合も、何を省略してよいかを素朴式から確かめる。

考え方

最初は区間和と例外減算の二つを、自分で素朴式から導けるようにする。以降の発展でも、保持する値の意味、更新前後の対応、計算量を同じ順で確かめる。

区間・例外・少数の集計値を更新する

累積和で共通部分を一度だけ足す

許可集合を半開区間 [Li,Ri)[L_i,R_i)、つまり Li≤j<RiL_i\leq j<R_i を満たす整数添字の集合にできたとする。端点は 0≤Li≤Ri≤m0\leq L_i\leq R_i\leq m とする。右端を含めないので、要素数は Ri−LiR_i-L_i、両端が同じなら空区間である。

旧配列を読むだけにして、累積和 PP を作る。ここでは数学的な和で説明し、ABC253 E・ABC212 E・ABC370 E・ABC372 Fで個数を求める際は、公式問題と同じく法998244353で計算する。

P[0]=0,P[j+1]=P[j]+old[j]P[0]=0,\qquad P[j+1]=P[j]+\mathrm{old}[j]

この定義から P[r]P[r] は添字0以上 rr 未満の和である。従って

new[i]=∑Li≤j<Riold[j]=P[Ri]−P[Li]\begin{aligned} \mathrm{new}[i] &=\sum_{L_i\leq j<R_i}\mathrm{old}[j]\\ &=P[R_i]-P[L_i] \end{aligned}

となる。右辺では、右端までの和から左端より前の部分が消え、必要な項だけが一度ずつ残る。旧配列 (2,1,3,4)(2,1,3,4) なら P=(0,2,3,6,10)P=(0,2,3,6,10) で、先ほどの二つの和は P[3]−P[1]=4P[3]-P[1]=4、P[3]−P[0]=6P[3]-P[0]=6 と確認できる。

一層の手順は、旧配列から累積和を作り、各遷移先の区間和を新配列へ書き、すべて終わってから旧・新配列を交換する、となる。各状態が定数個の区間を参照するなら、一層の時間は前処理込みで O(m)O(m)、作業領域も O(m)O(m)。層数を hh とすれば全体は O(hm)O(hm) 時間となり、状態数はそのままで一状態当たりの走査を減らせる。

空区間では差が0になる。到達不能な状態も個数DPでは0で初期化する。途中で旧値を上書きすると、後の遷移が同じ時刻の値を読めなくなる。二配列を一つにまとめるときは、別途、依存する旧値が失われないことを示す必要がある。

ABC253 Eの公式解説では、長さを一つ伸ばす遷移でこの形が現れる。ここだけ値は問題文どおり 1,…,M1,\ldots,M とし、old[j]\mathrm{old}[j] を直前値が jj の列の個数とする。次の値 ii に対して

new[i]=∑1≤j≤M∣j−i∣≥Kold[j]\mathrm{new}[i]=\sum_{\substack{1\leq j\leq M\\|j-i|\geq K}}\mathrm{old}[j]

を求めたい。K≥1K\geq1 なら許可範囲は j≤i−Kj\leq i-K と j≥i+Kj\geq i+K の二つで、重ならない。1始まりの値域に合わせて C[0]=0C[0]=0、C[r]=∑j=1rold[j]C[r]=\sum_{j=1}^{r}\mathrm{old}[j] と定めると

new[i]=C[max⁡(0,i−K)]+C[M]−C[min⁡(M,i+K−1)]\mathrm{new}[i] =C[\max(0,i-K)]+C[M]-C[\min(M,i+K-1)]

となる。端点を切り詰めることで値域外の空区間も処理できる。K=0K=0 では全値が許可されるため、全体和 C[M]C[M] を一度だけ使う。長さ1の各末尾の個数を1として長さ NN まで進め、最後の配列の和を答える。全体で O(NM)O(NM) 時間、O(M)O(M) 空間である。

全体和から禁止集合を除く

同じ基本式で、許可集合の補集合を FiF_i とする。旧状態全体が許可集合と禁止集合に重複なく分かれるため

T=∑j=0m−1old[j],new[i]=T−∑j∈Fiold[j]T=\sum_{j=0}^{m-1}\mathrm{old}[j],\qquad \mathrm{new}[i]=T-\sum_{j\in F_i}\mathrm{old}[j]

と書ける。TT を一度作り、各遷移先で禁止項だけを引く。一層の時間は O(m+∑i∣Fi∣)O(m+\sum_i|F_i|) である。禁止条件が複数あっても、同じ状態を二度引いてはいけない。禁止集合が空なら TT、全体なら0となる。

ABC212 Eでは、NN 都市の旅について、dpt[v]dp_t[v] を tt 日後に都市 vv にいる旅の数とする。old[v]=dpt[v]\mathrm{old}[v]=dp_t[v]、new[v]=dpt+1[v]\mathrm{new}[v]=dp_{t+1}[v] と対応する。禁止されるのは都市 vv 自身と、壊れた道路でつながる都市の集合 B(v)B(v) なので

new[v]=T−old[v]−∑u∈B(v)old[u]\mathrm{new}[v]=T-\mathrm{old}[v]-\sum_{u\in B(v)}\mathrm{old}[u]

となる。都市1の初期値だけ1、他は0とし、KK 日後の都市1の値を答える。壊れた道路 MM 本の両向きの寄与と自己遷移を引けば、一日 O(N+M)O(N+M)、全体 O(K(N+M))O(K(N+M)) 時間、二配列と道路の保存に O(N+M)O(N+M) 空間で済む。

この減算に必要なのが加法逆元、つまり足した寄与を打ち消す値である。整数や法上の和なら減算でき、法上では負の結果を正規化する。一方、最小値2を持つ集合から値2の項を除いても、残りの最小値は元の最小値だけでは分からない。区間最小・最大には累積和の差をそのまま使えない。

ただし接尾区間の最大値なら、後ろからの集計(suffix最大)を共有できる。

S[m]=−∞,S[j]=max⁡(old[j],S[j+1])S[m]=-\infty,\qquad S[j]=\max(\mathrm{old}[j],S[j+1])

これで max⁡Li≤j<mold[j]=S[Li]\max_{L_i\leq j<m}\mathrm{old}[j]=S[L_i]。最大化DPの到達不能値も −∞-\infty とする。任意区間の極値が必要なら、その取得に合ったデータ構造を選ぶ。

禁止状態が多ければキー別にまとめる

禁止集合そのものが大きくても、同じキーの状態をまとめて引ける場合がある。ABC370 Eでは dp[i]dp[i] を先頭 ii 要素の合法な分割数とする。累積和 Bi=∑k=1iAkB_i=\sum_{k=1}^{i}A_k、B0=0B_0=0 を使うと、最後の区間 j+1,…,ij+1,\ldots,i の和が KK になる条件は Bj=Bi−KB_j=B_i-K である。従って

dp[i]=∑0≤j<iBj≠Bi−Kdp[j]dp[i]=\sum_{\substack{0\leq j<i\\ B_j\ne B_i-K}}dp[j]

であり、計算直前に次の二つの和を保てばよい。

all=∑0≤j<idp[j],bucket[x]=∑0≤j<iBj=xdp[j]\mathrm{all}=\sum_{0\leq j<i}dp[j],\qquad \mathrm{bucket}[x]=\sum_{\substack{0\leq j<i\\ B_j=x}}dp[j]

遷移は dp[i]=all−bucket[Bi−K]dp[i]=\mathrm{all}-\mathrm{bucket}[B_i-K] となる。空の先頭部分の分割を dp[0]=1dp[0]=1 として、最初に all と bucket[0] へ登録する。各 ii では 値を取得してから、dp[i]dp[i] を all と bucket のキー BiB_i へ加える。これで集計には常に j<ij<i だけが入り、長さ0の最後の区間を混ぜない。

ここでは二層を同時更新するのでなく、確定した先頭部分の状態を順に追加している。例えば長さ1なら、A1=KA_1=K のとき 1−1=01-1=0、異なるとき 1−0=11-0=1 になる。答えは dp[N]dp[N]。キーが未登録なら和は0とし、ハッシュ表なら期待 O(N)O(N)、平衡木なら O(Nlog⁡N)O(N\log N) 時間、空間はいずれも O(N)O(N) である。

重みを分離して少数の和を持つ

遷移に重みがあっても、遷移先だけに依存する係数と遷移元だけに依存する係数に分けられることがある。現在有効な遷移元の集合を JJ とし、重みを RR 個の積の和

w(i,j)=∑r=1Rαr(i)βr(j)w(i,j)=\sum_{r=1}^{R}\alpha_r(i)\beta_r(j)

へ分けられたとする。集計値 Mr=∑j∈Jβr(j)dp[j]M_r=\sum_{j\in J}\beta_r(j)dp[j] を持てば、和の順序を入れ替えて

∑j∈Jw(i,j)dp[j]=∑r=1Rαr(i)Mr\sum_{j\in J}w(i,j)dp[j]=\sum_{r=1}^{R}\alpha_r(i)M_r

となる。新しい遷移元 jj を許可するときは、各 MrM_r へ βr(j)dp[j]\beta_r(j)dp[j] を足す。取得・追加は各 O(R)O(R) で、初期集計は O(R∣J∣)O(R|J|)。RR が小さく、係数の計算も速いことが有効性の条件となる。

例えば重みが i+ji+j なら、∑dp[j]\sum dp[j] と ∑j dp[j]\sum j\,dp[j] の二つで足りる。単に現在の答えが集計値から出るだけでなく、次の集計値も保持している量だけで更新できることを確かめる。これを「更新について閉じる」と呼ぶ。

極値でも、行・列・属性ごとの最大へ分けられる場合は同じように共有できる。ABC224 Eのように狭義の大小関係がある場合、同じ値の全状態の取得を終えてからまとめて登録し、同値間の遷移を混ぜない。

共通作用と例外を同時遷移へ戻す

区間和の共有では旧配列を一度読む費用が残る。次は、全状態の共通更新そのものを省く方法である。ただし、表現を変えても「例外の寄与は同じ旧時刻から読む」という条件は変わらない。

循環移動を添字対応で表す

ABC372 Fでは、環状の通常辺による移動に、少数の追加辺が加わる。ここでは頂点番号を 0,…,N−10,\ldots,N-1 と読み替え、頂点の添字を法 NN で循環させる。

new[v]=old[v−1]+∑追加辺 u→vold[u]\mathrm{new}[v]=\mathrm{old}[v-1]+\sum_{\text{追加辺 }u\to v}\mathrm{old}[u]

通常辺だけなら旧配列 (2,1,3,4)(2,1,3,4) が (4,2,1,3)(4,2,1,3) へ回る。この移動は、保存配列を動かさず、読む位置を変えて表せる。保存配列を aa、添字のずれを表すoffsetを oo とし、次の不変量を置く。

old[v]=a[(v−o) mod N]\mathrm{old}[v]=a[(v-o)\bmod N]

初めは o=0o=0 とする。oo を1増やすと、頂点 vv から読む位置が旧頂点 v−1v-1 の位置になるので、全通常辺の移動を一度に表せる。追加辺は次の順で処理する。

  1. offsetを変える前に、全追加辺の遷移元 old[u]\mathrm{old}[u] を退避する。
  2. o←(o+1) mod No\leftarrow(o+1)\bmod N とする。
  3. 各追加辺 u→vu\to v について、保存先 a[(v−o) mod N]a[(v-o)\bmod N] へ退避した値を足す。

これで通常辺の寄与に追加辺の寄与だけが加わる。辺ごとに読取りと加算を交互に行うと、ある辺の加算先を別の辺が新たな遷移元として読んでしまう。全退避が先である。負の剰余が返る言語では、保存先の添字を 0,…,N−10,\ldots,N-1 へ正規化する。

頂点1(読み替え後は0)だけを1で初期化し、KK 回更新した後に全頂点の値を足す。初期化・最後の総和に O(N)O(N)、各手に O(M+1)O(M+1) なので、全体は厳密には O(N+K(M+1))O(N+K(M+1)) 時間、空間は O(N+M)O(N+M)。通常は O(N+KM)O(N+KM) と略記されるが、M=0M=0 でもこの手順は KK 回のoffset更新を行う。

共通倍率・加算を係数で表す

今度は添字でなく値に共通操作を施す。体、例えば素数を法とする数の上で、実際のDP値 yjy_j を保存値 xjx_j と二つの共通係数で表す。

yj=μxj+νy_j=\mu x_j+\nu

初めは μ=1,ν=0\mu=1,\nu=0、xjx_j は初期値とする。全値へのアフィン作用 y←ay+by\leftarrow ay+b は

a(μxj+ν)+b=(aμ)xj+(aν+b)a(\mu x_j+\nu)+b=(a\mu)x_j+(a\nu+b)

だから、共通係数を μ←aμ\mu\leftarrow a\mu、ν←aν+b\nu\leftarrow a\nu+b とするだけでよい。この更新後の μ\mu が非零なら、一点への実値 δ\delta の加算は

xj←xj+δμx_j\leftarrow x_j+\frac{\delta}{\mu}

で実現できる。代入すると実値の増分が δ\delta になることを確認しよう。例外の量自体が旧値に依存するなら、循環移動と同様に旧値を先に保存する。複数の作用は合成順を変えてはいけない。

a=0a=0 では全実値が bb になり、旧保存値は不要になる。一方、倍率0には乗法逆元がないため、上の除算は使えない。ここは全消去として扱い、保存値をすべて0と見なして μ=1,ν=b\mu=1,\nu=b から再開する。

毎回全配列を消す費用を避けるには、各保存値に世代番号を付ける方法がある。全消去では現在世代だけを進め、古い世代の点は保存値0として読む。初めて書くときに世代と値を設定する。この方法は、データ構造が世代と既定値を扱える場合に使える。

全体和も持つなら、対象個数を nn として共通作用で ∑jyj←a∑jyj+nb\sum_j y_j\leftarrow a\sum_j y_j+nb、例外加算でさらに δ\delta を足す。共通係数の更新は定数回、例外は点の個数分の体演算で済むが、逆元やデータ構造の操作費用は別途数える。体でない法上では非零でも逆元があるとは限らない。

隣接差と閉形式のtailを導く

隣接する和の出入りだけを更新する

旧配列を固定し、幅 D≥1D\geq1 の窓の和を FiF_i とする。

Fi=∑j=ii+D−1old[j]F_i=\sum_{j=i}^{i+D-1}\mathrm{old}[j]

窓を一つ右へずらすと、左端の一項が出て右端の一項が入る。共通項が消えるため

Fi+1=Fi−old[i]+old[i+D]F_{i+1}=F_i-\mathrm{old}[i]+\mathrm{old}[i+D]

となる。例えば旧配列 (2,1,3,4)(2,1,3,4)、D=2D=2 では F0=3F_0=3、F1=3−2+3=4F_1=3-2+3=4、F2=4−1+4=7F_2=4-1+4=7。初めの和を O(D)O(D) で作れば、qq 個の出力は全体 O(D+q)O(D+q) 時間、入力・出力を除く追加領域は O(1)O(1) で求まる。

範囲外を参照するなら、元の遷移に合わせて値を0とするなど境界を定める。重み付き和では窓の移動で残る項の重みも変わり得るため、この二項だけでは更新できない。差に何が残るかを式で調べ、必要な補助集計を導く。

巨大歩数の後半を閉形式にする

ここまでの方法は一層の費用を減らす。層数そのものが巨大な場合は、後半(tail)をDPなしで求められる形へ変えられないか考える。

頂点数 nn のグラフで、各頂点に滞在する操作が許され、一手ごとに到着先の固定報酬 AvA_v を得る場合を考える。開始時点では報酬を得ず、ちょうど KK 手の総報酬を最大化する。ABC358 Gの公式解説の交換論を、この条件のグラフへ一般化して確かめよう。

任意の KK 手の歩行について、開始点を含む訪問頂点のうち報酬が最大の頂点 vv を選ぶ。vv までの前半から同じ頂点へ戻る部分を削り、単純な経路へ縮める。残った経路の長さを tt とすると t≤min⁡(K,n−1)t\leq\min(K,n-1)。その経路をたどった後、残りの K−tK-t 手をすべて vv での滞在に替える。

削った部分と元の後半の各手の報酬は、どれも AvA_v 以下である。置き換え後も総手数は同じで、その各手を報酬 AvA_v に替えるので総報酬は減らない。

そこで dp[t][v]dp[t][v] を「ちょうど tt 手で vv へ来る最大報酬」とし、dp[0][start]=0dp[0][\mathrm{start}]=0、他は −∞-\infty から通常のDPを行う。到達可能な状態について

max⁡0≤t≤min⁡(K,n−1)v(dp[t][v]+(K−t)Av)\max_{\substack{0\leq t\leq\min(K,n-1)\\v}} \bigl(dp[t][v]+(K-t)A_v\bigr)

を取れば答えになる。先の交換論で、任意の歩行以上の候補がこの式にある。逆に、各候補は前半の最良の歩行とその後の滞在で実現できるので、過大評価にもならない。前半DPが単純経路だけを扱う必要はない。

ABC358 Gでは n=HWn=HW で各状態の移動先は定数個だから、時間は O(n(1+min⁡(K,n−1)))O(n(1+\min(K,n-1)))、二層だけを保持して候補を都度評価すれば空間は O(n)O(n) となる。各頂点で滞在できない、報酬が時刻で変わる、といった問題にはこの証明をそのまま使えない。

初期状態と区間端を残して集約する

どの高速化でも、最後に元の状態の意味と端点へ戻る。整数添字の開区間 L<j<UL<j<U は、状態添字が0以上なら半開区間 [max⁡(0,L+1),U)[\max(0,L+1),U) になる。空状態を j=0j=0 に置くと、L=0L=0 では含まれず、L=−1L=-1 では含まれる。「存在しない前回の位置」と「空状態の位置」を同じ番兵へまとめると、最初の合法遷移を落とすことがある。

ABC446 Gでは、同じ値列を一度だけ数えるための代表を固定する。dp[p]dp[p] は最後の同値要素のまとまりが入力位置 pp で終わる代表の個数で、dp[0]=1dp[0]=1 は最初のまとまりを作るための空列を表す。一方、0回目の出現位置は −1-1 である。ここでは既存の問題解説に合わせ、両端を含む累積和を使う。

P[t]=∑j=0tdp[j],P[−1]=0P[t]=\sum_{j=0}^{t}dp[j],\qquad P[-1]=0

冒頭の P[r]P[r] は添字 rr を含まない和だったが、この節では含む和なので、取得式も合わせて変える。l=max⁡(0,L+1)l=\max(0,L+1)、r=U−1r=U-1 とすれば

∑L<j<U, j≥0dp[j]=P[r]−P[l−1]\sum_{L<j<U,\ j\geq0}dp[j]=P[r]-P[l-1]

である。P[−1]P[-1] は配列の負添字を読まず、分岐で0を返す。例えば最小入力 N=1,A=(1)N=1,A=(1) では L=−1,U=1L=-1,U=1 なので、区間 [0,1)[0,1) は dp[0]dp[0] を含み、dp[1]=1dp[1]=1 となる。

遷移が pp 未満だけを参照し、確定した旧状態を変更しないなら、この累積和を末尾へ伸ばすだけで各取得は O(1)O(1) となる。常にFenwick木の O(log⁡N)O(\log N) の取得が必要なわけではない。

最後の集計も状態の意味から決める。dp[1],…,dp[N]dp[1],\ldots,dp[N] だけを足すなら既に非空列だけで、さらに1を引かない。空状態込みの P[N]P[N] を使う場合だけ1を引く。初期化、遷移の両端、最終集計を同じ最小入力で追うことが、組合せた手順の検算になる。

成立条件と計算量

高速化を選ぶときは、次の違いを確認する。

共有するもの使える条件省けない確認
区間和遷移元が少数の区間になり、和を減算できる両端・空区間・累積和を作る費用
全体和からの例外減算禁止項を少数の項またはキー別の和にできる重複除去・自己遷移・登録順
共通作用添字対応や共通係数で実値を再現できる旧値の退避・作用の合成順・倍率0
少数の集計値・隣接差必要な量だけで取得と次の更新を行える有効な遷移元の範囲・補助集計
後半の閉形式任意の解を同じ反復へ移す正当化がある滞在の可否・報酬の条件・前半の長さ

時間計算量は「一回の取得が速い」で終えず、前処理、全層の全状態、集計の更新、最後の答えの取得まで数える。空間計算量には旧・新配列、集計値、入力やデータ構造を含める。小さな旧配列で直接総和と一致させた後、式の分解や不変量によって一般の場合も同じ値になることを説明しよう。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 青色(1600–1999)。漸化式の共通項・例外・集約範囲を取り出し、状態数と遷移数を別々に減らす。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 動的計画法。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-dp-transition-optimization

習得する技能

  • 余分な歩行を訪問済みの最良状態での反復へ移す交換論を示し、有限prefix DPと閉形式のtailへ分離できる。
  • 遷移式を属性別極値・少数の重み付き和へ分解し、その集計値が更新について閉じることを示せる。
  • 素朴な遷移元の列挙をprefix・suffix・区間の和や極値へ書き換え、依存順と問い合わせ範囲を保って高速化できる。
  • 全状態に共通する添字移動・倍率・affine作用を外出しし、旧値の保存と非可逆な作用を扱って例外だけを更新できる。
  • 隣接する出力の遷移式を比較し、共通項の消去と出入りする項から定数時間更新を導ける。
  • 全遷移の総和から禁止辺・禁止keyの集計値を引き、例外の総数で計算量を評価できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: 最小十分状態からDPを設計する。

このUnitを直接前提とする単元: Monge・monotone minima最適化。

正しい状態と遷移を作った後、共通項の因数分解や集約で同じDPを高速化する。

このUnitでは扱わないもの

  • 固定線形遷移の巨大回累乗。

根拠