概要

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

数値を「大きいグループ」と「小さいグループ」に分け、それらを交互に並べる（ジグザグに配置する）ことで、差の絶対値を最大化することができます。

---

考察

1. インパクト値を最大化する直感的なアイデア

隣り合う要素の差の絶対値を大きくするためには、「大きい数」と「小さい数」を交互に並べる（ジグザグに配置する） のが最適です。

例えば、ソートされた配列 \(A = [A_0, A_1, A_2, A_3]\) があるとき、これを単に順番に並べると差の合計は小さくなりますが、\([A_1, A_3, A_0, A_2]\) のように「小・大・小・大」と交互に並べることで、各隣接差を「大 \(-\) 小」の形にすることができ、合計値を大きくできます。

2. 各要素が合計値に与える影響（係数）

数値をジグザグに並べたとき、各数値が合計値にどのように足し引きされるかを考えます。 一列に並べたときの各位置の要素は、以下のルールで最終的な合計値に寄与します。

• 山（両隣より大きい要素）: 隣り合う2つの要素との差で、それぞれ「大きい数 \(-\) 小さい数」として計算されるため、合計値に \(+2\) 倍 されて寄与します。
• 谷（両隣より小さい要素）: 同様に、合計値から \(-2\) 倍 されて寄与します。
• 端の要素（列の左端・右端）: 隣が1つしかないため、山であれば \(+1\) 倍、谷であれば \(-1\) 倍 の寄与にとどまります。

この性質を利用して、配列を昇順にソートした上で、要素数 \(N\) の偶奇によって最適な配置を数式化します。

---

3. \(N\) が偶数の場合

要素数 \(N = 2M\) のとき、小さいグループ \(L = \{A_0, \dots, A_{M-1}\}\) と、大きいグループ \(R = \{A_M, \dots, A_{2M-1}\}\) に綺麗に二等分できます。

このとき、端の要素は「山（大きいグループ）」から1つ、「谷（小さいグループ）」から1つ選ばれます。 インパクト値を最大化するためには： - 引かれる回数を減らすため、小さいグループの中で最も大きい \(A_{M-1}\) を端に置く（係数は \(-1\)）。それ以外の小さい要素は \(-2\) 倍。 - 足される回数を増やすため、大きいグループの中で最も小さい \(A_M\) を端に置く（係数は \(+1\)）。それ以外の大きい要素は \(+2\) 倍。

これを数式に表すと、以下のようになります。 $\( \text{ans} = 2 \times \sum_{i=M+1}^{N-1} A_i + A_M - A_{M-1} - 2 \times \sum_{i=0}^{M-2} A_i \)$

---

4. \(N\) が奇数の場合

要素数 \(N = 2M + 1\) のとき、ジグザグの並べ方は以下の2パターンが考えられます。

パターン1：山が多い配置（大・小・大・…・大）

大きいグループが \(M+1\) 個、小さいグループが \(M\) 個となります。 両端はともに「山（大きい要素）」になります。 - 足される回数を最大化するため、大きいグループのうち最も小さい2つの要素 \(A_M, A_{M+1}\) を端に置きます（係数は \(+1\)）。残りの大きい要素は \(+2\) 倍。 - 小さい要素 \(A_0, \dots, A_{M-1}\) はすべて中央の谷になるため、\(-2\) 倍。

\[ \text{ans1} = 2 \times \sum_{i=M+2}^{N-1} A_i + A_{M+1} + A_M - 2 \times \sum_{i=0}^{M-1} A_i \]

パターン2：谷が多い配置（小・大・小・…・小）

小さいグループが \(M+1\) 個、大きいグループが \(M\) 個となります。 両端はともに「谷（小さい要素）」になります。 - 引かれる回数を最小化するため、小さいグループのうち最も大きい2つの要素 \(A_{M-1}, A_M\) を端に置きます（係数は \(-1\)）。残りの小さい要素は \(-2\) 倍。 - 大きい要素 \(A_{M+1}, \dots, A_{N-1}\) はすべて中央の山になるため、\(+2\) 倍。

\[ \text{ans2} = 2 \times \sum_{i=M+1}^{N-1} A_i - A_M - A_{M-1} - 2 \times \sum_{i=0}^{M-2} A_i \]

この2つのパターンのうち、値が大きい方を最大値として採用します。

---

アルゴリズム

1. コーナーケースの処理: \(N=1\) のときは隣り合う要素がないため、答えは 0 です。
2. ソート: 与えられた配列 \(A\) を昇順にソートします。
3. 場合分けと計算:
   • \(N\) が偶数の場合、上記の偶数用の式で計算します。
   • \(N\) が奇数の場合、パターン1（山が多い）とパターン2（谷が多い）の2つの値を計算し、大きい方を選択します。
4. 出力: 計算された最大値を出力します。

---

計算量

• 時間計算量: \(O(N \log N)\) 配列のソートに \(O(N \log N)\) の時間がかかります。ソート後のスライスを用いた和の計算は \(O(N)\) であるため、全体の時間計算量はソートがボトルネックとなり \(O(N \log N)\) です。制約の \(N \le 10^6\) に対しても、実行時間制限内に十分間に合います。
• 空間計算量: \(O(N)\) 入力された配列 \(A\) を保持するために \(O(N)\) のメモリを使用します。

---

実装のポイント

• スライスの範囲指定: Pythonでのリストのスライス（A[start:end]）は、end のインデックスを含まない（半開区間）ことに注意してインデックスを設定します。

• \(N=1\) の考慮: ソートや分割を行う前に、要素数が \(1\) の場合を早期リターン（Early Return）で除外することで、インデックスエラーを防ぎます。

  ソースコード

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    if N == 1:
        print(0)
        return

    A = [int(x) for x in input_data[1:]]
    A.sort()

    if N % 2 == 0:
        M = N // 2
        ans = sum(A[M + 1 :]) * 2 + A[M] - A[M - 1] - sum(A[: M - 1]) * 2
    else:
        M = N // 2
        ans1 = sum(A[M + 2 :]) * 2 + A[M + 1] + A[M] - sum(A[:M]) * 2
        ans2 = sum(A[M + 1 :]) * 2 - A[M] - A[M - 1] - sum(A[: M - 1]) * 2
        ans = max(ans1, ans2)

    print(ans)


if __name__ == "__main__":
    solve()

---

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