辺は \(\frac{N(N-1)}{2}\) 本あり、\(1\) つのハミルトンパスに含まれる辺は \(N\) 本、そしてハミルトンパスの総数は \((N-1)!\) です。

よって、ある長さ \(c\) の辺による最終的な答えへの寄与は \(2c\times (N-2)!\) です。

したがって、全ての辺の長さの総和を求め、それに \(2\times(N-2)!\) をかけたものが最終的な答えになります。

辺の長さの総和を愚直に計算していては間に合わないので、以下の式を利用します。

• \(\min(|x_i-x_j|,|y_i-y_j|) = |x_i-x_j| + |y_i-y_j| - \max(|x_i-x_j|,|y_i-y_j|)\)

また、\(X_i=\frac{x_i+y_i}{2},Y_i=\frac{x_i-y_i}{2}\) としたとき、

• \(\max(|x_i-x_j|,|y_i-y_j|) = |X_i-X_j| + |Y_i-Y_j|\)

が成り立ちます。以上から、求めたいものは、

• \(\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}(|x_i-x_j|+|y_i-y_j|-|X_i-X_j|-|Y_i-Y_j|)\)

です。\(x,y,X,Y\) は独立に考えることができ、ソートしておくことで絶対値を外すことができるので、次のような問題に帰着されます。

長さ \(N\) の数列 \(A=(A_1,A_2,\ldots,A_N)\) に対して、\(\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}(A_j-A_i)\) を求めよ。

各要素の寄与を考えると、この問題の答えは以下のようになります。

• \(\sum_{i=1}^{N}(2i-N-1)A_i\)

全体の計算量は \(O(N \log N)\) です。