ABC 457 G — Catch All Apples

考察

apple iを時刻順に一台で回収できる関係は |X_i-X_j|≤T_j-T_i であり、u=T+X、v=T-Xへ変換すると二座標とも非減少という半順序になる。

採用する候補: appleを (u,v) 辞書順にsortし、v列の最長狭義減少部分列長を求めて必要robot最小数とする。

一台の回収列は半順序のchainで、Dilworthの定理により最小chain分割数は最大antichainサイズに等しい。u順ではantichainがvの狭義減少列に一致する。

棄却する候補: robotを一台ずつ追加し、各appleをどのrobotのrouteへ割り当てるかgreedyまたはbacktrackingする。

局所割当は将来時刻の位置制約を誤り得て、分岐探索は指数的になる。

|ΔX|≤ΔT は T_i+X_i≤T_j+X_j と T_i-X_i≤T_j-X_j の二不等式へ分解できる。

u同値時のsort tieをv昇順にすると、比較可能な同u点を誤って狭義減少列へ同時採用しない。

各appleを(u_i,v_i)へ変換しpair昇順sortする。vを順に見て、狭義減少LIS相当として -v の狭義LISまたはlower_bound規約を使うpatience sortingを行い、その長さを出力する。

典型の発動条件

座標変換による到達半順序

発動条件: 一次元速度制約 |Δx|≤Δt があるevent回収問題のとき。

light-cone座標 t+x,t-xで二次元dominanceへ変換する。

DilworthとLDS

発動条件: 半順序集合を最小本数のchainへ分割したいとき。

最大antichainをsort後の最長減少部分列として求める。

問題固有の要素

移動可能性の絶対値不等式は時空座標を45度回転するとproduct orderになる。

別の問題へ持ち帰る視点: 最小台数のschedule分割は直接greedyせず、chain coverとantichainの双対定理で一つのLISへ変換できる。

正当性

一台で時刻順に回収できる関係は|ΔX|≤ΔTで、u=T+X,v=T−Xの両座標非減少に同値。必要台数はこのposetの最小chain coverでありDilworthより最大antichain幅。u昇順同値v昇順でsortするとantichainはv狭義減少列に対応するため、そのLIS相当の長さが幅になる。同vを比較不能と誤認しないstrict規約を使う。

実装上の注意

  • 同じ時刻・座標の反対称性と重複入力を問題定義に合わせ、u tie時のv sortおよび狭義/広義LIS規約を統一する。

復習の核

  • 絶対値からu,v二不等式を導き、chain=一台route、antichain=LDSの対応を同u・同vのtie例で確認する。

計算量と制約

時間

O(N log N)。座標変換sortと狭義LIS型patience sorting。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \le N \le 3 \times 10^5; 0 \le T_i \le 3 \times 10^5; 0 \le X_i \le 3 \times 10^5; (T_i, X_i) \neq (T_j, X_j) (i \neq j); All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Catch All Apples の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 半順序・Dilworth・最大反鎖

主題
追加で学ぶ技能
    なし
    既習技能
    • LIS・末尾の支配関係: 同じ長さなら小さい末尾が延長可能性を支配することを示し、長さ別最小末尾を二分探索で更新してLIS・非減少部分列を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
    • 幾何の基本判定と座標変換: 幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。

    主タグ: 半順序・Dilworth・最大反鎖

    補助タグ: 幾何の基本判定・配置・座標変換 LIS・末尾の支配関係

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

    学習の位置

    体系上の位置: 半順序・Dilworth・最大反鎖

    • 対象を半順序へ写し、Dilworth型のchain/antichain双対をLDS・matching・min-cutの適切な形で解ける。

    先に読む単元:

    • 二部matching・Hall・Kőnig — 二部グラフの彩色と成分構造で得た考え方と実装を再利用し、二部matching・Hall・Kőnigの発動条件・正当化・境界を重複なく学ぶ。
    • LIS・末尾の支配関係 — 列・subsequence DPで得た考え方と実装を再利用し、LIS・末尾の支配関係の発動条件・正当化・境界を重複なく学ぶ。
    • 列・subsequence DP — DPの最小十分状態で得た考え方と実装を再利用し、列・subsequence DPの発動条件・正当化・境界を重複なく学ぶ。
    • 幾何の基本判定と座標変換 — 座標と外積・距離式で向きや交差を代数判定し、凸幾何へ進む前提を作る。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題