概要

作品の色調値を並べ替えたときの、隣接差の絶対値の総和の最大値を求めます。
最大にするには、小さい値と大きい値をできるだけ交互に並べるのが重要です。

考察

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

そこで、各値が総和にどう貢献するかを考えます。

例えば、並びの中である値が両隣より大きい場合、

\(...,\ x,\ A_i,\ y,\ ...\)

となっていて \(A_i > x, A_i > y\) なら、隣接差への貢献は

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

となり、\(A_i\) は \(+2\) 回分足されます。

逆に、両隣より小さい場合は \(-2\) 回分引かれます。
つまり、

• 大きい値はできるだけ \(+2\) の係数を持たせたい
• 小さい値はできるだけ \(-2\) の係数を持たせたい

ということになります。

そのため、値を昇順にソートし、小さい側と大きい側を交互に並べるのが最適です。

ただし、列の両端の要素は隣が 1 個しかないため、係数は \(+1\) または \(-1\) にしかなりません。
この「端点による損失」を最小化するために、端点には中央付近の値を置くのがよいです。

ソート後の配列を \(A_0 \leq A_1 \leq \cdots \leq A_{N-1}\) とします。

\(N\) が偶数の場合

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

小さい側は \(A_0, A_1, \ldots, A_{m-1}\)、大きい側は \(A_m, A_{m+1}, \ldots, A_{2m-1}\) です。

理想的には、

• 小さい側すべてを \(-2\) 回
• 大きい側すべてを \(+2\) 回

使いたいので、まず

\(2 \sum_{i=m}^{2m-1} A_i - 2 \sum_{i=0}^{m-1} A_i\)

を考えます。

しかし、両端の要素は係数が \(2\) ではなく \(1\) になります。
偶数個の場合、交互に並べると端点は小さい側から 1 個、大きい側から 1 個になります。

損失を最小にするには、

• 小さい側の端点には最大の \(A_{m-1}\)
• 大きい側の端点には最小の \(A_m\)

を選べばよいです。

したがって答えは

\(2 \sum_{i=m}^{2m-1} A_i - 2 \sum_{i=0}^{m-1} A_i - (A_m - A_{m-1})\)

です。

\(N\) が奇数の場合

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

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

まず、中央を除いた小さい側・大きい側で

\(B = 2 \sum_{i=m+1}^{2m} A_i - 2 \sum_{i=0}^{m-1} A_i\)

とします。

中央 \(A_m\) を小さい側に入れる場合

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

端点には小さい側の中で大きい値を置きたいので、\(A_{m-1}\) と \(A_m\) を端点にします。
このときの損失は \(A_m - A_{m-1}\) です。

中央 \(A_m\) を大きい側に入れる場合

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

端点には大きい側の中で小さい値を置きたいので、\(A_m\) と \(A_{m+1}\) を端点にします。
このときの損失は \(A_{m+1} - A_m\) です。

よって、より損失が小さい方を選べばよく、答えは

\(B - \min(A_m - A_{m-1}, A_{m+1} - A_m)\)

となります。

例えば、ソート後の値が \([1, 2, 3, 8, 10]\) の場合、

\(B = 2(8 + 10) - 2(1 + 2) = 30\)

中央付近の差は

• \(3 - 2 = 1\)
• \(8 - 3 = 5\)

なので、答えは

\(30 - 1 = 29\)

です。

実際に \(2, 8, 1, 10, 3\) と並べると、

\(|2-8| + |8-1| + |1-10| + |10-3| = 6 + 7 + 9 + 7 = 29\)

になります。

アルゴリズム

1. 配列 \(A\) を昇順にソートする。
2. \(N = 1\) の場合、隣接する作品がないので答えは \(0\)。
3. \(N\) が偶数なら、上で導いた偶数の場合の式で答えを計算する。
4. \(N\) が奇数なら、上で導いた奇数の場合の式で答えを計算する。
5. 答えを出力する。

計算量

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

実装のポイント

• 答えは最大でおよそ \(10^6 \times 10^9 = 10^{15}\) 程度になるため、long long を使います。

• \(N = 1\) の場合は、\(A[m-1]\) などにアクセスできないため、先に処理しておきます。

• ソート後の添字はコードでは \(0\) 始まりで扱っています。

  ソースコード

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

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

    int N;
    cin >> N;

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

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

    if (N == 1) {
        cout << 0 << '\n';
        return 0;
    }

    long long ans = 0;

    if (N % 2 == 0) {
        int m = N / 2;

        for (int i = 0; i < m; i++) ans -= 2 * A[i];
        for (int i = m; i < N; i++) ans += 2 * A[i];

        ans -= A[m] - A[m - 1];
    } else {
        int m = N / 2;

        for (int i = 0; i < m; i++) ans -= 2 * A[i];
        for (int i = m + 1; i < N; i++) ans += 2 * A[i];

        ans -= min(A[m] - A[m - 1], A[m + 1] - A[m]);
    }

    cout << ans << '\n';

    return 0;
}

---

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