概要

各商品の「販売価格と準備コストの差」を計算し、利益がプラスになる商品だけを選んだときの合計額を求める問題です。

考察

商品の集合 \(S\) を選んだときの利益の式は、次のように変形できます。

\[\text{利益} = \sum_{i \in S} A_i - \sum_{i \in S} B_i = \sum_{i \in S} (A_i - B_i)\]

この式から、 \(i\) 番目の商品を選んだとき、全体の利益には \((A_i - B_i)\) 円が加算されることがわかります。 高橋君は各商品を選ぶか選ばないかを完全に独立に決めることができます。したがって、全体の利益を最大化するためには、選んだときの利益がプラスになる（つまり \(A_i - B_i > 0\) となる）商品だけをすべて選び、マイナスになる商品は1つも選ばないようにすればよいです。

たとえば、以下の3つの商品があったとします。 - 商品1: \(A_1 = 100, B_1 = 30 \implies\) 利益は \(100 - 30 = 70\) 円 - 商品2: \(A_2 = 50, B_2 = 80 \implies\) 利益は \(50 - 80 = -30\) 円 - 商品3: \(A_3 = 200, B_3 = 150 \implies\) 利益は \(200 - 150 = 50\) 円

この場合、商品1と商品3を選べば、利益は \(70 + 50 = 120\) 円となり、これが最大値です。

もし、考えられるすべての選び方（\(2^N\) 通り）を試す素朴な全探索を行おうとすると、\(N \le 2 \times 10^5\) という制約下では計算回数が天文学的な数字になり、実行時間制限超過（TLE）となってしまいます。しかし、上記のように各商品を独立に判定すれば、\(1\) つの商品につき \(1\) 回の計算で済むため、高速に答えを求めることができます。

アルゴリズム

1. 利益の合計を管理する変数を \(0\) で初期化します。
2. 各商品 \(i\) （\(1 \leq i \leq N\)）について、単体での利益 \(A_i - B_i\) を計算します。
3. その値が \(0\) より大きければ、利益の合計に加算します。数式で表すと、各商品について \(\max(0, A_i - B_i)\) を足していくことになります。
4. すべての商品について確認し終えたときの合計値が、求める利益の最大値です。

計算量

• 時間計算量: \(O(N)\)
  • 各商品に対して引き算と大小比較（\(\max\) の計算）を1回ずつ行うだけなので、商品の個数 \(N\) に比例した時間で処理が終わります。
• 空間計算量: \(O(N)\)
  • 入力データを一括で読み込み、配列（リスト）として保持するためのメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) が最大 \(2 \times 10^5\) と大きいため、Pythonの場合は input() を何度も呼ぶのではなく、sys.stdin.read().split() を使って入力を一括で読み込むと実行時間を短縮できます。

• 簡潔な記述: Pythonでは sum() とジェネレータ式を組み合わせることで、ループ処理を1行で簡潔に書くことができます。

• オーバーフローへの配慮: 利益の合計は最大で \(N \times \max(A_i) \approx 2 \times 10^{14}\) となり、32bit整数の上限（約 \(2 \times 10^9\)）を超えます。Pythonは自動で多倍長整数として扱うため問題ありませんが、C++などの他言語で実装する場合は、答えを格納する変数に64bit整数（long long など）を使用する必要があります。

  ソースコード

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    ans = sum(max(0, int(data[i]) - int(data[i+1])) for i in range(1, 2 * N, 2))
    print(ans)

if __name__ == '__main__':
    main()

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