概要

一列に並んだ \(N\) 本のリンゴの木から、高橋君がある規則に従ってリンゴを収穫したときの合計個数を求めます。

考察

高橋君は、連続する \(K\) 本の木からリンゴを全部収穫し、次の1本は休憩のために通り過ぎるという動作を繰り返します。
つまり、\(K\) 本収穫 → 1本スキップ → \(K\) 本収穫 → 1本スキップ … というように進んでいきます。

例えば、\(N = 8, K = 2\) の場合： - 木 1, 2 を収穫（合計 2本） - 木 3 をスキップ - 木 4, 5 を収穫 - 木 6 をスキップ - 木 7, 8 を収穫

このように、「\(K\) 個取って、1個飛ばす」というパターンが繰り返されます。

素朴な方法として、「各ステップで \(K\) 個足して、次をスキップ」という処理をシミュレーションしても解けますが、制約が \(N \leq 10^6\) なので、間に合います。
しかし、もし \(K\) が非常に大きい場合や、もっと複雑な条件があると、全探索だと時間がかかる可能性があります。

しかし今回の問題では、単純にシミュレーションすることで効率的に解くことができます。

アルゴリズム

1. 変数 i を使って現在位置を管理します（最初は 0）。
2. i が \(N\) 未満の間、以下を繰り返します：
   • 現在位置 i から min(i + K, N) までの木からリンゴをすべて合計に加える。
   • 次に、K + 1 だけ i を進めることで、\(K\) 個分の収穫と1個のスキップを同時に処理します。
3. 合計値を出力します。

このようにして、高橋君が実際に収穫する木を順に特定し、そのリンゴの数を足していけばよいです。

計算量

• 時間計算量: \(O(N)\)
  各木は最大でも1回しか訪れないため、線形時間で処理できます。
• 空間計算量: \(O(N)\)
  入力配列 \(D\) を保持するのに \(O(N)\) 必要です。

実装のポイント

• for j in range(i, min(i + K, N)) のように、範囲外アクセスを防ぐために min を使うのが重要です。

• 最後の区間で木が足りなくても問題ないように、ループの終了条件に注意しましょう。

• i += K + 1 で、収穫＋スキップを一度に進めている点がポイントです。

  ソースコード

N, K = map(int, input().split())
D = list(map(int, input().split()))

total = 0
i = 0

while i < N:
    # 収穫する木: i から i+K-1 まで
    for j in range(i, min(i + K, N)):
        total += D[j]
    # 次のK+1個分をスキップ (K個収穫 + 1個休憩)
    i += K + 1

print(total)

この解説は qwen3-coder-480b によって生成されました。