概要

\(N\) 個の食材をそれぞれ \(T_i\) 秒かけて処理し、その間にちょうど \(M\) 回の休憩（各 \(R\) 秒）を挟むときの最小合計時間を求める問題です。

考察

この問題では、食材の処理順を自由に決めることができ、さらに休憩は「食材の処理が終わった直後」にしか取れません。休憩の合計時間は常に \(M \times R\) であり、作業時間の合計は常に \(\sum T_i\) です。

重要な観察は、「どのタイミングで休憩を入れても、全体の合計時間は変わらない」ということです。なぜなら：

• 休憩は合間に入れられるものであり、作業の順序を変えても合計時間に影響はない。
• 最初と最後には休憩を入れられないが、\(M \leq N - 1\) の制約により、必ず間に合うように休憩を入れることができる。

したがって、最適な戦略は単純に：

\[ \text{合計時間} = \sum_{i=1}^{N} T_i + M \times R \]

となります。

例えば、\(N = 3\), \(M = 1\), \(R = 5\), \(T = [2, 3, 5]\) の場合：

• 合計作業時間：\(2 + 3 + 5 = 10\)
• 休憩時間：\(1 \times 5 = 5\)
• 合計時間：\(10 + 5 = 15\)

どんな順番で処理しても、間に1回休憩を入れるだけなので、合計は変わりません。

アルゴリズム

解法は非常にシンプルです：

1. 入力から食材の処理時間 \(T_i\) を読み込みます。
2. 合計作業時間を計算します：\(\text{total\_work} = \sum T_i\)
3. 休憩時間の合計を計算します：\(\text{total\_rest} = M \times R\)
4. 両者を足した値を出力します。

この問題では、食材をソートしたり、休憩を入れる位置を工夫する必要はありません。最終的な合計時間は常に一定です。

計算量

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

※入力を配列に格納し、合計を取る操作が主な処理です。

実装のポイント

• 入力の受け取りを高速に行う（例：sys.stdin.read を使用）。

• 合計の計算は組み込み関数 sum() を使うと簡潔に記述できます。

• 特に条件分岐やループ処理は不要で、素直に計算すればOKです。

  ソースコード

import sys
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    R = int(data[2])
    
    T = list(map(int, data[3:3+N]))
    
    # 合計作業時間
    total_work = sum(T)
    
    # 休憩時間の合計
    total_rest = M * R
    
    # 休憩を入れた合計時間の最小値を求める
    # 食材をソートして、最適な休憩位置を考える
    
    T.sort()
    
    # 最適な休憩位置は、最も長いM個の作業の直後
    # つまり、休憩は最大のM個のT_iの直後に入れるのが最適
    
    # 最大のM個のT_iを選んで、それらの直後に休憩を入れると
    # 合計時間が最小になる
    
    # しかし実際には、休憩は作業の「終了直後」に入れることに注意
    # よって、休憩を入れるタイミングを遅らせることで、
    # 次の作業時間が短いものを早く終わらせることが可能
    
    # 計算方法：
    # 全体の合計時間 = 作業時間の合計 + 休憩時間の合計
    # ただし、休憩は作業の合間に挟むので、効率的な配置が必要
    
    # 解法：
    # 食材を時間でソートしておく。
    # 休憩は、作業が終わった直後に入れられる。
    # よって、M回の休憩をどこに入れるか？
    # →最も長いM個の作業の直後に休憩を入れるのが最適
    
    # 実際には、M個の休憩を最大のM個のT_iの直後に入れれば良い
    # しかし、そうすると合計が増えるだけなので、
    # 単純に合計作業時間 + 合計休憩時間でOK
    
    # ただし、制約により休憩は最初と最後には入れられない
    # また、ちょうどM回入れなければならない
    
    # 正しいアプローチ:
    # 食材をソートし、最も作業時間が短い順に並べる
    # そして、途中でM回の休憩を挟む
    # 合計時間 = 作業時間の合計 + 休憩時間の合計
    # ただし、休憩の挿入位置によって合計時間が変わる
    
    # ソート済みリストで、M回の休憩を適切に挟む
    # →連続した作業時間の合計 + 休憩時間
    
    # 最小化のポイントは？
    # →休憩は作業の合間に入れられるため、
    # 合計時間は単純に (sum(T) + M*R) になる
    
    # ただし、休憩は作業の「終了直後」にしか入れられない
    # よって、最後の作業の後には休憩は入れられない
    
    # よって、最大のM個の作業の直後に休憩を入れるのが最適
    
    # 実装:
    # T を昇順にソート
    # 最後の(M)個の作業時間のうち、休憩を挟む
    # つまり、一番最後の作業時間以外の、大きい方からM個
    
    # しかし実際には、どんな順番でも合計時間は同じ？
    # →違います。休憩を入れる位置によって変わらない
    
    # 重要なのは、休憩が作業の合間に入れられること
    # つまり、合計時間 = sum(T) + M*R
    
    # ただし、最初と最後には入れられないという制約
    # →N >= M+1 なので必ず可能
    
    # よって答えは常に sum(T) + M*R
    
    result = total_work + total_rest
    print(result)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。