ABC 237 F — |LIS| = 3

考察

LIS の長さだけでは次の値を追加したときに伸びるか判断できず、各長さの増加部分列をどれだけ小さい末尾で作れるかが必要になる。

求める LIS 長が 3 と固定され、値域 M も 10 以下なので、長さ 1、2、3 の最小末尾三つを数え上げ DP の状態にできる。

棄却する候補: 位置ごとに現在の LIS 長だけを状態として、次の値を M 通り試す。

同じ LIS 長でも末尾値によって将来の値が部分列を伸ばせるか異なり、正しい遷移を決められない。

採用する候補: 長さ j の増加部分列の最小末尾 a_j を j=1,2,3 について持ち、各 x を追加したとき最初の a_j≥x を x に置き換える DP を行う。

patience sorting の末尾最小値列は将来の全遷移に十分で、長さ 4 が生じる遷移だけ捨てれば LIS≤3 の全列を数えられる。

厳密増加 LIS では x を lower_bound、すなわち最初の a_j≥x の位置へ入れることで、処理済み列の LIS 情報を三つの最小末尾に圧縮できる。

a_3 が有限な終了状態だけを合計すれば LIS≥3 であり、長さ 4 を作る遷移を除外済みなので LIS はちょうど 3 になる。

通常は一列の LIS を求める patience sorting の tails 配列を、小さい値域上の有限状態へ変えて列の個数を数える DP にする。

未存在のtailsを M+1 として dp[0][M+1,M+1,M+1]=1、他を0にする。各 x=1,…,M に対して最初の a_j≥x を置き換え、三つとも x より小さければ長さ4ができるため捨てる。N個処理後に a_3≤M の全状態を足す。この sentinel と初期値により、長さ0,1,2の列も同じ三成分状態で扱える。

典型の発動条件

LIS の最小末尾配列

発動条件: 要素を順に追加したときの増加部分列情報を、将来の延長可能性を保ったまま圧縮したいとき。

長さごとの最小末尾を持ち、新要素で lower_bound の位置を更新する。

アルゴリズム状態の数え上げ DP 化

発動条件: 通常の逐次アルゴリズムの内部状態数が、小さい値域や小さい目標長によって有限個に抑えられるとき。

各 tails 状態へ到達する数を持ち、次の値 M 通りについてアルゴリズムと同じ更新を配る。

問題固有の要素

未到達の末尾値には M+1 を番兵として使い、初期状態を (M+1,M+1,M+1) と表せる。

別の問題へ持ち帰る視点: 固定長までの部分列情報を数えるときは、存在しない層へ値域外番兵を置くと初期化と終了判定を統一できる。

正当性

厳密増加部分列の各長さの最小末尾は、将来の伸長可否を完全に決めるpatience sortingの不変量。次値xは最初のtail≥xを置換する。三つのtailを全状態として数えれば、同じ情報のprefixを合流しても後続のLIS条件は変わらない。第四tailが必要になる遷移を禁止し、終了時に第三tailが有限な状態だけ合計すれば長さちょうど3を過不足なく数える。

実装上の注意

  • x が a_3 より大きく lower_bound が四番目になる遷移は、LIS 4 を作るため加算しない。
  • 各長さで新しい DP 配列へ遷移し、加算のたびに 998244353 で剰余を取る。

復習の核

  • 逐次アルゴリズムの結果だけでなく、次の入力への応答を決める最小の内部状態を DP にできないか考える。
  • 「ちょうど K」は、K+1 以上になる遷移を遮断した上で K に到達した状態を数える形に分解する。

計算量と制約

時間

O(NM^4)。三つのtails状態O(M³)から各値Mを遷移する。

空間

O(M³)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 3 \leq N \leq 1000; 3 \leq M \leq 10; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

|LIS| = 3 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 最小十分状態からDPを設計する

主題
追加で学ぶ技能
    なし
    既習技能
    • LIS・末尾の支配関係: 同じ長さなら小さい末尾が延長可能性を支配することを示し、長さ別最小末尾を二分探索で更新してLIS・非減少部分列を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    主タグ: DPの最小十分状態

    補助タグ: LIS・末尾の支配関係

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

    学習の位置

    体系上の位置: 最小十分状態からDPを設計する

    • 採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。

    先に読む単元:

    • LIS・末尾の支配関係 — 列・subsequence DPで得た考え方と実装を再利用し、LIS・末尾の支配関係の発動条件・正当化・境界を重複なく学ぶ。

    この解説で扱わないこと:

    • 状態の再利用をせず、頂点を一度ずつ訪問する到達可能性探索。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題