概要

\(N\) 個の区間の走行時間の合計に、特定のルールで発生する「休憩時間」を加算して、全行程にかかる合計時間を求める問題です。

考察

この問題で求めるべき合計時間は、以下の2つの要素の和です。 1. 走行時間の合計: 全ての区間の走行時間 \(A_1 + A_2 + \cdots + A_N\) 2. 休憩時間の合計: ルールに従って発生する休憩（1回につき1時間）の総数

休憩回数の数え方

休憩は「番号が \(K\) の倍数である区間を走り終えた直後」に発生しますが、「まだ走行すべき区間が残っている場合」という条件があります。 つまり、第 \(K\) 区間、第 \(2K\) 区間、… と休憩を取っていきますが、最後の第 \(N\) 区間を走り終えた後は休憩しません。

具体例で考えてみましょう。 - \(N=5, K=2\) のとき： 第 2 区間、第 4 区間の後に休憩します。第 6 区間は存在しないため、休憩は合計 2回 です。 - \(N=6, K=2\) のとき： 第 2 区間、第 4 区間の後に休憩します。第 6 区間は最後なので休憩しません。休憩は合計 2回 です。

このように、休憩が発生するタイミングは \(K, 2K, 3K, \dots\) のうち \(N\) 未満のものとなります。 これを数式で表すと、休憩回数は \((N-1)\) を \(K\) で割ったときの商（切り捨て）、すなわち \(\lfloor (N-1) / K \rfloor\) と一致します。

アルゴリズム

1. 入力から \(N, K\) および各区間の走行時間 \(A_i\) を読み込みます。
2. 走行時間の合計 \(S = \sum_{i=1}^{N} A_i\) を計算します。
3. 休憩回数 \(R = \lfloor (N-1) / K \rfloor\) を計算します。
4. \(S + R\) を答えとして出力します。

計算量

• 時間計算量: \(O(N)\)
  • 走行時間の合計を求めるために \(N\) 個の要素を走査する必要があるためです。休憩回数の計算は \(O(1)\) で行えます。
• 空間計算量: \(O(N)\)
  • 入力された \(A_i\) をリスト等に保持する場合、その要素数に比例したメモリが必要です。

実装のポイント

• 大きな数値への対応: \(A_i\) は最大 \(10^9\)、 \(N\) は最大 \(2 \times 10^5\) であるため、合計時間は最大で約 \(2 \times 10^{14}\) 程度になります。Pythonでは整数の大きさに制限がありませんが、他の言語（C++やJavaなど）を使用する場合は、64ビット整数型（long long や long）を使用する必要があります。

• 休憩回数の計算: n // k とすると、 \(N\) が \(K\) の倍数のときに最後の区間後もカウントしてしまいます。必ず (n - 1) // k とすることで、最後の区間を除外した正しい回数を求めることができます。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを取得し、空白で分割してリスト化します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 区間の数, K: 休憩を挟む間隔
    n = int(input_data[0])
    k = int(input_data[1])
    
    # 各区間の走行時間の合計を計算します
    # map関数を使用して文字列のリストを整数のイテレータに変換し、sumで合計します
    total_travel_time = sum(map(int, input_data[2:2+n]))
    
    # 休憩の回数を計算します
    # 番号がKの倍数である区間のうち、最後の区間（第N区間）を除いたものの個数です
    # これは (n - 1) // k で求めることができます
    num_rests = (n - 1) // k
    
    # 合計時間（走行時間 + 休憩時間）を出力します
    # 休憩1回につき1時間なので、休憩時間は num_rests と等しくなります
    print(total_travel_time + num_rests)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。