ABC 406 G — Travelling Salesman Problem

考察

品物 i を座標 x で受け取るときの最小費用 f_i(x) は、直前座標 y から自分が動く C|x-y| と商人 i が X_i から動く D|X_i-x| の和で遷移する。

f が離散凸なら g(x)=min_y(f(y)+C|x-y|) も凸であり、これは f の傾きを [-C,C] に切り詰める操作に一致する。その後 D|X_i-x| を加えると X_i に傾き差 2D が入る。

採用する候補: 凸区分線形関数の傾き変化を slope trick で管理し、絶対値の min-plus convolution と加算を各商人について更新する

変化点を map または Fenwick tree で扱えば各更新を対数時間で行え、各段のclipで残る区間の両端を保存して逆順に最適な受取座標も復元できる。

棄却する候補: 全座標 x,y を列挙して dp_i[x]=min_y(dp_{i-1}[y]+C|x-y|)+D|X_i-x| を計算する

座標候補が約 2×10^5、商人も 2×10^5 で、少なくとも状態数だけで O(NR)、素朴遷移は O(NR^2) になる。

min convolution で値が f から変わらない座標は一つの区間をなし、その外側では端点から傾き ±C で延長される。したがって傾き変化を左右から削るだけで g を得られる。

最終 f_N の最小点を選び、各段階で現在座標 x を「f_{i-1}=g_i だった区間」へ clamp すると最適な直前座標を得る。各段階でこの区間の二端を保存すれば逆順に参照できる。

初期状態はf_0(0)=0、f_0(x≠0)=+∞。従って最初のconvolutionはg_1(x)=C|x|であり、f_1(x)=C|x|+D|X_1−x|から始める。定数0で初期化すると自由な始点を許すので、X_1=1,C=2,D=3の最小費用2を0と誤る。

各i≥2では、f_{i−1}の離散傾きq(z)=f_{i−1}(z+1)−f_{i−1}(z)を非減少順に保持する。−C未満の左側、Cより大きい右側を削り、残った傾きとの境界をI_i=[l_i,r_i]として保存する。これはg_i=f_{i−1}となる閉区間である。全座標[-10^5,10^5]内で端がなければdomain端を用い、I_1=[0,0]とする。削った側では区間端から傾き−C,+Cでg_iを延長し、その後D|X_i−x|を足す。絶対値追加の傾きjumpはX_iで2Dなので、変化点とその重みを二つのheapまたはordered mapへ追加する。境界のjumpを途中まで削る場合は残り重みも保持する。

各追加は一つのjumpを作り、clipで削除したjumpは再登場しないので、削除総数を償却できる。I_iの二端だけを保存すれば、変更履歴全体のundoは必要ない。最終f_Nの最小点A_Nを選び、i=N,…,2でA_{i−1}=clamp(A_i,I_i)とする。A_iがI_i内ならy=A_i、外なら近い端点がmin_y(f_{i−1}(y)+C|A_i−y|)を達成するため、この復元はprefix最適値へ戻る。A_0=0として復元列のΣ_i C|A_i−A_{i−1}|+D|X_i−A_i|が出力した最小値に等しいことも検査できる。

重み付きjumpを値まで接続するには、f(x)=β+αx+Σ_{(z,w)}w max(x−z,0)と表す。初期g_1=C|x|はα=−C、β=0、event(0,2C)。D|X_i−x|を足す操作はα−=D、β+=DX_i、event(X_i,2D)の挿入である。従って各f_iの両端の傾きは−(C+D),C+D、jumpの総重みは2(C+D)となる。

次のclipでは左端から重みD、右端から重みDを取り除く。左のevent(z,w)からδだけ取ると、α+=δ、β−=δz、重みw−=δ。右からδを取る場合は重みだけを減らす。これは左側ではfの右側の値を、右側ではfの左側の値を保って外側だけを傾き±Cに変える恒等式である。残り重み0のeventは削除し、途中でDに達したら一eventを部分的に残す。最後にα=−C、総jump重み2Cとなり、定数項も正しく更新される。

左から最後に削った座標をl_i、右から最後に削った座標をr_iとして保存すれば、g_i=f_{i−1}の区間I_i=[l_i,r_i]を得る。最小event・最大eventを得るordered mapと、座標ごとのw,wzのprefix和を持つFenwick木を使える。座標は0と全X_iだけなので圧縮可能。q(x)=α+Σ_{z≤x}wが非負となる最初の座標を最小点にし、f(x)=β+αx+xΣ_{z<x}w−Σ_{z<x}wzで最小値を評価する。最終位置から保存済みI_iへ逆順clampして受取位置列を復元する。重みC,Dの個数だけeventを展開する必要はない。

典型の発動条件

slope trick

発動条件: 絶対値を加える操作や絶対値との min-plus convolution を繰り返す凸 DP のとき。

傾きの変化点・変化量と基準値を持ち、傾き clip と kink 追加で関数全体を更新する。

凸 DP の最適解復元

発動条件: 関数値の最小値だけでなく各段階の argmin 列が必要なとき。

前向き更新の履歴を保存し、逆向きに convolution の不変区間へ座標を clamp する。

離散凸関数の傾き管理

発動条件: 整数座標上の区分線形凸関数を多数更新したいとき。

傾き差分を ordered map や座標範囲上の Fenwick tree で保持する。

問題固有の要素

商人と自分の移動順序を受取座標列だけに集約すると、二種類の移動費は連続する座標差と入力座標からの絶対値として完全に分離する。

別の問題へ持ち帰る視点: 絶対値距離の列最適化では DP 関数そのものではなく傾きの変化だけを持ち、復元には clip で失った領域の境界履歴を残す。

正当性

C|x−y|とのmin convolutionは任意y候補の凸costを比較し、元関数の傾きを[−C,C]へ切る操作に等しい。D|X_i−x|追加は現在受取費用であり、従って各f_iは最適prefix費用そのもの。最終minimizerからclipで元fと一致した区間へclampすると最適yが得られるので、保存した区間を逆順に参照して全受取位置も最適に構成できる。 初期f_0は原点以外を禁止し、最初の費用C|x|を必ず含む。clipで残った区間I_iへのclampはconvolutionの最小候補を与えるため、逆順の各接続が等号を保ち、原点からの復元列の費用が最小値に一致する。 左clipのα+=δ,β−=δzは削ったhingeの右側の値を保存し、右clipは左側の値を保存する。左右の極端な傾きを±Cへ戻すまでそれぞれ重みDを削るため、本文の係数更新は定数項を含めてmin convolutionと一致する。

実装上の注意

  • 表現はf(x)=β+αx+Σw max(x−z,0)。絶対値追加、左clip、右clipでαとβを更新する式を固定する。
  • eventは位置と重みの組。同座標の重みを加算し、部分削除では残り重みを保存する。
  • 最初のclip前は原点だけを許し、g_1=C|x|から始める。I_1=[0,0]。
  • 復元はI_iの二端を保存すればよい。元の費用ΣC|A_i−A_{i−1}|+D|X_i−A_i|でも照合する。

復習の核

  • N=1、C≪D、C≫D、同一 X の反復、X が左右に交互に振れる場合を小座標の全 DP と比較し、費用と復元列の双方を再評価する。

計算量と制約

時間

O(N log(N+1))。各商人で一eventを追加し、clipによる全削除はO(N)。一clipの部分削除は左右各高々一つ。ordered mapとw,wzのFenwick更新・最小点検索はO(log N)、逆順復元はO(N)。C,Dの大きさに比例した展開をしない。

空間

O(N)。

制約との対応

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

出典

分類・前提・執筆情報

掲載状態: 収録済み

Travelling Salesman Problem の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: slope trick

主題
  • slope trick: 区分線形凸関数を左右breakpointのheapと定数項で表し、|x-a|追加・平行移動・prefix minimumを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: slope trick

    補助タグ: 構成解・witness復元 ordered set・multisetの動的順序管理

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

    学習の位置

    体系上の位置: slope trick

    • 区分線形凸関数を左右breakpointのheapと定数項で表し、|x-a|追加・平行移動・prefix minimumを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    • 一次元凸・単峰最適化 — 差分/導関数の単調性または単峰性を証明し、連続解近傍・ternary search・整数境界で最適点を求める。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
    • 成立証明から構成解を復元する — 存在条件の証明に対応する親・選択・局所操作を記録し、実際の構成へ戻す。
    • ordered set・multisetの動的順序管理 — 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題