Day 090-Q2 — 双調巡回セールスマン問題（Bitonic TSP）

問題

平面上に $N$ 個の点（$x$ 座標はすべて相異なる）が与えられる。双調巡回路とは、最も $x$ が小さい点から出発し $x$ 単調増加で最も $x$ が大きい点へ至り（上側経路）、そこから $x$ 単調減少で出発点に戻る（下側経路）、という条件ですべての点をちょうど1回訪れる閉路のこと。総移動距離が最小の双調巡回路の長さを求めよ。

入出力例

3
0 0
1 2
2 0

6.4721359550

5
1 1
2 3
3 1
4 3
5 1

10.4721359550

例2: ジグザグ配置。単純な往復（$4\sqrt5+4\approx12.94$）より上下経路をうまく振り分けた方が短くなる。

概念図: ジグザグ点を上側・下側経路に振り分ける

ヒント

dp[0][1] = dist(0, 1)
for j in range(2, n):
    for i in range(j):
        if i < j - 1:
            dp[i][j] = dp[i][j-1] + dist(j-1, j)
        else:  # i == j-1
            dp[j-1][j] = min(dp[k][j-1] + dist(k, j) for k in range(j-1))
answer = min(dp[i][n-1] + dist(i, n-1) for i in range(n-1))

模範解答

import sys
import math

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    pts = []
    for _ in range(n):
        x = int(data[idx]); idx += 1
        y = int(data[idx]); idx += 1
        pts.append((x, y))
    pts.sort()

    def dist(a, b):
        return math.hypot(pts[a][0] - pts[b][0], pts[a][1] - pts[b][1])

    if n == 2:
        print(f"{dist(0, 1) * 2:.10f}")
        return

    INF = float('inf')
    dp = [[INF] * n for _ in range(n)]
    dp[0][1] = dist(0, 1)

    for j in range(2, n):
        d_j1_j = dist(j - 1, j)
        for i in range(j - 1):
            dp[i][j] = dp[i][j - 1] + d_j1_j
        best = INF
        for k in range(j - 1):
            v = dp[k][j - 1] + dist(k, j)
            if v < best:
                best = v
        dp[j - 1][j] = best

    ans = min(dp[i][n - 1] + dist(i, n - 1) for i in range(n - 1))
    print(f"{ans:.10f}")

main()

計算量: 状態数 $O(N^2)$、遷移は各 $j$ で合計 $O(N)$ の走査（i==j-1 の行のみ）なので全体 $O(N^2)$。

Step-by-Step 解説

Step 1: $x$ 座標でソートして追加順序を固定

点を $x$ 昇順に処理すれば、新しく追加する点は常にその時点で最も右にある点になる。

Step 2: 状態を $(i,j)$ に圧縮できる理由

片方の末端が常に「直近に追加した点」に固定されるため、独立な自由度は実質 $i$ 側の1つだけになり、状態数が $O(N^2)$ に抑えられる。

Step 3: 2種類の遷移

Step 4: 最終的な閉路の形成

配置し終えたら2本の経路の末端はどちらも点 $n-1$ に到達している。最後にその末端同士を直接結んで閉路を閉じる。

よくあるミス

次のステップ

• 発展問題: 一般の平面TSPを小さい $N$（$\le15$程度）で bitDP により厳密に解く
• 発展問題: 双調巡回路の実際の訪問順序を遷移元の記録から復元する

自己評価