ABC 395 F — Smooth Occlusion

考察

最終sum Hを固定すると削る総量はΣ(U_i+D_i)-NHで構成によらないため、cost最小化は実現可能なH最大化と同値である。

各上歯a_iは0≤a_i≤U_iかつ0≤H-a_i≤D_iより区間[max(0,H-D_i),min(U_i,H)]に入り、隣接差≤Xを満たす列の存在判定になる。

採用する候補: Hを二分探索し、左から到達可能なa_iの区間を伝播して可否判定する

棄却する候補: 各歯の最終上長を個別にgreedyで最大化する

隣接差制約が連鎖するため局所最大選択は将来区間を空にし得て、共通Hも保証しない。

H候補ごとにpossible=[max(0,H-D_1),min(U_1,H)]から始め、iを進めてpossibleを[possible.low-X,possible.high+X]と歯iの許容区間で交差する。空ならNo。最大Yes Hから総和-NHを出す。

典型の発動条件

区間到達可能性DP

発動条件: 一次元列で各値が区間制約と隣接Lipschitz制約を満たすか判定するとき。

到達値集合を一つのintervalとして伝播する。

実現可能値最大化の二分探索

発動条件: 目的が共通parameter Hの単調可否と線形に結び付くとき。

最大feasible Hを探す。

問題固有の要素

削り方のcostを直接最適化せず、上下和Hを固定すると目的が消え、上歯だけの区間列feasibilityへ変わる。

別の問題へ持ち帰る視点: 総量削減問題では最終総和parameterを固定し、局所変数の可到達区間を調べる。

正当性

前位置で可能な値が連続区間[l,r]なら、次位置へ差X以内で移れる値全体も[l-X,r+X]という区間である。 Hが実現できれば適切に上下歯を追加で削って任意の小さいHも実現でき、binary searchの単調性が成立する。 Hの可否は下方向に単調で、各位置の可能区間を前区間±XとのintersectionでO(N)更新できるためO(N log maxHeight)で解ける。

実装上の注意

  • 許容区間下端max(0,H-D_i)、上端min(U_i,H)を使い、交差空判定を等号込みで行う。Σ(U+D)-NHは64 bit整数。

復習の核

  • N≤7、小heightで全最終U'_iを列挙し、H=0、区間が一点、差がXちょうどのcaseを二分探索判定と比較する。

計算量と制約

時間

O(N log Hmax)、歯一つごとの可能値区間伝播はO(1)。

空間

O(N)、判定自体O(1)補助。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2 \times 10^5; 1 \leq U _ i \leq 10^9 \ (1 \leq i \leq N); 1 \leq D _ i \leq 10^9 \ (1 \leq i \leq N); 1 \leq X \leq 10^9; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 単調境界を証明して探索する

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

      主タグ: 単調境界探索

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

      学習の位置

      体系上の位置: 単調境界を証明して探索する

      • 判定の単調性を証明し、二分探索の成功側・失敗側を設定できる。

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

      • 連続窓の両端を一方向に進める尺取り法、および真偽判定の単調境界を持たない三分探索・局所探索。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題