概要

\(N\) 台の機械を好きな順番でメンテナンスするとき、作業時間と工具整備時間の合計を最小化する問題です。最後の機械の後には工具整備が不要であることがポイントです。

考察

合計時間の構造を理解する

機械をある順番 \(\sigma_1, \sigma_2, \dots, \sigma_N\) でメンテナンスするとき、合計時間は次のようになります：

\[\text{合計時間} = \underbrace{T_{\sigma_1} + R_{\sigma_1}}_{\text{1台目}} + \underbrace{T_{\sigma_2} + R_{\sigma_2}}_{\text{2台目}} + \cdots + \underbrace{T_{\sigma_{N-1}} + R_{\sigma_{N-1}}}_{\text{N-1台目}} + \underbrace{T_{\sigma_N}}_{\text{最後（整備不要）}}\]

これを整理すると：

\[\text{合計時間} = \sum_{i=1}^{N} T_i + \sum_{i=1}^{N} R_i - R_{\sigma_N}\]

ここで重要な気づきがあります。\(\sum T_i\) と \(\sum R_i\) は順番によらず一定です。変化するのは最後にメンテナンスする機械の \(R_{\sigma_N}\) だけです。

最適な戦略

合計時間は \(\sum T_i + \sum R_i - R_{\sigma_N}\) なので、これを最小化するには \(R_{\sigma_N}\) を最大化すればよいです。

つまり、工具整備時間 \(R_i\) が最も大きい機械を最後にメンテナンスするのが最適です。

具体例

例えば \(N = 3\) で、\((T_1, R_1) = (2, 5)\), \((T_2, R_2) = (3, 1)\), \((T_3, R_3) = (4, 3)\) の場合：

• \(\sum T_i = 2 + 3 + 4 = 9\)
• \(\sum R_i = 5 + 1 + 3 = 9\)
• \(\max(R_i) = 5\)（機械1）

最後に機械1を持ってくると、合計時間 \(= 9 + 9 - 5 = 13\) 秒で最小となります。

アルゴリズム

1. 全ての \(T_i\) の合計 \(\sum T_i\) を求める。
2. 全ての \(R_i\) の合計 \(\sum R_i\) を求める。
3. \(R_i\) の最大値 \(\max(R_i)\) を求める。
4. 答えは \(\sum T_i + \sum R_i - \max(R_i)\) である。

計算量

• 時間計算量: \(O(N)\) — 全ての値を1回ずつ走査するだけ
• 空間計算量: \(O(N)\) — 入力の格納に使用（合計値だけ保持すれば \(O(1)\) も可能）

実装のポイント

• \(T_i, R_i\) が最大 \(10^9\)、\(N\) が最大 \(2 \times 10^5\) なので、合計値は最大約 \(4 \times 10^{14}\) 程度になります。Pythonでは整数のオーバーフローを気にする必要はありませんが、C++などでは long long を使う必要があります。

• 順番を実際に構築する必要はなく、合計と最大値だけ求めれば十分です。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    machines = []
    for i in range(N):
        T = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        machines.append((T, R))
    
    # Total time = sum of all T_i + sum of R_i for all except the last machine
    # We want to minimize total time, so we want to maximize the R of the last machine
    # But wait - we need to think more carefully.
    #
    # Total time = sum(T_i) + sum of R_i for machines not last
    # = sum(T_i) + sum(R_i) - R_last
    # To minimize, we maximize R_last, i.e., put the machine with largest R last.
    
    total_T = sum(t for t, r in machines)
    total_R = sum(r for t, r in machines)
    max_R = max(r for t, r in machines)
    
    print(total_T + total_R - max_R)

main()

---

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