ABC 448 F — Authentic Traveling Salesman Problem

考察

要求は全点を一度ずつ訪れて戻る巡回で、総Manhattan距離が10^10以下ならよい。x方向を幅Bのstripへ分け、strip内をy昇順・降順で交互に並べると、蛇行するHamilton cycleが得られる。

この問題では W=2×10^7、N≤60000 に対して B=82000 と固定する。x座標が0..Wなのでstripは高々244個。横移動は各stripの中央x座標を経由する仮想経路で抑える。n_s点あるstripの中では、両端から中央への移動が合計B以下、点間が(n_s−1)B以下なので合計n_s B以下。中央どうしの単調移動と閉路復帰は2W以下で、全横移動はNB+2W以下。空stripも含む全244区画を上下端まで蛇行する仮想経路を考える。実際の点間移動はこの経路を飛ばすshortcutなので、strip境界の移動込みで縦移動は244W以下、復帰を加えて245W以下。合計は NB+247W ≤ 60000×82000+247×20000000 = 9.86×10^9 < 10^10。

採用する候補: strip番号順に点を並べ、stripごとにyの向きを交互に反転する。

最適TSPを解かずに、制約の数値上限を満たす構成を作れる。

棄却する候補: 最近傍未訪問点を選ぶ貪欲。

局所選択だけでは総距離の上限を保証できない。

典型の発動条件

空間 strip の蛇行構成

発動条件: 平面上の全点巡回を厳密最適化せず距離上界付きで構成したいとき。

細長い領域ごとに順方向を交互にして Hamilton cycle を作る。

上界式の parameter balancing

発動条件: 構成コストが A/B+CB の形で評価できるとき。

二項を均衡させる B を選んで最悪上界を最小化する。

問題固有の要素

出力構築問題では最適 TSP を解かず、制約値を下回ることを証明できる規則的巡回を設計する。

別の問題へ持ち帰る視点: Mo順のような蛇行 sort は、区画をまたぐたびの大きな座標方向の戻りを相殺する。

正当性

strip番号とその偶奇に応じたy順で並べれば、各点を一度ずつ訪れる。空stripも含む仮想の蛇行を点間で飛ばしても、三角不等式により縦の総移動量は増えず、最後の復帰込みで245W以下である。横方向もstrip中央を挟む経路をshortcutしたものとしてNB+2Wで抑えられるので、考察の数値上界が全巡回に成立する。

実装上の注意

  • key=(floor(x/B), strip番号の偶奇に応じた±y) でsortし、B=82000を使う。stripは最大244個。
  • 出力を点1から始めるようrotateし、最後から点1への距離も上界に含める。

復習の核

  • 縦・同strip横・strip間・閉路復帰の四項を別々に上界評価し、選んだ B で10^10以下となる数値まで確認する。

計算量と制約

時間

O(N log N)、strip keyでsort、output rotate O(N)。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 6 \times 10^4; 0 \leq X_i \leq 2 \times 10^7; 0 \leq Y_i \leq 2 \times 10^7; (X_i, Y_i) \neq (X_j, Y_j) if i \neq j; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 成立証明から構成解を復元する

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

      主タグ: 構成解・witness復元

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

      学習の位置

      体系上の位置: 成立証明から構成解を復元する

      • 成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。

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

      • 存在判定・個数計算だけで、具体的な解や操作列を復元しない問題。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題