概要

各商品の販売価格と準備コストが与えられたとき、利益が正となる商品のみを選ぶことで最大利益を得られる問題です。

考察

各商品 \(i\) の利益は \(A_i - B_i\) で計算できます。利益が正の商品は販売することで全体の利益を増やせますが、利益が負の商品を販売すると全体の利益が減少してしまいます。したがって、利益が正の商品だけを選んで販売するのが最適な戦略となります。

素朴なアプローチとして全ての商品の組み合わせを試す方法がありますが、\(N\) が最大 \(2 \times 10^5\) と大きいため、\(2^N\) 通りの組み合わせを試すことは現実的ではありません。しかし、各商品の選択が独立であることと、利益の計算が加算的であることから、各商品を個別に評価できることに気付くことが重要です。

アルゴリズム

1. 各商品について \(A_i - B_i\) を計算し、利益を求める
2. 利益が正の商品だけを選び、それらの利益の総和を計算する
3. 利益の総和を出力する

このアルゴリズムでは、利益が正の商品は必ず含め、負の商品は含めないという貪欲法を用いています。各商品の選択が他の商品に影響を与えないため、この単純な方法で最適解が得られます。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個の商品それぞれに対して定数時間の計算を行うため
• 空間計算量: \(O(N)\)
  • 商品のデータを格納するための配列が必要なため

実装のポイント

• 入力の読み込みは sys.stdin.read を使用して一度に読み込むことで高速化しています

• 各商品の利益計算はループ内で逐次行い、正の場合のみ総和に加算します

• 1つも商品を選ばない場合の利益が0円であるため、特別な処理は必要ありません

  ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    A = []
    B = []
    index = 1
    for i in range(n):
        a = int(data[index])
        b = int(data[index+1])
        index += 2
        A.append(a)
        B.append(b)
    
    total_profit = 0
    for i in range(n):
        profit = A[i] - B[i]
        if profit > 0:
            total_profit += profit
            
    print(total_profit)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。