ABC 339 E — Smooth Subsequence

考察

A_iを末尾にするsmooth subsequenceの最長長だけを値ごとに持てばよい。直前値xは|x-A_i|≤D、すなわち値域区間[A_i-D,A_i+D]にあるため、遷移は区間最大値+1になる。dp[x]を処理済みprefixで値xを末尾とする最大長とすれば、A_i以外のdpは変化しない。new=1+max_{x∈[A_i-D,A_i+D]}dp[x]を計算してdp[A_i]をchmaxすれば、同じ値が再登場しても最良prefixだけを残せる。

採用する候補: 値軸segment treeでrange maximum queryとpoint chmaxを行う

入力順を保つ一次元DPを、値域上のO(log V)query/updateで実装できる。

棄却する候補: 各iで全ての以前のjを調べるLIS型二重loop

隣接差条件の確認にO(N^2)かかりN=5×10^5に間に合わない。

値域1…500000にmax segment treeを作る。A_iを左から読み、l=max(1,A_i-D), r=min(V,A_i+D)の区間maxをqueryしv+1を得る。位置A_iを現在値とのmaxでpoint updateし、tree全体のmaxを出力する。

典型の発動条件

値域DP

発動条件: subsequence遷移条件がindex距離でなく直前要素の値範囲で決まる。

末尾値ごとにprefix内の最良長をまとめ、入力順に一度ずつ更新する。

segment treeのrange max・point update

発動条件: 連続値区間の最大値を多数queryし、一点だけchmaxする。

値をleaf indexにしてmonoid maxを管理する。

問題固有の要素

dpにindex次元を残す必要はなく、将来から区別されるのは最後の値だけなので、過去の同値末尾を最大長へ集約できる。

別の問題へ持ち帰る視点: subsequence DPは将来条件が末尾値だけを見るなら、index×値状態を値別frontierへ圧縮する。

正当性

各A_iで終わる解の直前値は[A_i−D,A_i+D]に限る。前prefixのこの範囲の最長値へ1を足せば全候補を覆う。値が同じ状態は長い方が全将来に有利なので最大だけを保持でき、入力順の帰納法で正しい。

実装上の注意

  • query区間は値域端で切り、segment treeが半開区間ならr+1を渡す。D=0では同値だけが遷移元となり、update前の値をqueryしてから加える。

復習の核

  • D=0、Dが値域以上、同じ値の反復、増減が交互の列をO(N^2) DPと比較する。

計算量と制約

時間

列長N、値域V=500000。segment treeで O(N log V)。

空間

DPを値ごとに保持して O(V)、入力逐次処理可。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 5 \times 10^5; 0 \leq D \leq 5 \times 10^5; 1 \leq A_i \leq 5 \times 10^5; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Smooth Subsequence の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 値域集約による部分列DP

主題
  • 値域集約による部分列DP: 末尾の値ごとに最良状態を持ち、許される直前値の区間を集約して部分列DPの遷移を高速化する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
    • 区間monoid要約: 要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。

    主タグ: 値域集約による部分列DP

    補助タグ: 区間monoid要約

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

    学習の位置

    体系上の位置: 値域集約による部分列DP

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

    先に読む単元:

    • 列・subsequence DP — DPの最小十分状態で得た考え方と実装を再利用し、列・subsequence DPの発動条件・正当化・境界を重複なく学ぶ。
    • 区間monoid要約 — queryに十分な値と結合順・単位元を定義し、Segment Treeまたはprefix foldで動的区間要約を保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題