概要

\(N\) 区間の走行時間の合計に、\(K\) 区間ごとに取る休憩の回数を加えることで、ドライブ全体の所要時間を求める問題です。

考察

まず、合計時間は「走行時間の総和」＋「休憩時間の総和」に分解できます。

走行時間の総和は単純に \(A_1 + A_2 + \cdots + A_N\) です。

休憩の回数を正しく数えることがポイントです。休憩が発生する条件を整理しましょう：

• 区間番号が \(K\) の倍数（\(K, 2K, 3K, \ldots\)）を走り終えた直後
• かつ、まだ走行すべき区間が残っている場合

つまり、区間 \(N\)（最後の区間）を走り終えた直後には休憩を取りません。

具体例で確認します：

• 例1: \(N = 5, K = 2\) の場合、\(K\) の倍数は \(2, 4\) です。区間2の後は残りがあるので休憩、区間4の後も残りがあるので休憩。休憩回数は 2回。
• 例2: \(N = 4, K = 2\) の場合、\(K\) の倍数は \(2, 4\) です。区間2の後は残りがあるので休憩、区間4は最後の区間なので休憩なし。休憩回数は 1回。
• 例3: \(N = 3, K = 5\) の場合、\(K\) の倍数で \(N\) 以下のものはないので、休憩回数は 0回。

一般に、\(N\) 以下の \(K\) の倍数のうち、\(N\) 自身を除いたものの個数が休憩回数です。

\(N\) 以下の \(K\) の倍数の個数は \(\lfloor N / K \rfloor\) 個です。ここから、\(N\) 自体が \(K\) の倍数であれば最後の区間での休憩は取らないので1引く…と場合分けしたくなりますが、「\(N\) 未満の \(K\) の倍数の個数」と考えれば \(\lfloor (N-1) / K \rfloor\) で統一的に計算できます。ただし \(K > N-1\)（つまり休憩が1回も発生しない）の場合は \(0\) です。

アルゴリズム

1. 走行時間の総和 \(\text{total} = \sum_{i=1}^{N} A_i\) を計算する。
2. 休憩回数 \(\text{breaks}\) を求める。
   • \(K \leq N - 1\) の場合：\(\text{breaks} = \lfloor (N-1) / K \rfloor\)
   • それ以外（\(K \geq N\)）の場合：\(\text{breaks} = 0\)
3. 答えは \(\text{total} + \text{breaks}\) を出力する。

補足: \(\lfloor (N-1) / K \rfloor\) は「\(1\) 以上 \(N-1\) 以下の \(K\) の倍数の個数」を表します。これは区間 \(K, 2K, \ldots\) のうち最後の区間 \(N\) より前のものだけを数えていることに相当します。

計算量

• 時間計算量: \(O(N)\)（配列の総和を計算するため）
• 空間計算量: \(O(N)\)（配列 \(A\) を格納するため）

実装のポイント

• \(A_i\) が最大 \(10^9\)、\(N\) が最大 \(2 \times 10^5\) なので、総和は最大 \(2 \times 10^{14}\) 程度になります。C++ などでは 64-bit 整数型（long long）を使う必要がありますが、Python では整数のオーバーフローを気にする必要はありません。

• 休憩回数の計算で、\(K \geq N\) の場合（\(K\) 区間走り終える前にドライブが終わる場合）は休憩が0回であることに注意しましょう。コード中では K <= N - 1 の条件で分岐していますが、実際には \(\lfloor (N-1) / K \rfloor\) の式だけでも \(K \geq N\) のとき自動的に \(0\) になるため、条件分岐なしでも正しく動作します。

  ソースコード

N, K = map(int, input().split())
A = list(map(int, input().split()))
total = sum(A)
if K <= N - 1:
    breaks = (N - 1) // K
else:
    breaks = 0
print(total + breaks)

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