概要

\(N\) 個の値 \(A_i\) を好きな順番に並べ替えたとき、隣り合う値の差の絶対値の総和を最大化する問題です。

値をソートし、小さい値のグループと大きい値のグループを交互に並べると最大になります。

考察

まず、作品の番号自体には意味がなく、重要なのは色調値 \(A_i\) だけです。
そのため、値を昇順にソートして考えます。

ソート後の配列を \(A\) とします。

隣り合う 2 つの値の差 \(|x-y|\) は、大きい方から小さい方を引いた値です。
つまり、ある値は隣接する相手によって「足される側」または「引かれる側」になります。

ここで重要な観察は次の通りです。

• 大きい値はできるだけ多く「足される側」にしたい
• 小さい値はできるだけ多く「引かれる側」にしたい
• 各要素は列の内部にあれば最大 2 回、端にあれば 1 回しか隣接差に登場しない

したがって、最大化するには、小さい値と大きい値をなるべく交互に並べるのがよいです。

例えば、小さい値同士や大きい値同士を隣り合わせても差はあまり大きくなりません。
一方で、小さい値と大きい値を隣り合わせると、大きな差を作れます。

素朴にすべての並べ方を試すと \(N!\) 通りあり、\(N \leq 10^6\) では到底間に合いません。
そこで、ソート後の値の性質を使って、最大値を数式で直接求めます。

---

\(N\) が偶数の場合

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

ソート後の配列を、前半 \(m\) 個と後半 \(m\) 個に分けます。

• 小さい側: \(A_0, A_1, \ldots, A_{m-1}\)
• 大きい側: \(A_m, A_{m+1}, \ldots, A_{2m-1}\)

小さい側と大きい側を交互に並べると、ほとんどの要素は 2 回ずつ差に登場します。

理想的には、

• 大きい側はすべて \(2\) 回足される
• 小さい側はすべて \(2\) 回引かれる

ので、

\(2 \times (\text{大きい側の総和} - \text{小さい側の総和})\)

となります。

ただし、列の両端の要素は 1 回しか使われません。
偶数個の場合、端には小さい側から 1 個、大きい側から 1 個が来ます。

損を最小にするには、境界に近い

• 小さい側の最大値 \(A_{m-1}\)
• 大きい側の最小値 \(A_m\)

を端に置けばよいです。

よって最大値は、

\(2 \times (\text{大きい側の総和} - \text{小さい側の総和}) - (A_m - A_{m-1})\)

です。

コードでは次の形で計算しています。

\(2 \times (\text{high} - \text{low}) + A_{m-1} - A_m\)

---

\(N\) が奇数の場合

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

ソート後の配列を次のように分けます。

• 小さい側: \(A_0, A_1, \ldots, A_{m-1}\)
• 中央: \(A_m\)
• 大きい側: \(A_{m+1}, A_{m+2}, \ldots, A_{2m}\)

中央の値 \(A_m\) を、小さい側に入れるか、大きい側に入れるかの 2 通りを考えます。

---

1. 中央を小さい側に入れる場合

小さい側の個数が \(m+1\)、大きい側の個数が \(m\) になります。

この場合、交互に並べると両端は小さい側になります。
端に置く小さい側の値は 1 回しか引かれないため、できるだけ大きい値を端に置くと得です。

小さい側で大きい 2 つは、

• \(A_{m-1}\)
• \(A_m\)

です。

この場合の値は、

\(2 \times (\text{high} - \text{low}) + A_{m-1} - A_m\)

となります。

---

2. 中央を大きい側に入れる場合

小さい側の個数が \(m\)、大きい側の個数が \(m+1\) になります。

この場合、交互に並べると両端は大きい側になります。
端に置く大きい側の値は 1 回しか足されないため、できるだけ小さい値を端に置くと損が少ないです。

大きい側で小さい 2 つは、

• \(A_m\)
• \(A_{m+1}\)

です。

この場合の値は、

\(2 \times (\text{high} - \text{low}) + A_m - A_{m+1}\)

となります。

したがって、奇数の場合はこの 2 通りの大きい方を答えにします。

アルゴリズム

1. 配列 \(A\) を昇順にソートする
2. \(N = 1\) の場合、隣り合う要素がないので答えは \(0\)
3. \(m = \lfloor N/2 \rfloor\) とする
4. 小さい側の総和 low を求める
5. \(N\) が偶数なら、
   • 大きい側の総和 high を求める
   • 答えは
     \(2 \times (\text{high} - \text{low}) + A_{m-1} - A_m\)
6. \(N\) が奇数なら、
   • 中央 \(A_m\) を除いた大きい側の総和 high を求める
   • 次の 2 通りを比較する
     • 中央を小さい側に入れる: \(A_{m-1} - A_m\)
     • 中央を大きい側に入れる: \(A_m - A_{m+1}\)
   • 答えは
     \(2 \times (\text{high} - \text{low}) + \max(A_{m-1} - A_m,\ A_m - A_{m+1})\)

計算量

• 時間計算量: \(O(N \log N)\)
• 空間計算量: \(O(N)\)

ソートが最も重い処理です。
総和の計算は \(O(N)\) でできます。

実装のポイント

• \(N = 1\) の場合は答えが \(0\) なので、先に処理します。

• 答えは最大でおよそ \(10^{15}\) 程度になるため、C++ などでは long long が必要です。

• Python では整数が任意精度なので、そのままで問題ありません。

• コード中の << 1 は「2 倍する」という意味です。例えば x << 1 は 2 * x と同じです。

  ソースコード

import sys

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

    if N == 1:
        print(0)
        return

    m = N >> 1
    total = sum(A)
    low = sum(A[:m])

    if N & 1:
        high = total - low - A[m]
        add1 = A[m - 1] - A[m]
        add2 = A[m] - A[m + 1]
        ans = ((high - low) << 1) + (add1 if add1 > add2 else add2)
    else:
        high = total - low
        ans = ((high - low) << 1) + A[m - 1] - A[m]

    print(ans)

if __name__ == "__main__":
    main()

---

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