値域集約による部分列DP

概要

末尾の値ごとに最良状態を持ち、許される直前値の区間を集約して部分列DPの遷移を高速化する。

処理済みprefixについて、末尾の値vごとの最良長best[v]を持つ。直前値として許される区間の最大値に1を足し、現在値へchmaxする。列の順序は左からの処理で守り、値の条件は区間queryで守る。

ABC339 Eでは直前値が[A_i−D,A_i+D]にあることが条件である。末尾が小さいほど有利とは限らず、LISのtailsには圧縮できない。ABC360 Gでは未変更・変更済みの状態を分け、各値域構造を同じ要素から二度遷移させない更新順も確かめる。

ABC354 Fの採用解法では左右から値域最大DPを行い、l_i+r_i−1=Lで最長解に属し得る位置を判定する。この所属条件とLISの計算法は別の観察であり、基本LISのtailsを使う別実装と区別する。ABC240 Exでは部分文字列を辞書順に処理し、選択済みの最後の右端位置を集約軸にする。ABC410 Gでは右端順に処理し、左端位置の範囲を集約する。集約する座標は入力の数値そのものとは限らず、次の候補との接続条件から決める。

考え方

直前値が区間[L(x),R(x)]にある状態の最大値や総和を使うなら、末尾値ごとのDPを区間構造へ入れる。列の時間順は左からの走査、値の制約はquery範囲で守る。

狭義増加部分列ならdp_i=1+max_{j<i,a_j<a_i}dp_j。値をsort-uniqueし、各rankの最良長を初期0でsegment treeへ持つ。位置iでrank(a_i)未満のprefix最大を取得し、一伸ばしてそのrankへchmaxする。queryをupdateより先に行うのでj<iを保ち、同値をquery範囲から除くので狭義性も保つ。非減少なら自分のrankを含める。時間の順と値の順の二制約を別々に守るのがこの設計の要点である。

成立条件と計算量

N要素・値域MならSegment TreeでO(N log M)。同じ値の更新を上書きか合成かはDPの意味による。遷移前にqueryして同じ要素の再利用を防ぐ。LISの最小末尾への圧縮とは適用条件が違う。

問題一覧

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

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。列DPの遷移を値域の集約へ写し、Segment Treeと更新順を組み合わせる。

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

概念上の親: 列・subsequence DP。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-dp-value-range

値域集約による部分列DP

習得する技能

  • 末尾の値ごとに最良状態を持ち、許される直前値の区間を集約して部分列DPの遷移を高速化する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

前提と範囲

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

直接の前提単元: 列・subsequence DP、区間monoid要約。

このUnitを直接前提とする単元: なし。

区間monoid要約・列・subsequence DPで得た考え方と実装を再利用し、値域集約による部分列DPの発動条件・正当化・境界を重複なく学ぶ。

このUnitでは扱わないもの

  • 値域集約による部分列DPの発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠