問題
平面上に $N$ 個の点があり、$x$ 座標はすべて異なる。次の条件を満たす閉じた巡回路（全ての点をちょうど 1 回通って出発点に戻る）をバイトニック巡回路という。
- 最も左の点から出発して、$x$ 座標が単調に増える向きに進んで最も右の点に着き、そこから $x$ 座標が単調に減る向きに進んで出発点に戻る。
バイトニック巡回路の長さ（ユークリッド距離の総和）の最小値を求めよ。絶対誤差または相対誤差が $10^{-6}$ 以下なら正解とする。
入力形式
N
x_1 y_1
...
x_N y_N制約
| # | 条件 |
|---|---|
| 1 | $2\le N\le2000$ |
| 2 | $0\le x_i,y_i\le10^6$（整数） |
| 3 | $x_i$ は互いに異なる |
入出力例
入力例1
3
0 0
1 1
2 0出力例1
4.828427（3 点なので巡回路は一つだけ。$2+2\sqrt2$）
入力例2
4
0 0
1 2
2 1
3 3出力例2
8.944272入力例3
2
0 0
3 4出力例3
10.000000（往復で 5 の 2 倍）
背景と出典
バイトニック巡回路による最短巡回路の近似は、Bentley が 1990 年ごろに紹介したものを CLRS の演習問題（15 章の問題）で見た、と記憶している（本セッションでは原典を確認していない）。
この問題で確かめたいのは次の 3 点。(1) 「$x$ 順に点を足し、二本の経路の端を状態にする」DP が、定義どおりの全列挙（中間の点をどちらの経路に割り当てるかの $2^{N-2}$ 通り）と一致すること。(2) 状態を $i>j$ に限ると 1 次元のずらしだけで $O(N)$ 空間にできること。(3) バイトニックの最小が真の最短巡回路より長くなる頻度（絞ったことの代償）。
ヒント（クリックで段階的に開示）
ヒント1（方向性）
点を $x$ の小さい順に $p_0,\dots,p_{N-1}$ と並べる。最も左の点から出る二本の経路（上の経路と下の経路）を同時に右へ伸ばすと考える。点 $p_0,\dots,p_i$ を使い切った時点で、二本の経路の右端はどの点にあるか。
ヒント2（アプローチ）
$b[i][j]$（$j<i$）を、点 $0,\dots,i$ をすべて使い、二本の経路の端がそれぞれ $p_i$ と $p_j$ にあるときの、二本の長さの和の最小値とする。次の点 $p_{i+1}$ は、端 $p_i$ か端 $p_j$ のどちらかにつながる。つなぎ先で新しい状態がどうなるか。
ヒント3（誘導）
$p_i$ につなぐと状態は $(i+1,\,j)$ で長さは $d(i,i+1)$ 増える。$p_j$ につなぐと状態は $(i+1,\,i)$ で長さは $d(j,i+1)$ 増える。最終的に $p_{N-1}$ を二本の経路の合流点として、$b[N-1][j]+d(j,N-1)$ の最小を答える。$b[i][j]$ は $j<i-1$ なら $b[i-1][j]+d(i-1,i)$ なので、$j$ ごとの値に共通のずらしを持たせれば 1 次元で足りる。
模範解答 (Python)
模範解答を表示する（まず自力で解いてから）
import sys
from math import hypot
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
P = sorted((int(data[1+2*i]), int(data[2+2*i])) for i in range(n))
X = [p[0] for p in P]; Y = [p[1] for p in P]
def d(i, j):
return hypot(X[i]-X[j], Y[i]-Y[j])
if n == 2:
print("%.6f" % (2*d(0, 1))); return
# b[i][j] (j<i) = 点 0..i を二本の経路で覆い、端が i と j のときの長さの和の最小。
# b[i][j] = b[i-1][j] + d(i-1,i) (j<i-1) なので、j ごとの値は共通のずらし off を使って持つ。
B = [0.0]*n # B[j] + off = b[i][j]
off = d(0, 1) # b[1][0]
B[0] = 0.0
for i in range(2, n):
xi = X[i]; yi = Y[i]
# b[i][i-1] = min_j b[i-1][j] + d(j,i)
best = min(B[j] + off + hypot(X[j]-xi, Y[j]-yi) for j in range(i-1))
off += d(i-1, i)
B[i-1] = best - off
ans = min(B[j] + off + d(j, n-1) for j in range(n-1))
print("%.6f" % ans)
main()
計算量: 時間 $O(N^2)$、空間 $O(N)$。実測（Python 3.14、M1 Mac）で $N=2000$ のランダム入力が 1.23 s、$N=3000$ では 3.46 s（制約を 2000 にした理由）。
Step-by-Step 解説
巡回路を「左端から右端への上の経路」と「左端から右端への下の経路」の二本に分けると、どちらの経路も $x$ について単調に進む。巡回路の長さは二本の和。点を $x$ 順に一つずつ足していき、足した点は二本のどちらかの先頭につなぐ、と見れば点は $x$ 順に必ず使われる。
点 $0,\dots,i$ を使い切ったとき、点 $i$ はどちらかの経路の端である（最後に足した点だから）。もう一方の経路の端は $j<i$。上下の区別は意味を持たないので、$(i,j)$ の順序なしの組で足りる。$b[i][j]$ は二本の長さの和の最小値。
次の点 $i+1$ のつなぎ先は 2 通り。端 $i$ につなぐと状態は $(i+1,j)$、増加は $d(i,i+1)$。端 $j$ につなぐと、新しい端は $i+1$ と $i$ なので状態は $(i+1,i)$、増加は $d(j,i+1)$。$b[1][0]=d(0,1)$ から始める。
最後の点 $N-1$ では二本の経路が合流するので、状態 $(N-1,j)$ にさらに $d(j,N-1)$ を足して最小を取る。$N=2$ は往復で $2d(0,1)$ になるので別扱い。
$j<i-1$ の $b[i][j]$ は、前の行の値に $d(i-1,i)$ を足すだけ。そこで $B[j]+\text{off}=b[i][j]$ となるように共通の off を持ち、$j<i-1$ の更新は off += d(i-1,i) の 1 回にする。新しく作る $b[i][i-1]$ だけを $B[i-1]=b[i][i-1]-\text{off}$ として入れる。行列全体を持つ版（$N=3000$ で 9 百万要素）は実測 32.6 s、この版は 3.46 s。差の原因（メモリ確保か呼び出し回数か）の切り分けはしていない。
迷った他案と採らなかった理由
| 案 | 計算量 | 採否 | 理由 |
|---|---|---|---|
| $b[i][j]$ のずらし付き 1 次元 DP（本解） | $O(N^2)$、空間 $O(N)$ | 採用 | 中間の点の割り当て全列挙と 200 件全件一致 |
| $b[i][j]$ を行列で持つ素直な版 | $O(N^2)$、空間 $O(N^2)$ | 不採用 | $N=3000$ で 32.6 s（実測）。同じ漸化式だが 1 次元版は 3.46 s |
| 中間の点を上下に振り分ける全列挙 | $O(2^N N)$ | 検算用のみ | $N\le10$ でしか動かない |
| ビット DP の厳密な巡回セールスマン | $O(2^N N^2)$ | 不採用 | 別問題。$N\le20$ 程度でしか動かず、バイトニックとは答えも違う |
| 最近傍法などの貪欲 | $O(N^2)$ | 不採用 | 最適性の保証が無い（本問は最小値を求める） |
前提が変わったら:
- $x$ 座標が同じ点を許すと、点を並べる順序（同じ $x$ の中の順）で答えが変わりうる。本問は $x$ を相異なるとしたので扱っていない
- バイトニックでなくてよい（普通の巡回セールスマン）なら NP 困難。実測で、$N\le8$ の 200 件中 36 件はバイトニックの最小が真の最短巡回路より長かった。バイトニックは近似であって最適解ではない
- $N\ge10^5$ のときは $O(N^2)$ が届かない。バイトニックの最小を $O(N\log N)$ で求める方法があるかは知らない（未確認）。本問では扱わない
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 点を $x$ 順に並べ替えない | 入力順のままで DP してしまう | 先に sorted |
| $N=2$ を DP に通す | 点 2 個では二本の経路が同じ辺になる | $2d(0,1)$ を直接出力 |
| 最後に $b[N-1][j]$ だけを答える | 合流する最後の辺 $d(j,N-1)$ を足し忘れる | + d(j, n-1) を足して最小 |
off を更新する前に新しい端を入れる | $B[i-1]$ に入れる値は新しい off を引いたもの | off += ... の後に B[i-1] = best - off |
次のステップ
- 発展1: 巡回路そのものを復元して出力する（親ポインタを $O(N^2)$ の配列で持つ）
- 発展2: 巡回路でなく、点 $1$ から点 $N$ への経路で $x$ 単調ではない部分を許す版との差を数える
- 次回予告: 焦点帯外（M2・M3）を含む通常のローテーション
検証ログ（本セッションで実行した数値）
- 全列挙との照合（実測）: $N\le10$ の 200 件で、中間の点をどちらの経路に割り当てるかの全列挙による最小値とプログラムの出力（小数 6 桁）が全件で $10^{-4}$ 以内に一致
- 真の最短巡回路との比較（実測）: $3\le N\le8$ の 200 件中、バイトニックの最小が真の最短巡回路（全順列）より長いものが 36 件。下回るものは 0 件（バイトニックは巡回路の一種なので当然）
- 入力例（実測）: 例 1 は 4.828427、例 2 は 8.944272、例 3 は 10.000000
- 実行時間（実測）: $N=2000$ で 1.23 s、$N=3000$ で 3.46 s。行列を持つ版は $N=3000$ で 32.6 s
- 浮動小数の誤差: ずらし
offを使う分、桁落ちが起きうるが、$N\le10$ の照合は $10^{-4}$ 以内で通った。大きな $N$ での誤差評価はしていない - 扱っていない範囲: $x$ の重複、巡回路の復元、$N\ge10^5$ の高速化、原典（CLRS・Bentley）の確認