概要

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

ポイントは、値を昇順にソートし、「小さい値」と「大きい値」ができるだけ交互に並ぶような配置を考えることです。

考察

まず、値を昇順に並べたものを

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

とします。

素朴に全ての並べ方を試すと \(N!\) 通りあり、\(N \leq 10^6\) なので到底間に合いません。

隣り合う \(2\) つの値 \(x, y\) について、\(x < y\) ならその差は

\( y - x \)

です。

つまり、総コントラストは

• 大きい側として足される値の合計
• 小さい側として引かれる値の合計

の差として考えられます。

各要素は最大でも左右 \(2\) つの隣接要素としか関わらないので、ある値が「足される側」または「引かれる側」として現れる回数は高々 \(2\) 回です。

したがって、最大化するには直感的に

• 大きい値をできるだけ \(+2\) 回使う
• 小さい値をできるだけ \(-2\) 回使う
• 端に置かれる要素は \(1\) 回しか使われないので、できるだけ中央付近の値を端にしたい

という形になります。

---

\(N\) が偶数の場合

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

小さい側を

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

大きい側を

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

と分けます。

理想的には、大きい側の値を \(+2\) 回、小さい側の値を \(-2\) 回使いたいです。

しかし、並びの両端の要素は \(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}) \)

になります。

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

\( 2 \times ((4+5+6) - (1+2+3)) - (4-3) = 17 \)

です。

実際に

\( 3, 6, 1, 5, 2, 4 \)

と並べると、総和は

\( 3 + 5 + 4 + 3 + 2 = 17 \)

になります。

---

\(N\) が奇数の場合

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

中央値は \(a_m\) です。

小さい側を

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

大きい側を

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

とします。

中央値 \(a_m\) を除いて考えると、小さい側と大きい側はどちらも \(m\) 個ずつです。

理想的な値は

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

ですが、中央値 \(a_m\) も必ずどこかに配置しなければなりません。

中央値を使うことで、以下のどちらかの損失が発生します。

• 中央値を小さい側として扱う場合、\(a_m - a_{m-1}\) の損失
• 中央値を大きい側として扱う場合、\(a_{m+1} - a_m\) の損失

損失は小さい方を選べばよいので、最大値は

\( 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) = 11 \)

です。

実際に

\( 2, 4, 1, 5, 3 \)

と並べると、

\( 2 + 3 + 4 + 2 = 11 \)

になります。

アルゴリズム

1. 配列 \(C\) を昇順にソートする。
2. \(N\) が偶数か奇数かで場合分けする。
3. 偶数の場合：
   • \(m = N/2\)
   • 小さい側の和を \(\text{low} = \sum_{i=0}^{m-1} a_i\)
   • 大きい側の和を \(\text{high} = \sum_{i=m}^{N-1} a_i\)
   • 答えは
     \( 2(\text{high} - \text{low}) - (a_m - a_{m-1}) \)
4. 奇数の場合：
   • \(m = N/2\)
   • 小さい側の和を \(\text{low} = \sum_{i=0}^{m-1} a_i\)
   • 大きい側の和を \(\text{high} = \sum_{i=m+1}^{N-1} a_i\)
   • 答えは
     \( 2(\text{high} - \text{low}) - \min(a_m - a_{m-1}, a_{m+1} - a_m) \)
5. 答えを出力する。

計算量

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

実装のポイント

答えは最大でおよそ \((N-1) \times 10^9\) となり、\(10^{15}\) 程度になる可能性があります。

そのため、int ではなく long long を使う必要があります。

また、\(N \leq 10^6\) と大きいので、C++ では高速入出力のために

ios::sync_with_stdio(false);
cin.tie(nullptr);

を入れておくと安全です。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<long long> C(N);
    for (int i = 0; i < N; i++) cin >> C[i];

    sort(C.begin(), C.end());

    long long ans = 0;

    if (N % 2 == 0) {
        int m = N / 2;
        long long low = 0, high = 0;

        for (int i = 0; i < m; i++) low += C[i];
        for (int i = m; i < N; i++) high += C[i];

        ans = 2 * (high - low) - (C[m] - C[m - 1]);
    } else {
        int m = N / 2;
        long long low = 0, high = 0;

        for (int i = 0; i < m; i++) low += C[i];
        for (int i = m + 1; i < N; i++) high += C[i];

        ans = 2 * (high - low) - min(C[m] - C[m - 1], C[m + 1] - C[m]);
    }

    cout << ans << '\n';
    return 0;
}

---

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