概要

各区間の走行時間の合計に、「何回休憩するか」を足せばよい問題です。
休憩回数は直接数えることができ、答えは \( \sum A_i + \left\lfloor \dfrac{N-1}{K} \right\rfloor \) になります。

考察

まず、走行時間の合計は単純に

\[ A_1 + A_2 + \cdots + A_N \]

です。

あとは休憩時間の合計を求めればよいです。
休憩は

• 第 \(K\) 区間の後
• 第 \(2K\) 区間の後
• 第 \(3K\) 区間の後
• …

に入りますが、最後の区間を走り終えた後には休憩しません。
つまり、「\(K\) の倍数の区間のうち、\(N\) 未満のものの個数」が休憩回数です。

休憩回数は何回か

休憩が入るのは

\[ K, 2K, 3K, \ldots \]

のうち、\(N\) 未満のものです。
これは「\(1\) 以上 \(N-1\) 以下にある \(K\) の倍数の個数」と同じなので、

\[ \left\lfloor \frac{N-1}{K} \right\rfloor \]

回です。

具体例

例えば \(N=10,\ K=3\) なら、休憩は

• 3区間目の後
• 6区間目の後
• 9区間目の後

の 3 回です。実際に

\[ \left\lfloor \frac{10-1}{3} \right\rfloor = \left\lfloor \frac{9}{3} \right\rfloor = 3 \]

となります。

間違えやすい点

\(N // K\) としてしまうと誤りになることがあります。
例えば \(N=6,\ K=3\) のとき、\(3\) 区間目の後には休憩しますが、\(6\) 区間目の後はもう走行が終わっているので休憩しません。

• 正しい休憩回数：\(1\)
• \(N // K = 6 // 3 = 2\) は誤り

このため、\((N-1)//K\) を使うのがポイントです。

素朴な方法について

各区間を順に見て、

• 走行時間を足す
• 区間番号が \(K\) の倍数かつ最後でなければ \(1\) を足す

とシミュレーションしても \(O(N)\) で十分間に合います。
ただし、この問題は休憩回数を式で直接求められるため、よりシンプルに書けます。

アルゴリズム

1. 配列 \(A\) の総和 \(S = \sum A_i\) を求める
2. 休憩回数 \(R = (N-1)//K\) を求める
3. \(S + R\) を出力する

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 休憩回数は \(N // K\) ではなく \((N-1) // K\) です。

• 他言語で実装する場合、\(\sum A_i\) は大きくなるので 64-bit 整数型 (long long など) を使いましょう。

• このコードでは入力全体を配列として受け取っているため空間計算量は \(O(N)\) です。

  ソースコード

import sys

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

total = sum(A) + (N - 1) // K
print(total)

---

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