概要

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

考察

インパクト値を最大にするためには、隣り合う要素の差をできるだけ大きくする必要があります。 直感的には、「小さい値」と「大きい値」を交互に並べる（ジグザグに配置する）ことで、差の絶対値を最大化できます。

例えば、与えられた配列を昇順にソートしたものを \(A = [a_0, a_1, \ldots, a_{N-1}]\) とします。 要素数が偶数の場合と奇数の場合で、どのように並べると最適になるかを考えてみましょう。

1. \(N\) が偶数の場合（例: \(N = 4\)）

要素を小さいグループ \([a_0, a_1]\) と大きいグループ \([a_2, a_3]\) に分けます。 これらをジグザグに \([a_2, a_0, a_3, a_1]\) と並べたとき、インパクト値は以下のようになります。 $\( |a_2 - a_0| + |a_3 - a_0| + |a_3 - a_1| = (a_2 - a_0) + (a_3 - a_0) + (a_3 - a_1) = -2a_0 - a_1 + a_2 + 2a_3 \)\( 一般に \)N = 2m\(（偶数）のとき、最適な並び順における各要素の係数（足されるか引かれるか）は以下のようになります。 - 最も小さい \)m-1\( 個の要素：両隣が自分より大きいため、2回引かれる（係数 \)-2\(） - \)m\( 番目に小さい要素：端に配置されるため、1回だけ引かれる（係数 \)-1\(） - \)m+1\( 番目に小さい要素：端に配置されるため、1回だけ足される（係数 \)+1\(） - 最も大きい \)m-1\( 個の要素：両隣が自分より小さいため、2回足される（係数 \)+2$）

したがって、偶数の場合の最大インパクト値は以下のように一意に定まります。 $\( \text{Ans} = -2\sum_{i=0}^{m-2} a_i - a_{m-1} + a_m + 2\sum_{i=m+1}^{N-1} a_i \)$

---

2. \(N\) が奇数の場合（例: \(N = 5\)）

\(N = 2m+1\)（奇数）のときは、中央の要素 \(a_m\) を「小さいグループ」に含めるか、「大きいグループ」に含めるかで2通りの最適な並べ方が存在します。

• パターン1：大きいグループを多くする場合（小さい要素 \(m\) 個、大きい要素 \(m+1\) 個） 例として \([a_2, a_0, a_3, a_1, a_4]\) と並べると、インパクト値は次のようになります。 $\( |a_2 - a_0| + |a_3 - a_0| + |a_3 - a_1| + |a_4 - a_1| = -2a_0 - 2a_1 + a_2 + 2a_3 + a_4 \)$ 一般化すると：

  • 小さい方から \(m\) 個の要素は、係数 \(-2\)
  • 中央付近の2つの要素 \(a_m, a_{m+1}\) は、係数 \(+1\)
  • 大きい方から \(m-1\) 個の要素は、係数 \(+2\)

• パターン2：小さいグループを多くする場合（小さい要素 \(m+1\) 個、大きい要素 \(m\) 個） 例として \([a_0, a_3, a_1, a_4, a_2]\) と並べると、インパクト値は次のようになります。 $\( |a_3 - a_0| + |a_3 - a_1| + |a_4 - a_1| + |a_4 - a_2| = -a_0 - 2a_1 - a_2 + 2a_3 + 2a_4 \)$ 一般化すると：

  • 小さい方から \(m-1\) 個の要素は、係数 \(-2\)
  • 中央付近の2つの要素 \(a_{m-1}, a_m\) は、係数 \(-1\)
  • 大きい方から \(m\) 個の要素は、係数 \(+2\)

奇数の場合は、これら2つのパターンのうち値が大きくなる方が答えとなります。

アルゴリズム

1. 配列 \(A\) を昇順にソートします。
2. \(N = 1\) の場合は、隣り合う要素がないため 0 を出力して終了します。
3. \(N\) が偶数の場合は、上記の偶数用の式に当てはめて計算します。
4. \(N\) が奇数の場合は、パターン1とパターン2の計算をそれぞれ行い、大きい方の値を出力します。

計算量

• 時間計算量: \(O(N \log N)\) 配列のソートに \(O(N \log N)\) かかります。その後の累積計算は \(O(N)\) で行えるため、全体の計算量はソートがボトルネックとなります。
• 空間計算量: \(O(N)\) 入力された \(N\) 個の要素を保持するための配列（std::vector）のメモリです。

実装のポイント

• オーバーフローへの対策: \(A_i \le 10^9\) かつ \(N \le 10^6\) であるため、インパクト値の合計は int 型（最大約 \(2 \times 10^9\)）の範囲を容易に超えます。そのため、計算には必ず 64 ビット整数型（C++では long long）を使用してください。

• 入出力の高速化: \(N\) が最大 \(10^6\) と非常に大きいため、C++では std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); を用いて入出力を高速化しておくことで、実行時間制限（TLE）を安全に回避できます。

  ソースコード

#include <iostream>
#include <vector>
#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> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    if (n == 1) {
        cout << 0 << "\n";
        return 0;
    }
    
    sort(a.begin(), a.end());
    
    if (n % 2 == 0) {
        int m = n / 2;
        long long ans = 0;
        for (int i = 0; i < m - 1; ++i) {
            ans -= 2 * a[i];
        }
        ans -= a[m - 1];
        ans += a[m];
        for (int i = m + 1; i < n; ++i) {
            ans += 2 * a[i];
        }
        cout << ans << "\n";
    } else {
        int m = n / 2;
        long long ans1 = 0;
        for (int i = 0; i < m; ++i) {
            ans1 -= 2 * a[i];
        }
        ans1 += a[m];
        ans1 += a[m + 1];
        for (int i = m + 2; i < n; ++i) {
            ans1 += 2 * a[i];
        }

        long long ans2 = 0;
        for (int i = 0; i < m - 1; ++i) {
            ans2 -= 2 * a[i];
        }
        ans2 -= a[m - 1];
        ans2 -= a[m];
        for (int i = m + 1; i < n; ++i) {
            ans2 += 2 * a[i];
        }
        cout << max(ans1, ans2) << "\n";
    }
    
    return 0;
}

---

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