概要

この問題は、与えられた \(N\) 個の展望スポットの標高から \(K+1\) 個を選び、それらを一列に並べ替えて、隣り合う要素の差の絶対値の和（スリル値の合計）を最大化する問題です。

考察

1. 問題の言い換え

「\(N\) 個のスポットから隣り合う \(K\) 箇所に吊り橋を架ける」ということは、\(N\) 個の中から \(K+1\) 個のスポットを選び、それらを一列に並べるパスを作ることと同値です。 選んだ \(K+1\) 個のスポットの標高を、ソートして \(Y_1 \le Y_2 \le \dots \le Y_{K+1}\) とします。これらを並び替えた配列を \(X_1, X_2, \dots, X_{K+1}\) としたとき、最大化したい値は以下の通りです。 $\( \sum_{i=1}^{K} |X_{i+1} - X_i| \)$

2. 差の絶対値の和を最大化する並べ方（ジグザグ配置）

差の絶対値の合計を最大化するには、隣り合う要素が「（小さい）→（大きい）→（小さい）→（大きい）」と交互に並ぶ（ジグザグになる）ように配置するのが最適です。

例えば、選んだ4つの要素が \(Y = [1, 3, 6, 8]\) のとき、\([3, 8, 1, 6]\) と並べるのが最適です。このときのスリル値は、 $\( |8 - 3| + |1 - 8| + |6 - 1| = 5 + 7 + 5 = 17 \)\( となります。絶対値を外して式を展開してみると、 \)\( (8 - 3) + (8 - 1) + (6 - 1) = 2 \times 8 + 1 \times 6 - 2 \times 1 - 1 \times 3 \)\( となり、大きい方の要素には正の係数（\)+2, +1\(）、小さい方の要素には負の係数（\)-2, -1$）がかかることが分かります。

このように、要素数 \(K+1\) の偶奇によって、かかる係数のパターンが決まります。

3. \(K\) の偶奇による場合分け

値を最大化するためには、「正の大きな係数には \(A\) の中で最も大きい値を、負の大きな係数には \(A\) の中で最も小さい値を割り当てる」のが最適です。したがって、元の配列 \(A\) を昇順にソートした上で、両端から要素を割り当てていきます。

パターンA: \(K\) が奇数の場合（要素数 \(K+1\) が偶数）

要素数を \(2m + 2\) と表します（\(m = (K-1)/2\)）。 このとき、最適な係数の割り当ては以下の1通りに定まります。 - 大きい方から \(m\) 個に \(+2\)、次の1個に \(+1\) - 小さい方から \(m\) 個に \(-2\)、次の1個に \(-1\)

したがって、ソート済みの \(A\) に対して、最大値は以下のように計算できます。 $\( 2 \sum_{i=N-m}^{N-1} A_i + A_{N-m-1} - 2 \sum_{i=0}^{m-1} A_i - A_m \)$

パターンB: \(K\) が偶数の場合（要素数 \(K+1\) が奇数）

要素数を \(2m + 1\) と表します（\(m = K/2\)）。 このとき、ジグザグの端点が「山」になるか「谷」になるかで、以下の2つの係数パターンが考えられます。

1. 山が多いパターン
   • 大きい方から \(m-1\) 個に \(+2\)、次の2個に \(+1\)
   • 小さい方から \(m\) 個に \(-2\)
2. 谷が多いパターン
   • 大きい方から \(m\) 個に \(+2\)
   • 小さい方から \(m-1\) 個に \(-2\)、次の2個に \(-1\)

この2つのパターンのうち、計算結果が大きくなる方を採用します。

---

アルゴリズム

1. 展望スポットの標高配列 \(A\) を昇順にソートします。
2. \(K\) が奇数の場合：
   • パターンAの式に従って、スライスと sum() を用いて計算します。
3. \(K\) が偶数の場合：
   • パターンBの2つの式の計算値をそれぞれ求め、大きい方を採用します。

---

計算量

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

  • 配列 \(A\) のソートに \(O(N \log N)\) かかります。
  • その後の和の計算（スライスと sum()）は、最大でも \(O(N)\) で行えるため、ソートが全体のボトルネックとなります。\(N \le 10^6\) であるため、実行時間制限に十分間に合います。

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

  • 入力された配列 \(A\) を保持するためのメモリ空間が必要です。

---

実装のポイント

• \(K\) が偶数のときは2つのパターンを比較する必要があります。配列のインデックス（境界値）の指定が複雑になりやすいため、具体例（例えば \(K=2\) のときなど）を手元で動かしてインデックスがずれていないか確認すると安全です。

• Pythonでは sum(A[l:r]) を用いることで、指定した範囲の合計を高速に計算できます。

  ソースコード

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    K = int(data[1])
    A = [int(x) for x in data[2:]]
    A.sort()

    if K % 2 == 1:
        m = (K - 1) // 2
        ans = 2 * sum(A[N - m :]) + A[N - m - 1] - 2 * sum(A[:m]) - A[m]
    else:
        m1 = K // 2 - 1
        m2 = K // 2
        ans1 = (
            2 * sum(A[N - m1 :])
            + A[N - m2]
            + A[N - m2 - 1]
            - 2 * sum(A[:m2])
        )

        m3 = K // 2
        m4 = K // 2 - 1
        ans2 = (
            2 * sum(A[N - m3 :])
            - 2 * sum(A[:m4])
            - A[m4]
            - A[m4 + 1]
        )

        ans = max(ans1, ans2)

    print(ans)


if __name__ == "__main__":
    solve()

---

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