ABC 456 F — Plan Holidays

考察

ここでは有料で休日にする日を選び、その間に残る一日を後で無料操作で埋める。二日以上の空きは両隣が休日になる日がなく埋められないので、有料で選ぶ休日の間隔は高々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.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Plan Holidays の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: SWAG・two-stack queue aggregation

主題
  • SWAG・two-stack queue aggregation: queueを二つのstackへ分け、それぞれの向きにmonoid積を持ってpush/pop/foldを償却O(1)で処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
    • 半環行列・min-plus/max-min遷移: 遷移を半環行列として定義し、結合則と単位元を保つ二分累乗・区間積で巨大回数の最適化遷移を計算できる。

    主タグ: SWAG・two-stack queue aggregation

    補助タグ: 半環行列・min-plus/max-min遷移

    執筆: abc-explanation-author1.1.1 / revision 3

    学習の位置

    体系上の位置: SWAG・two-stack queue aggregation

    • queueを二つのstackへ分け、それぞれの向きにmonoid積を持ってpush/pop/foldを償却O(1)で処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    • 区間monoid要約 — queryに十分な値と結合順・単位元を定義し、Segment Treeまたはprefix foldで動的区間要約を保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
    • 半環行列・min-plus/max-min遷移 — 線形遷移・行列累乗で得た考え方と実装を再利用し、半環行列・min-plus/max-min遷移の発動条件・正当化・境界を重複なく学ぶ。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題