概要

与えられた \(N\) 個の数値を一列に並べ替えて、隣り合う要素の差の絶対値の総和（総コントラスト）を最大化する問題です。

考察

1. 総コントラストを最大化するための基本的な考え方

並び替えた後の配列を \(A_1, A_2, \ldots, A_N\) とします。求める値は \(\sum_{i=1}^{N-1} |A_i - A_{i+1}|\) です。

絶対値の記号を外すことを考えます。総和を最大化するためには、「大きい数」と「小さい数」を交互に配置することで、各隣り合うペアの差が常に「(大きい数) - (小さい数)」の形になるように並べるのが最適です。

このように交互に並べると、各要素 \(C_i\) が総和に寄与する符号（\(+\) または \(-\)）と、その回数（係数）が決まります。 - 「谷」となる要素（小さい数）: 両隣の要素より小さいため、差の計算においてマイナスの符号（\(-1\) または \(-2\)）で寄与します。 - 「山」となる要素（大きい数）: 両隣の要素より大きいため、プラスの符号（\(+1\) または \(+2\)）で寄与します。 - 端にある要素: 隣り合う要素が \(1\) つしかないため、寄与する回数は \(1\) 回（係数は \(\pm 1\)）になります。 - 内側にある要素: 隣り合う要素が \(2\) つあるため、寄与する回数は \(2\) 回（係数は \(\pm 2\)）になります。

この性質を利用し、与えられた配列 \(C\) を昇順にソートして \(C_0 \leq C_1 \leq \ldots \leq C_{N-1}\) とした上で、要素を「小さいグループ（谷）」と「大きいグループ（山）」に分けて考えます。

---

2. \(N\) が偶数の場合（\(N = 2k\)）

要素を半分に分け、小さいグループ \(k\) 個（\(C_0, \ldots, C_{k-1}\)）と、大きいグループ \(k\) 個（\(C_k, \ldots, C_{2k-1}\)）にします。

このとき、端の一方を山、もう一方を谷にする並べ方が最適です（例：谷, 山, 谷, 山, \(\ldots\), 谷, 山）。 - 山の中で最も小さい \(C_k\) を端に配置し、係数を \(+1\) にします。それ以外の山は内側に配置して係数を \(+2\) にします。 - 谷の中で最も大きい \(C_{k-1}\) を端に配置し、係数を \(-1\) にします。それ以外の谷は内側に配置して係数を \(-2\) にします。

したがって、最大値は以下の式で求まります。 $\( \text{Ans} = 2 \sum_{i=k}^{N-1} C_i - C_k - 2 \sum_{i=0}^{k-1} C_i + C_{k-1} \)$

---

3. \(N\) が奇数の場合（\(N = 2k+1\)）

山と谷の個数のバランスが \(1\) つずれるため、以下の 2 つのパターンを比較する必要があります。

パターン 1：山が \(k+1\) 個、谷が \(k\) 個の場合

端の \(2\) つが両方とも「山」になります（例：山, 谷, 山, \(\ldots\), 谷, 山）。 - 山の中で最も小さい \(2\) つの要素 \(C_k, C_{k+1}\) を端に配置し、係数を \(+1\) にします。残りの山は係数 \(+2\) です。 - 谷はすべて内側に入るため、係数はすべて \(-2\) になります。

\[ \text{Ans}_1 = 2 \sum_{i=k+2}^{N-1} C_i + C_k + C_{k+1} - 2 \sum_{i=0}^{k-1} C_i \]

パターン 2：山が \(k\) 個、谷が \(k+1\) 個の場合

端の \(2\) つが両方とも「谷」になります（例：谷, 山, 谷, \(\ldots\), 山, 谷）。 - 谷の中で最も大きい \(2\) つの要素 \(C_{k-1}, C_k\) を端に配置し、係数を \(-1\) にします。残りの谷は係数 \(-2\) です。 - 山はすべて内側に入るため、係数はすべて \(+2\) になります。

\[ \text{Ans}_2 = 2 \sum_{i=k+1}^{N-1} C_i - 2 \sum_{i=0}^{k-2} C_i - C_{k-1} - C_k \]

この \(2\) つのパターンのうち、値が大きい方を答えとします。

アルゴリズム

1. 入力された配列 \(C\) を昇順にソートします。
2. \(N\) が偶数の場合は、偶数用の数式を用いて総コントラストを計算します。
3. \(N\) が奇数の場合は、奇数のパターン 1 とパターン 2 の両方を計算し、大きい方を採用します。
4. 計算した最大値を出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 配列のソートに \(O(N \log N)\) かかります。
  • その後の部分和の計算は \(O(N)\) で行えるため、全体のボトルネックはソート部分となります。
• 空間計算量: \(O(N)\)
  • 入力された配列 \(C\) を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• オーバーフローの防止: \(N\) が最大 \(10^6\)、各 \(C_i\) が最大 \(10^9\) であるため、総コントラストは最大で \(10^{15}\) 程度に達します。32ビット整数型ではオーバーフローするため、計算には必ず 64 ビット整数型（C++ では long long）を使用してください。

• 高速入出力: \(N\) の値が大きいため、C++ では cin.tie(NULL) や ios_base::sync_with_stdio(false) を用いて入出力を高速化しておくことで、実行時間制限に余裕を持って間に合わせることができます。

  ソースコード

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    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 k = N / 2;
        long long sum_L = 0;
        for (int i = 0; i < k; ++i) sum_L += C[i];
        long long sum_R = 0;
        for (int i = k; i < N; ++i) sum_R += C[i];
        ans = 2 * sum_R - C[k] - 2 * sum_L + C[k - 1];
    } else {
        int k = N / 2;
        // パターン 1: 小さいグループが k 個、大きいグループが k+1 個
        long long sum_L1 = 0;
        for (int i = 0; i < k; ++i) sum_L1 += C[i];
        long long sum_R1_rest = 0;
        for (int i = k + 2; i < N; ++i) sum_R1_rest += C[i];
        long long ans1 = 2 * sum_R1_rest + C[k] + C[k + 1] - 2 * sum_L1;

        // パターン 2: 小さいグループが k+1 個、大きいグループが k 個
        long long sum_L2_rest = 0;
        for (int i = 0; i < k - 1; ++i) sum_L2_rest += C[i];
        long long sum_R2 = 0;
        for (int i = k + 1; i < N; ++i) sum_R2 += C[i];
        long long ans2 = 2 * sum_R2 - 2 * sum_L2_rest - C[k - 1] - C[k];

        ans = max(ans1, ans2);
    }

    cout << ans << "\n";

    return 0;
}

---

この解説は gemini-3.5-flash-high によって生成されました。