概要

この問題は、一列に並んだお店の中で、初期位置 \(S\) からちょうど \(K\) 回移動したときに獲得できる宝石の最大値を求める問題です。 高橋君が訪れるお店の範囲は必ず \(S\) を含む連続する区間になるため、移動経路の性質を利用して「訪れる区間」を全探索することで、効率よく最適解を求めることができます。

考察

1. 訪れるお店の範囲は「連続する区間」になる

高橋君は隣接するお店にしか移動できないため、最終的に訪れたお店の集合は、初期位置 \(S\) を含む連続する区間 \([S-x, S+y]\) （ただし \(x, y \ge 0\)）になります。 同じお店の宝石は最初の 1 回しか回収できないため、宝石の合計を最大化するためには、移動回数 \(K\) の範囲内でできるだけ広い区間 \([S-x, S+y]\) をカバーすることが目標になります。

2. 区間 \([S-x, S+y]\) を訪れるための最小移動回数

\(S\) から出発して、左に \(x\) 個、右に \(y\) 個進んだ区間 \([S-x, S+y]\) のすべてのお店を訪れるための最短経路は、以下の 2 通りのどちらかになります。

• パターン A（左に最初に行ってから、右に引き返す） まず左に \(x\) 個進んで \(S-x\) に到達し、そこから右に引き返して \(S+y\) まで進みます。 このときの移動回数は \(x + (x + y) = 2x + y\) 回です。

• パターン B（右に最初に行ってから、左に引き返す） まず右に \(y\) 個進んで \(S+y\) に到達し、そこから左に引き返して \(S-x\) まで進みます。 このときの移動回数は \(y + (y + x) = 2y + x\) 回です。

したがって、区間 \([S-x, S+y]\) をすべて訪れるために必要な最小の移動回数は \(\min(2x + y, 2y + x)\) となります。これが \(K\) 以下であれば、ちょうど \(K\) 回の移動でこの区間を訪れることができます（余った移動回数は、隣り合うお店を往復することで消費できます）。

※ただし、制約より \(K \ge 1\) なので、初期位置から必ず 1 歩以上は動く必要があります。よって \(x + y \ge 1\) を満たす必要があります。

3. 全探索による解法

お店の数 \(N\) は最大で \(2 \times 10^5\) なので、すべての区間を素直に 2 重ループで探索すると \(O(N^2)\) となり、実行時間制限に間に合いません（TLE）。 しかし、片方の移動距離（例えば \(x\)）を固定すると、もう片方の移動距離 \(y\) は、移動回数 \(K\) を使い切るように貪欲に（できるだけ大きく）決定するのが最適になります。

これにより、探索範囲を \(O(N)\) に抑えることができます。

• ケース 1: パターン A (\(2x + y \le K\)) の探索 左への移動距離 \(x\) を \(0\) から可能な範囲（\(\min(S-1, \lfloor K/2 \rfloor)\)）で全探索します。 このとき、右への移動距離 \(y\) は最大で \(K - 2x\) まで伸ばせるため、\(y = \min(N-S, K-2x)\) と決定します。

• ケース 2: パターン B (\(2y + x \le K\)) の探索 右への移動距離 \(y\) を \(0\) から可能な範囲（\(\min(N-S, \lfloor K/2 \rfloor)\)）で全探索します。 このとき、左への移動距離 \(x\) は最大で \(K - 2y\) まで伸ばせるため、\(x = \min(S-1, K-2y)\) と決定します。

区間 \([S-x, S+y]\) の宝石の総和は、あらかじめ累積和を計算しておくことで、各クエリ \(O(1)\) で高速に求めることができます。

アルゴリズム

1. 累積和の構築 配列 \(A\) の累積和配列 \(P\) を作成します。これにより、区間 \([L, R]\) の宝石の総和を \(P[R] - P[L-1]\) として \(O(1)\) で計算できるようになります。

2. ケース 1 の全探索 \(x\) を \(0\) から \(\min(S-1, \lfloor K/2 \rfloor)\) までループさせます。 各 \(x\) に対して \(y = \min(N-S, K-2x)\) とし、\(x+y \ge 1\) を満たす場合に区間 \([S-x, S+y]\) の総和を計算し、最大値を更新します。

3. ケース 2 の全探索 \(y\) を \(0\) から \(\min(N-S, \lfloor K/2 \rfloor)\) までループさせます。 各 \(y\) に対して \(x = \min(S-1, K-2y)\) とし、\(x+y \ge 1\) を満たす場合に区間 \([S-x, S+y]\) の総和を計算し、最大値を更新します。

4. 答えの出力 更新された最大値を出力します。

計算量

• 時間計算量: \(O(N)\) 累積和の構築に \(O(N)\)、ケース 1 とケース 2 のループがそれぞれ高々 \(N\) 回まわるため、全体の時間計算量は \(O(N)\) となり、実行時間制限に十分間に合います。

• 空間計算量: \(O(N)\) 入力配列 \(A\) と累積和配列 \(P\) を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 型に注意: 宝石の個数 \(A_i\) は最大で \(10^9\) であり、その総和は \(2 \times 10^{14}\) に達するため、累積和や答えを格納する変数には C++ の long long 型を使用する必要があります。また、移動回数 \(K\) も最大で \(10^9\) であるため、同様に long long 型で扱います。

• コーナーケース: \(K \ge 1\) のため、全く動かない（\(x = y = 0\)）という選択肢は取れません。コード内の if (x + y >= 1) という条件分岐によって、必ず 1 歩以上動くケースのみを正しく考慮しています。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, S;
    long long K;
    if (!(cin >> N >> S >> K)) return 0;

    vector<long long> A(N + 1);
    vector<long long> P(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        P[i] = P[i - 1] + A[i];
    }

    auto get_sum = [&](int L, int R) {
        if (L > R) return 0LL;
        return P[R] - P[L - 1];
    };

    long long ans = 0;

    // ケース 1: 2x + y <= K
    // 左に x 個、右に y 個進む（左に行ってから右に行く）
    long long limit_x = min((long long)S - 1, K / 2);
    for (long long x = 0; x <= limit_x; ++x) {
        long long y = min((long long)N - S, K - 2 * x);
        if (y < 0) continue;
        if (x + y >= 1) {
            ans = max(ans, get_sum(S - x, S + y));
        }
    }

    // ケース 2: 2y + x <= K
    // 右に y 個、左に x 個進む（右に行ってから左に行く）
    long long limit_y = min((long long)N - S, K / 2);
    for (long long y = 0; y <= limit_y; ++y) {
        long long x = min((long long)S - 1, K - 2 * y);
        if (x < 0) continue;
        if (x + y >= 1) {
            ans = max(ans, get_sum(S - x, S + y));
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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