ABC 381 F — 1122 Subsequence

考察

値は1..20で、1122部分列では各採用値をちょうど二回ずつ使うため長さは最大40である。採用値集合 S が同じなら、最も早く作れる終了位置だけ残せば以後の拡張可能性を完全に表せる。同じ集合 S を作る方法のうち終了位置が早いものは、遅いものが可能な全ての将来追加を同様に行えるため支配する。next(pos,x) を前計算すれば、x を二回追加した終了位置は next(next(dp[S],x),x) と書ける。

採用する候補: dp[S] を各値を二回ずつ並べた部分列を作れる最小終了位置とし、S から最後の値 x を除いた状態の後に x の次出現を二回辿って更新する bit DP を行う。

2^20 状態と各状態の set bit 遷移で O(20·2^20)、次出現表で各遷移 O(1) にできる。

棄却する候補: 長さ40以下の全ての部分列 index を DFS して 1122 条件を確認する。

N が2×10^5で短い長さでも部分列数は組合せ爆発し、値集合の小ささを使えていない。

各位置と値の次出現 index を後ろから前計算する。dp[0]=0、他をINFとし、mask と未使用値 x について二回 next を適用して dp[mask|1<<x] を chmin する。到達 mask の最大 popcount×2を返す。

典型の発動条件

最早終了位置を値にする bit DP

発動条件: 種類数が小さい部分列選択で、同じ集合なら早い終了だけが優越するとき。

mask ごとに最小 prefix 長を保持し next occurrence で遷移する。

問題固有の要素

部分列そのものを状態にせず、採用済み値集合と将来余地を最大化する最早位置だけへ圧縮する。

別の問題へ持ち帰る視点: 各値をちょうど二回という規則が、遷移を next の二重適用へする。

正当性

maskで使った各値は隣接二出現のblockとして選ぶ。未使用値の最初二出現を現在終点後から選ぶと、同値二個を選ぶどの他の選択より終点が早く全将来に優越する。maskごと最短終点だけ残す帰納法で全feasible値集合を見つけ最大2popcountを得る。

実装上の注意

  • 値を0-origin bitへ直し、INF に next を適用しない。dp[empty] の位置0と配列 index の番兵規約を統一する。

復習の核

  • 同じ mask の二つの終了位置を比較し、早い方だけで十分という支配性を次の二出現選択から説明する。

計算量と制約

時間

列長N、値種C=20。next表 O(NC)、subset DP O(C2^C)。

空間

next表 O(NC)、最短終点DP O(2^C)。

制約との対応

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

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 部分集合・bitmask状態DP

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 部分集合・bitmask状態DP

    補助タグ: DPの最小十分状態

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

    学習の位置

    体系上の位置: 部分集合・bitmask状態DP

    • bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題