概要

高橋君がお店 \(S\) から出発してちょうど \(K\) 回移動するときに、訪問したお店にある宝石の合計個数の最大値を求める問題です。 訪問するお店の集合は常に \(S\) を含む連続する区間 \([L, R]\) になるため、累積和と数式による範囲の絞り込みを用いて \(O(N)\) で解くことができます。

考察

1. 訪問するお店の性質

高橋君はワープができないため、ちょうど \(K\) 回の移動で訪問するお店の集合は、初期位置 \(S\) を含む連続する区間 \([L, R]\)（\(L \le S \le R\)）になります。 また、宝石の個数 \(A_i\) はすべて非負（\(0\) 以上）であるため、同じ移動回数であれば、訪問する区間 \([L, R]\) は広ければ広いほど（\(L\) が小さく、 \(R\) が大きいほど）獲得できる宝石の合計は多くなります。

2. 「ちょうど \(K\) 回」という制約の言い換え

一見すると「ちょうど \(K\) 回」という偶奇（パリティ）の制約が難しそうに見えます。しかし、お店の数 \(N \ge 2\) かつ \(K \ge 1\) より、訪問する区間の長さは必ず 2 以上（\(L < R\)）になります。 このとき、区間 \([L, R]\) のすべてのお店を訪問する最小移動回数を \(D(L, R)\) とすると、\(D(L, R) \le K\) であれば、ちょうど \(K\) 回の移動で訪問区間を \([L, R]\) にぴったり収めることができます。

なぜなら： - \(K - D(L, R)\) が偶数の場合：区間の端点（例えば \(R\)）とその隣（\(R-1\)）を往復することで、訪問区間を広げずに移動回数を 2 ずつ消費できます。 - \(K - D(L, R)\) が奇数の場合：最後に端点に到達する手前で 1 歩戻る、あるいは到達後に 1 歩戻ることで、訪問区間を広げずに移動回数を 1 消費し、残りの偶数回は往復で消費できます（区間の長さが 2 以上あるため、必ず内側に戻るスペースがあります）。

したがって、問題は「\(D(L, R) \le K\) を満たす区間 \([L, R]\) における宝石の総和の最大値を求める」という問題に単純化されます。

3. 最小移動回数 \(D(L, R)\) の計算

\(S\) から出発して \([L, R]\) をすべて訪れるための最短ルートは、以下の 2 パターンのどちらかです。 - パターン1（先に左端 \(L\) に行き、折り返して右端 \(R\) に行く） 移動回数：\((S - L) + (R - L) = 2(S - L) + (R - S)\) - パターン2（先に右端 \(R\) に行き、折り返して左端 \(L\) に行く） 移動回数：\((R - S) + (R - L) = (S - L) + 2(R - S)\)

よって、最小移動回数は \(D(L, R) = (R - L) + \min(S - L, R - S)\) となります。

4. 高速化のアイデア（全探索から \(O(N)\) へ）

すべての \([L, R]\) の組み合わせを全探索すると \(O(N^2)\) かかり、 \(N \le 2 \times 10^5\) では実行時間制限に間に合いません（TLE）。 そこで、上記の 2 つのパターン（どちらが最短になるか）で場合分けを行い、片方の端点を固定したときにもう片方の端点がどこまで届くかを数式で直接求めます。

アルゴリズム

区間内の宝石の総和を高速に計算するために、あらかじめ \(A\) の累積和 \(P\) を用意しておきます（\(P[i] = A_1 + \dots + A_i\) とすると、区間 \([L, R]\) の総和は \(P[R] - P[L-1]\) で \(O(1)\) で求まります）。

ケース1：先に左、次に右に行くのが最適な場合（\(S - L \le R - S\)）

このとき、最小移動回数は \(D(L, R) = 2(S - L) + (R - S) = S - 2L + R\) です。 条件 \(D(L, R) \le K\) より、 $\(S - 2L + R \le K \iff 2L \ge S + R - K \iff L \ge \frac{S + R - K}{2}\)\( \)L\( は整数なので、切り上げて \)L \ge \lceil (S + R - K) / 2 \rceil = (S + R - K + 1) // 2$ となります。

右端 \(R\) を固定したとき、左端 \(L\) が満たすべき条件は以下のすべてです： 1. \(L \ge 1\) （お店の範囲内） 2. \(L \ge 2S - R\) （ケース1の前提条件 \(S - L \le R - S\) より） 3. \(L \ge (S + R - K + 1) // 2\) （移動回数の制限より）

宝石の個数は非負なので、左端 \(L\) は小さければ小さいほど（左に広げるほど）得られる宝石が多くなります。 したがって、各 \(R\) （\(S + 1 \le R \le \min(N, S + K)\)）に対して、条件を満たす最小の \(L\) は以下のように一意に決定できます。 $\(L = \max(1, 2S - R, (S + R - K + 1) // 2)\)\( このときの区間 \)[L, R]$ の宝石の総和を計算し、最大値を更新します。

ケース2：先に右、次に左に行くのが最適な場合（\(S - L > R - S\)）

このとき、最小移動回数は \(D(L, R) = (S - L) + 2(R - S) = 2R - S - L\) です。 条件 \(D(L, R) \le K\) より、 $\(2R - S - L \le K \iff 2R \le S + L + K \iff R \le \frac{S + L + K}{2}\)\( 切り下げて \)R \le (S + L + K) // 2$ となります。

左端 \(L\) を固定したとき、右端 \(R\) が満たすべき条件は以下のすべてです： 1. \(R \le N\) （お店の範囲内） 2. \(R \le 2S - L - 1\) （ケース2の前提条件 \(S - L > R - S\) より） 3. \(R \le (S + L + K) // 2\) （移動回数の制限より）

右端 \(R\) は大きければ大きいほど（右に広げるほど）得られる宝石が多くなります。 したがって、各 \(L\) （\(\max(1, S - K) \le L \le S - 1\)）に対して、条件を満たす最大の \(R\) は以下のように一意に決定できます。 $\(R = \min(N, 2S - L - 1, (S + L + K) // 2)\)\( このときの区間 \)[L, R]$ の宝石の総和を計算し、最大値を更新します。

最後に、ケース1とケース2で得られた最大値を出力します。

計算量

• 時間計算量: \(O(N)\) 累積和の構築に \(O(N)\)、ケース1のループ（\(R\) の探索）に最大 \(O(N)\)、ケース2のループ（\(L\) の探索）に最大 \(O(N)\) かかります。ループ内部の処理はすべて \(O(1)\) なので、全体で \(O(N)\) となり、実行時間制限に余裕で間に合います。
• 空間計算量: \(O(N)\) 長さ \(N+1\) の累積和配列 \(P\) を保持するため、 \(O(N)\) のメモリを使用します。

実装のポイント

• 1-based index への対応: 問題文は 1-indexed（お店 1 から \(N\)）で書かれています。Pythonコードでは累積和配列 P を N + 1 のサイズで確保し、1-indexed のまま計算できるようにすることで、インデックスのズレによるバグを防いでいます。

• 整数除算の切り上げ: ケース1の \(L\) の計算における切り上げ \(\lceil (S + R - K) / 2 \rceil\) は、Pythonの整数除算を用いて (S + R - K + 1) // 2 とスマートに表現されています。

  ソースコード

import sys


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

    P = [0] * (N + 1)
    for i in range(N):
        P[i + 1] = P[i] + A[i]

    ans = 0

    # ケース1: S - L <= R - S
    R_start = S + 1
    R_end = min(N, S + K)
    for R in range(R_start, R_end + 1):
        L = max(1, 2 * S - R, (R + S - K + 1) // 2)
        if L <= S:
            val = P[R] - P[L - 1]
            if val > ans:
                ans = val

    # ケース2: S - L > R - S
    L_start = max(1, S - K)
    L_end = S - 1
    for L in range(L_start, L_end + 1):
        R = min(N, 2 * S - L - 1, (L + S + K) // 2)
        if R >= S:
            val = P[R] - P[L - 1]
            if val > ans:
                ans = val

    print(ans)


if __name__ == "__main__":
    solve()

---

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