概要

\(N\) 個の商品からいくつかを選んで販売し、利益（販売価格の合計 − 準備コストの合計）を最大化する問題です。各商品について「売るか売らないか」を独立に判断すればよいという、貪欲法の基本問題です。

考察

重要な気づき：各商品は独立に判断できる

利益の式を見てみましょう。

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

このように、利益は 各商品ごとの差額 \(A_i - B_i\) の合計 に分解できます。

つまり、ある商品 \(i\) を販売するかどうかは、他の商品の選択に一切影響しません。各商品を独立に判断できるのです。

各商品の判断基準

商品 \(i\) について： - \(A_i - B_i > 0\)（販売価格 > 準備コスト）なら、販売すると利益がプラスになる → 売るべき - \(A_i - B_i \leq 0\)（販売価格 ≤ 準備コスト）なら、販売すると利益がゼロまたはマイナスになる → 売らないべき

具体例

例えば \(N = 3\) で、以下の商品があるとします。

商品	\(A_i\)（販売価格）	\(B_i\)（準備コスト）	\(A_i - B_i\)	判断
1	100	30	+70	売る ✅
2	50	80	−30	売らない ❌
3	200	150	+50	売る ✅

商品 1 と 3 を売り、利益は \(70 + 50 = 120\) 円です。

素朴なアプローチとの比較

全ての商品の組み合わせを試す方法では \(2^N\) 通りを調べる必要があり、\(N = 2 \times 10^5\) ではとても間に合いません。しかし、上記の考察から各商品を独立に判断できるため、\(N\) 回のループで解けます。

アルゴリズム

1. 利益の合計 ans を \(0\) で初期化する。
2. 各商品 \(i\) について、\(A_i > B_i\) ならば ans に \(A_i - B_i\) を加算する。
3. 最終的な ans を出力する。

（1つも \(A_i > B_i\) となる商品がなければ、ans は \(0\) のままとなり、「1つも選ばない場合の利益は \(0\) 円」という条件と整合します。）

計算量

• 時間計算量: \(O(N)\) — 各商品を1回ずつ見るだけ
• 空間計算量: \(O(1)\) — 合計値を保持する変数のみ（入力を保存する必要がない）

実装のポイント

• \(A_i, B_i\) がそれぞれ最大 \(10^9\) のため、合計は最大 \(N \times 10^9 = 2 \times 10^{14}\) 程度になります。C++ などでは long long を使う必要がありますが、Python では整数のオーバーフローを気にする必要はありません。

• 商品の情報を配列に保存する必要はなく、入力を読みながらその場で判定・加算すれば十分です。

  ソースコード

N = int(input())
ans = 0
for _ in range(N):
    a, b = map(int, input().split())
    if a > b:
        ans += a - b
print(ans)

---

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