概要

各区間の走行時間の合計に、「休憩が何回入るか」を足すだけで答えが出る問題です。
休憩回数はシミュレーション不要で、\(N\) と \(K\) から直接計算できます。

考察

まず、走行時間の合計は明らかに \(\sum_{i=1}^{N} A_i\) です。

次に休憩について考えます。
休憩は「\(K\) の倍数番目の区間を走り終えた直後」に入りますが、まだ区間が残っているときだけです。
つまり休憩が入る区間番号は

• \(K, 2K, 3K, \dots\)
• ただし \(N\) は含まない（\(N\) 区間目の後はもう終わりなので休憩しない）

となります。

これは「\(1\) 以上 \(N-1\) 以下の \(K\) の倍数の個数」と同じなので、休憩回数は \(\left\lfloor \dfrac{N-1}{K} \right\rfloor\) です。

---

具体例

例えば \(N=10,\ K=3\) のとき、休憩候補は区間 \(3,6,9\) の後で、いずれもまだ先があるので 3 回。
式でも \(\left\lfloor \dfrac{10-1}{3} \right\rfloor = \left\lfloor 3 \right\rfloor = 3\) で一致します。

例えば \(N=6,\ K=3\) のとき、区間 \(3\) の後は休憩、区間 \(6\) の後は終了なので休憩なし。
式でも \(\left\lfloor \dfrac{6-1}{3} \right\rfloor = 1\) で正しいです。

---

素朴に「各区間を順に見て、\(i \% K==0\) なら休憩を加算」としても \(O(N)\) で十分間に合います。
ただしこの問題はさらに単純化でき、休憩回数を式で一発計算できるのがポイントです。

アルゴリズム

1. 入力で \(N, K\) と配列 \(A\) を受け取る。
2. total = sum(A) で全走行時間を計算。
3. 休憩回数 breaks = (N - 1) // K を計算。
4. total += breaks して出力。

これで合計時間（走行＋休憩）が求まります。

計算量

• 時間計算量: \(O(N)\)（sum(A) のみ）
• 空間計算量: \(O(N)\)（入力配列 \(A\) を保持）

実装のポイント

• 休憩回数は N // K ではなく (N - 1) // K。
  最後の区間後には休憩しないためです。

• 合計値は大きくなる可能性がありますが、Python の int ならオーバーフローの心配はありません。

• 提示コードのように sys.stdin.buffer.read() でまとめて読む実装は高速で、競技向きです。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, K = data[0], data[1]
    A = data[2:2 + N]

    total = sum(A)
    total += (N - 1) // K  # 休憩回数

    print(total)

if __name__ == "__main__":
    main()

---

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