概要

\(N\) 個の値を自由に並べ替え、隣り合う値の差の絶対値の総和を最大化する問題です。
値を昇順にソートし、「小さい値」と「大きい値」を交互に並べる形を考えると、最大値を数式で求められます。

考察

以降、ソート後の配列を

\( a_0 \leq a_1 \leq \cdots \leq a_{N-1} \)

とします。

全ての配置を試すと \(N!\) 通りあり、\(N \leq 10^6\) では到底間に合いません。
また、単純に「差が大きいペアから順に作る」ような貪欲法も、どの値を端に置くかで損失が変わるため正しくありません。

重要なのは、各値が総和にどのように寄与するかを見ることです。

隣接する 2 つの値が \(x \leq y\) のとき、その寄与は

\( |x-y| = y-x \)

です。つまり、大きい方は \(+1\) 回、小さい方は \(-1\) 回だけ総和に現れます。

ある値について考えると、

• 端に置かれた値は隣が 1 つなので、係数は \(+1\) または \(-1\)
• 内部に置かれた値は隣が 2 つなので、係数は \(+2, 0, -2\) のいずれか

になります。

最大化するには、大きい値に正の係数、小さい値に負の係数を付けたいです。
そのため、基本的には

• 小さい値を「谷」
• 大きい値を「山」

にして交互に並べるのが最適になります。

\(N\) が偶数の場合

\(N=2m\) とします。

小さい側を

\( a_0, a_1, \ldots, a_{m-1} \)

大きい側を

\( a_m, a_{m+1}, \ldots, a_{2m-1} \)

と分けます。

交互に並べると、小さい側は負、大きい側は正の寄与になります。
もし全ての小さい値が \(-2\)、全ての大きい値が \(+2\) として寄与できるなら、

\( 2 \times \left(\sum_{i=m}^{2m-1} a_i - \sum_{i=0}^{m-1} a_i\right) \)

になります。

しかし実際には列には端が 2 つあり、端の値は 1 回しか隣接しません。
偶数個の場合、端には小さい側から 1 つ、大きい側から 1 つ置くのが最適です。

端に置くなら、

• 小さい側では、なるべく大きい \(a_{m-1}\) を端にする
• 大きい側では、なるべく小さい \(a_m\) を端にする

のが損失を最小にします。

したがって最大値は

\( 2 \times \left(\sum_{i=m}^{2m-1} a_i - \sum_{i=0}^{m-1} a_i\right) - (a_m-a_{m-1}) \)

です。

\(N\) が奇数の場合

\(N=2m+1\) とします。

中央値は \(a_m\) です。
この中央値を「小さい側」に入れるか「大きい側」に入れるかで 2 通り考えます。

1. \(a_m\) を小さい側に入れる場合

小さい側は \(m+1\) 個、大きい側は \(m\) 個です。
交互に並べると、小さい側が両端になります。

端に置く小さい側の値は、なるべく大きい方がよいので、\(a_{m-1}\) と \(a_m\) を端にします。

このとき最大値は

\( 2 \times \left(\sum_{i=m+1}^{2m} a_i - \sum_{i=0}^{m-1} a_i\right) - (a_m-a_{m-1}) \)

です。

2. \(a_m\) を大きい側に入れる場合

大きい側は \(m+1\) 個、小さい側は \(m\) 個です。
交互に並べると、大きい側が両端になります。

端に置く大きい側の値は、なるべく小さい方がよいので、\(a_m\) と \(a_{m+1}\) を端にします。

このとき最大値は

\( 2 \times \left(\sum_{i=m+1}^{2m} a_i - \sum_{i=0}^{m-1} a_i\right) - (a_{m+1}-a_m) \)

です。

よって奇数の場合は、上の 2 通りのうち大きい方、つまり

\( 2 \times \left(\sum_{i=m+1}^{2m} a_i - \sum_{i=0}^{m-1} a_i\right) - \min(a_m-a_{m-1}, a_{m+1}-a_m) \)

になります。

例えば \([1,2,3,4,5]\) の場合、

\( 2 \times ((4+5)-(1+2)) - \min(3-2,4-3) = 12-1=11 \)

で、実際に \(2,4,1,5,3\) と並べると

\( |2-4|+|4-1|+|1-5|+|5-3|=2+3+4+2=11 \)

となります。

アルゴリズム

1. 配列 \(C\) を昇順にソートする。
2. \(m=\lfloor N/2 \rfloor\) とする。
3. 小さい側の和 low を求める。
4. \(N\) の偶奇で場合分けする。
   • \(N\) が偶数の場合
     $\( \text{ans} = 2 \times \left(\sum_{i=m}^{N-1} a_i - \sum_{i=0}^{m-1} a_i\right) - (a_m-a_{m-1}) \)$
   • \(N\) が奇数の場合
     $\( \text{ans} = 2 \times \left(\sum_{i=m+1}^{N-1} a_i - \sum_{i=0}^{m-1} a_i\right) - \min(a_m-a_{m-1}, a_{m+1}-a_m) \)$

コードでは total を使って、必要な和を効率よく計算しています。

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートが支配的です。
• 空間計算量: \(O(N)\)
  • 配列を保持するために必要です。

実装のポイント

• 答えは最大でおよそ \(10^{15}\) になるため、C++ などでは long long が必要です。Python では整数が任意精度なので問題ありません。

• \(N\) が奇数の場合、\(N \geq 3\) なので a[m-1], a[m], a[m+1] は必ず存在します。

• 入力サイズが大きいので、Python では sys.stdin.buffer.readline を使うと安全です。

• n >> 1 は n // 2 と同じ意味です。

  ソースコード

import sys

def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()

    m = n >> 1
    total = sum(a)

    low = 0
    for i in range(m):
        low += a[i]

    if n & 1:
        high = total - low - a[m]
        ans = 2 * (high - low) - min(a[m] - a[m - 1], a[m + 1] - a[m])
    else:
        ans = 2 * (total - 2 * low) - (a[m] - a[m - 1])

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。