概要

展望スポットを好きな順に並べ、隣り合う箇所からちょうど \(K\) 箇所を選んで、標高差の絶対値の合計を最大化する問題です。

結論として、標高をソートし、「低い標高」と「高い標高」を交互に並べる形を考えることで最大値を求められます。

考察

まず、選んだ吊り橋だけに注目します。

標高 \(x < y\) の 2 点を結ぶ吊り橋のスリル値は

\(y - x\)

です。つまり、この吊り橋は

• 高い方に \(+1\)
• 低い方に \(-1\)

の係数を与える、と考えられます。

また、1 つの展望スポットは、並びの中で左右高々 2 箇所の吊り橋にしか接しません。
したがって、ある標高が \(+1\) や \(-1\) として数えられる回数は高々 2 回です。

最大化するには、

• \(+\) の係数はできるだけ大きい標高に付けたい
• \(-\) の係数はできるだけ小さい標高に付けたい

です。

そのため、使うべき標高はソート後の「小さい側」と「大きい側」に集中します。

また、吊り橋を複数の離れたパスに分けると、端点が増えます。
端点は係数の絶対値が \(1\) にしかなりませんが、内部の点は係数の絶対値を \(2\) にできます。

したがって、最大値は \(K\) 本の吊り橋を 1 本のパスとして使い、標高を

低い・高い・低い・高い・…

のように交互に並べることで達成できます。

残りの使わない展望スポットは、この列の外側に置けばよいです。

---

ソート後の配列を 0-indexed で

\(A_0 \leq A_1 \leq \cdots \leq A_{N-1}\)

とします。

また、

• \(S(t)\): 小さい方から \(t\) 個の和
• \(L(t)\): 大きい方から \(t\) 個の和

とします。

\(K\) が奇数の場合

\(K = 2m - 1\) とします。

このとき、使う頂点数は \(K+1 = 2m\) 個です。

交互に並べると、

• 高い側を \(m\) 個使う
• 低い側を \(m\) 個使う

ことになります。

内部の点は係数が \(\pm 2\)、端点は係数が \(\pm 1\) です。

高い側では、最も小さいものを端点にして \(+1\)、残りを \(+2\) にします。
低い側では、最も大きいものを端点にして \(-1\)、残りを \(-2\) にします。

よって答えは

\(2(L(m) - S(m)) - (A_{N-m} - A_{m-1})\)

です。

例えば、\(K=3\)、標高が \(1,2,99,100\) の場合、

\(2((99+100)-(1+2)) - (99-2) = 295\)

となり、実際に

\(2,100,1,99\)

と並べると

\(|2-100| + |100-1| + |1-99| = 98+99+98=295\)

です。

\(K\) が偶数の場合

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

このとき、使う頂点数は \(K+1 = 2m+1\) 個です。

交互に並べると、端点は両方とも

• 高い側になる
• 低い側になる

のどちらかです。

端点が高い側の場合

高い側を \(m+1\) 個、低い側を \(m\) 個使います。

• 低い側 \(m\) 個はすべて内部なので係数 \(-2\)
• 高い側 \(m+1\) 個のうち、端点 2 個は係数 \(+1\)
• 残り \(m-1\) 個は係数 \(+2\)

よって候補値は

\(-2S(m) + A_{N-m-1} + A_{N-m} + 2L(m-1)\)

です。

端点が低い側の場合

低い側を \(m+1\) 個、高い側を \(m\) 個使います。

• 高い側 \(m\) 個はすべて内部なので係数 \(+2\)
• 低い側 \(m+1\) 個のうち、端点 2 個は係数 \(-1\)
• 残り \(m-1\) 個は係数 \(-2\)

よって候補値は

\(2L(m) - \left(2S(m-1) + A_{m-1} + A_m\right)\)

です。

この 2 つのうち大きい方が答えです。

アルゴリズム

1. 標高配列 \(A\) を昇順にソートする。
2. 累積和 pref を作る。
3. 以下を定義する。
   • sum_small(t) = 小さい方から \(t\) 個の和
   • sum_large(t) = 大きい方から \(t\) 個の和
4. \(K\) の偶奇で場合分けする。
   • \(K\) が奇数なら、上の奇数用の式で答えを計算する。
   • \(K\) が偶数なら、端点が高い場合・低い場合の 2 通りを計算し、大きい方を答えにする。

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートが支配的です。
• 空間計算量: \(O(N)\)
  • 配列と累積和を持ちます。

実装のポイント

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

• 偶数の場合、\(m=1\) のとき sum_small(m-1) や L(m-1) は 0 個の和になります。累積和を使うと自然に処理できます。

• 添字は 0-indexed で考えると、コード中の式と対応しやすいです。

  ソースコード

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

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

    int N, K;
    cin >> N >> K;

    vector<long long> A(N);
    for (auto &x : A) cin >> x;

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

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

    auto sum_small = [&](int t) -> long long {
        return pref[t];
    };

    auto sum_large = [&](int t) -> long long {
        return pref[N] - pref[N - t];
    };

    long long ans;

    if (K % 2 == 1) {
        int m = (K + 1) / 2;
        ans = 2 * (sum_large(m) - sum_small(m)) - (A[N - m] - A[m - 1]);
    } else {
        int m = K / 2;

        long long ans1 = -2 * sum_small(m)
                       + A[N - m - 1] + A[N - m]
                       + 2 * (pref[N] - pref[N - m + 1]);

        long long ans2 = 2 * sum_large(m)
                       - (2 * sum_small(m - 1) + A[m - 1] + A[m]);

        ans = max(ans1, ans2);
    }

    cout << ans << '\n';
    return 0;
}

---

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