考察
ここでは有料で休日にする日を選び、その間に残る一日を後で無料操作で埋める。二日以上の空きは両隣が休日になる日がなく埋められないので、有料で選ぶ休日の間隔は高々2である。正の費用なので、最初と最後に選ぶ休日の距離がKを超える計画は、端の休日を削って距離K−1またはKへ縮められる。長さKの窓を選び、末日は有料の休日、最初の有料の休日は窓の初日またはその直前とするDPを考える。
dp0 を当日を有料の休日に選ばない場合、dp1 を選ぶ場合の最小費用とする。一日の遷移は dp0′=dp1、dp1′=min(dp0,dp1)+A_i。二日続けて選ばないことを禁止し、選ぶなら直前状態を問わず費用を払う遷移である。列vector用のmin-plus行列は M_i=[[INF,0],[A_i,A_i]] である。
窓の開始l=1,…,N−K+1に対し、直前の初期vectorを (0,A_{l−1}) とする。第1成分はlを最初の休日にする選択、第2成分はl−1から始める選択を表す。l=1だけ番兵 A_0=INF を使い、l>1では実際の費用を使う。
M_{l+K−1}…M_l を初期vectorへ作用させたdp1が、この窓の最小費用である。全窓のdp1の最小を出す。毎回K日分を計算するとO(NK)だが、行列積は結合的なのでSWAGで窓の積を保てる。各日を定数回push・移送・popするだけで全体O(N)となる。
⊗ を通常のmin-plus行列積とする。古い日から新しい日へ並べる汎用SWAGには merge(A,B)=B⊗A を渡す。先にA、後にBの遷移を作用させるため、後の日の行列が左に来る。
典型の発動条件
DP遷移のmin-plus行列化
発動条件: 短い状態DPを多数の連続windowで再評価したいとき。
各要素の遷移を小行列として区間積へ変換する。
SWAG
発動条件: 非可換なassociative積をsliding windowごとに求めたいとき。
front/back stackの向き付き累積積でqueue積を維持する。
問題固有の要素
windowごとのDPは状態数が小さければ、入力要素を遷移operatorに変えてsliding product問題へ移せる。
別の問題へ持ち帰る視点: min-plus写像も結合則があれば通常のmonoid queueと同じdata structureで扱える。
正当性
無料操作で埋める前の有料の休日列を考える。端の休日を削ると費用が下がり、隣り合う休日の距離は高々2なので、条件を保つ最短の両端距離はK−1かKになる。初期二状態と末日の休日状態はこの二場合を覆い、日ごとの遷移は一日だけの空きを許す有料の休日列を過不足なく扱う。空きを無料で埋めれば連続K日以上の休日になる。SWAGの向き付き積は同じ遷移列の合成を返すので、全窓最小が最適費用に一致する。
実装上の注意
- frontを古い日、backを新しい日とすると、窓の行列は
merge(frontProduct,backProduct)=backProduct⊗frontProduct。前提単元のqueue順と、列vectorへ作用する行列の左右順を区別する。
- INF加算overflowとK=1・K=Nの境界を処理する。
復習の核
- 無料操作を直接DPへ入れる前に、有料で選ぶ日だけに注目して条件を言い換える。
- 列vectorへ順に作用する行列は、後の日ほど左に来る。非可換な窓の集約では二日分で合成順を確かめる。
計算量と制約
時間
O(N)、固定2×2行列のSWAGへ各日を一回pushし高々一回移送・popする。
空間
O(K)、window積を保つ二stack。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq T \leq 2 \times 10^5; 1 \leq K \leq N \leq 2 \times 10^5; 1 \leq A_i \leq 10^9; All input values are integers.; The sum of N over all test cases is at most 2\times 10^5.
出典