概要

一列に並んだ木を左から順に「\(K\) 本収穫 → \(1\) 本スキップ」のパターンを繰り返し、収穫したリンゴの合計を求める問題です。

考察

この問題のポイントは、高橋君の行動パターンが完全に決まっているということです。高橋君は選択の自由がなく、木 \(1\) から始めて以下を機械的に繰り返します：

1. 連続する \(K\) 本の木から収穫する
2. \(1\) 本の木をスキップする

つまり、\((K+1)\) 本ごとに \(1\) サイクルが構成され、各サイクルの最後の \(1\) 本だけがスキップされます。

具体例で確認してみましょう：

• \(N = 7, K = 3\) のとき：サイクル長は \(K+1 = 4\)

  • サイクル1：木 \(1, 2, 3\)（収穫）→ 木 \(4\)（スキップ）
  • サイクル2：木 \(5, 6, 7\)（収穫）→ 木 \(8\) は存在しないので終了
  • 収穫する木：\(1, 2, 3, 5, 6, 7\)

• \(N = 8, K = 2\) のとき：サイクル長は \(K+1 = 3\)

  • サイクル1：木 \(1, 2\)（収穫）→ 木 \(3\)（スキップ）
  • サイクル2：木 \(4, 5\)（収穫）→ 木 \(6\)（スキップ）
  • サイクル3：木 \(7, 8\)（収穫）→ 木 \(9\) は存在しないので終了
  • 収穫する木：\(1, 2, 4, 5, 7, 8\)

このように各木を収穫するかスキップするかは一意に決まるので、シミュレーションするだけで解けます。

素朴なアプローチ自体が十分高速で、各木を高々 \(1\) 回ずつ見るだけなので \(O(N)\) で動作します。特別なアルゴリズムは不要です。

アルゴリズム

インデックス \(i\) を \(0\) から始めて、以下を繰り返します：

1. 収穫フェーズ：\(K\) 回繰り返し、\(D[i]\) を合計に加算して \(i\) を \(1\) 増やす。\(i \geq N\) になったら終了。
2. スキップフェーズ：\(i\) を \(1\) 増やす（\(1\) 本スキップ）。

\(i \geq N\) になるまでこれを繰り返し、最後に合計を出力します。

i = 0, total = 0
while i < N:
    K本分だけ D[i] を total に加算し、i を進める（i < N の間）
    i を 1 増やす（スキップ）

計算量

• 時間計算量: \(O(N)\)（各木を高々 \(1\) 回だけ処理するため）
• 空間計算量: \(O(N)\)（リンゴの個数を格納する配列のため）

実装のポイント

• 収穫フェーズの内側で \(i < N\) のチェック を忘れないこと。\(K\) 本収穫する途中で木 \(N\) に到達する場合があります（パターンの途中で終了するケース）。

• スキップフェーズでは境界チェックは不要です。\(i\) が \(N\) 以上になっても、次の while i < N の条件でループが終了するためです。

• \(D_i\) が最大 \(10^9\)、\(N\) が最大 \(10^6\) なので、合計値は最大 \(10^{15}\) 程度になります。Python では整数のオーバーフローがないため問題ありませんが、C++ などでは long long を使う必要があります。

  ソースコード

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

total = 0
i = 0
while i < N:
    # Harvest K trees
    for j in range(K):
        if i < N:
            total += D[i]
            i += 1
        else:
            break
    # Skip 1 tree
    i += 1

print(total)

---

この解説は claude4.6opus-thinking によって生成されました。