概要

各商品の販売価格と準備コストが与えられるので、利益が最大化されるように商品を選ぶ問題です。利益は選んだ商品の販売価格の合計から準備コストの合計を引いたものです。

考察

各商品について「販売するかしないか」を独立に決めることができます。利益を最大化するには、それぞれの商品が全体の利益に寄与するかどうかを考えるのが有効です。

各商品 \(i\) について、その商品を販売することで得られる利益は \(A_i - B_i\) です。これが正であれば販売すべきであり、負であれば販売しないべきです。特に、同じ商品を複数回選ぶことはできないので、全商品についてこの判断をすれば最適な選び方が得られます。

例えば、以下のような入力があるとします：

3
5 3
2 4
6 1

このとき各商品の利益は：

• 商品1: \(5 - 3 = 2\)（販売する価値あり）
• 商品2: \(2 - 4 = -2\)（販売しない方が良い）
• 商品3: \(6 - 1 = 5\)（販売する価値あり）

したがって、商品1と3を選ぶことで利益は \(2 + 5 = 7\) となり、これが最大です。

このように、各商品について利益が正かどうかだけを見て選べば良いことが分かります。

素朴なアプローチとして、部分集合を全探索する方法が考えられますが、商品の数 \(N\) が最大で \(2 \times 10^5\) あるため、\(2^N\) の組み合わせは到底計算できません。しかし、実は各商品を独立に判断できるので、全探索は不要です。

アルゴリズム

1. 各商品について、販売価格 \(A_i\) と準備コスト \(B_i\) を読み込む。
2. 各商品に対して、\(A_i - B_i > 0\) であれば、その差を総利益に加える。
3. 最終的な総利益を出力する。

つまり、利益が正になる商品だけを選んで足し合わせるだけで最適解が得られます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（入力データを除く）

各商品を1回ずつ見れば十分なので、線形時間で解けます。

実装のポイント

• 各商品の利益 \(A_i - B_i\) が正かどうかを判定し、正であれば加算するだけなので、シンプルなループで実装できます。

• 1つも選ばない場合の利益は0円であり、初期値を0としておけば自然に処理されます。

  ソースコード

n = int(input())
items = [tuple(map(int, input().split())) for _ in range(n)]

total_profit = 0
for a, b in items:
    if a > b:
        total_profit += a - b

print(total_profit)

---

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