概要

\(N\) 台の機械をメンテナンスする際、各作業時間 \(T_i\) とその後の整備時間 \(R_i\) が発生します。ただし、最後に作業した機械については整備時間が不要になります。作業順序を工夫して、すべての作業が終わるまでの最短時間を求める問題です。

考察

1. 作業時間の構成を分解する

どのような順番で機械をメンテナンスしても、以下の時間は必ず発生します。 - すべての機械のメンテナンス時間： \(T_1 + T_2 + \dots + T_N\) - 最後に選んだ機械以外の整備時間： \(R_i\) （ \(N-1\) 台分）

全体の作業時間は、数式で表すと以下のようになります。 $\(\text{合計時間} = \sum_{i=1}^{N} T_i + \sum_{i \in \text{最後以外}} R_i\)$

2. 最短にするための戦略

すべての \(T_i\) の合計は、メンテナンスの順番を変えても変化しません。したがって、合計時間を最小にするためには、「最後以外の整備時間の合計」を最小にする必要があります。

すべての整備時間の合計を \(\sum R_i\) とすると、「最後以外の整備時間の合計」は以下の式で書き換えられます。 $\(\sum_{i \in \text{最後以外}} R_i = (\sum_{i=1}^{N} R_i) - R_{\text{最後に作業する機械}}\)$

この値を最小にするには、引く値である \(R_{\text{最後に作業する機械}}\) を最大にすればよい ことがわかります。

3. 結論

1. すべての \(T_i\) を足し合わせる。
2. すべての \(R_i\) を足し合わせる。
3. \(R_i\) の中から最大値を見つける。
4. 「\(T\) の合計 + \(R\) の合計 - \(R\) の最大値」が答えとなる。

アルゴリズム

1. 変数 total_t, total_r, max_r を用意し、それぞれ 0 で初期化する。
2. \(N\) 台の機械について、入力を受け取りながら以下の処理を繰り返す：
   • total_t に \(T_i\) を加算する。
   • total_r に \(R_i\) を加算する。
   • max_r と \(R_i\) を比較し、大きい方で max_r を更新する。
3. total_t + total_r - max_r を計算して出力する。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 台の機械の情報を 1 回ずつ走査するだけなので、線形時間で計算可能です。
• 空間計算量: \(O(N)\)
  • 入力データをすべてリスト等に保持する場合 \(O(N)\) となります。1つずつ処理する場合は \(O(1)\) まで抑えることも可能です。

実装のポイント

• 大きな数値の扱い: \(T_i\) や \(R_i\) が最大 \(10^9\) で \(N\) が \(2 \times 10^5\) なので、合計値は \(10^{14}\) を超えることがあります。Pythonでは整数の大きさに制限がないため問題ありませんが、他の言語（C++など）では 64bit 整数型（long long など）を使用する必要があります。

• 高速な入出力: \(N\) が大きいため、データ量が多い場合は sys.stdin.read().split() を使うなど、入力速度に気をつけると安全です。

  ソースコード

import sys

def solve():
    # 入力をすべて取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    
    total_t = 0
    total_r = 0
    max_r = 0
    
    # 各機械の情報を処理
    for i in range(N):
        t = int(input_data[2 * i + 1])
        r = int(input_data[2 * i + 2])
        
        total_t += t
        total_r += r
        if r > max_r:
            max_r = r
            
    # 全体の時間は (全てのTの合計) + (最後の機械以外のRの合計)
    # これは (全てのTの合計) + (全てのRの合計) - (最後に持ってくる機械のR) と等しい
    # 最短時間を求めるには、最後に持ってくる機械のRを最大にすればよい
    ans = total_t + total_r - max_r
    print(ans)

if __name__ == "__main__":
    solve()

---

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