概要

木を左から順に見ていき、「\(K\) 本収穫して 1 本休む」を繰り返すとき、収穫される木にあるリンゴ数 \(D_i\) の総和を求める問題です。

考察

重要なのは、どの木を収穫するかは完全に位置（番号）で決まっているという点です。
具体的には、木を \(K+1\) 本ごとの周期で見たとき、

• 周期の先頭から \(K\) 本は収穫する
• 周期の最後の 1 本は収穫しない（休む）

となります。

たとえば \(K=3\) なら周期は \(4\) で、
「収穫・収穫・収穫・スキップ・収穫・収穫・収穫・スキップ…」です。

したがって各 \(i\) について、 - \(i \bmod (K+1)\) が \(1,2,\ldots,K\) なら足す - \(i \bmod (K+1)\) が \(0\)（周期の最後）なら足さない

とすればよいです。

素朴に「収穫する区間を作って合計を計算する」などと考えても結局 \(D_i\) を全て読む必要があり、最終的にやることはこの判定を \(N\) 回するだけです。
制約が \(N \le 10^6\) なので、\(O(N)\) で一回なめる方針が最適です。また入力が大きいので、標準入力を高速に読む工夫が必要になります。

アルゴリズム

1. 周期長を \(cycle = K+1\) とする。
2. 周期内の位置 pos を \(1\) から数える（1～\(K\) は収穫、\(K+1\) はスキップ）。
3. \(i=1\) から \(N\) まで順に \(D_i\) を読み、
   • pos <= K なら答えに加算する
   • pos を 1 進め、pos == cycle + 1 になったら pos = 1 に戻す（周期の繰り返し）
4. 最後に合計を出力する。

これで、問題のルール通りに「\(K\) 本収穫 → 1 本休む」を正確にシミュレーションできます。
（\(N\) が周期の途中で終わる場合も、そのまま途中で打ち切られる形になり自然に対応できます。）

計算量

• 時間計算量: \(O(N)\)（各木を 1 回ずつ処理）
• 空間計算量: \(O(1)\)（入力配列を持たず、読みながら加算）

実装のポイント

• \(N\) が最大 \(10^6\)、\(D_i\) が最大 \(10^9\) なので、合計は最大で \(10^{15}\) 程度になり得ます。Python の int ならそのまま安全に扱えます。

• 入力が大きいため、sys.stdin.buffer.read() でまとめて読み取り、自前で整数をパースすることで高速化しています（input() を \(10^6\) 回呼ぶと遅くなりやすい）。

• 周期判定は i % (K+1) でもできますが、コードでは pos を進めて周期的に戻すことで剰余計算を避け、シンプルにしています。

  ソースコード

import sys

data = sys.stdin.buffer.read()
n_data = len(data)
p = 0

def read_int():
    global p
    while p < n_data and data[p] <= 32:
        p += 1
    x = 0
    while p < n_data and data[p] > 32:
        x = x * 10 + (data[p] - 48)
        p += 1
    return x

N = read_int()
K = read_int()

cycle = K + 1
pos = 1
ans = 0

for _ in range(N):
    d = read_int()
    if pos <= K:
        ans += d
    pos += 1
    if pos == cycle + 1:
        pos = 1

sys.stdout.write(str(ans))

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