概要

\(N\) 個のプロジェクトについて、現在の予算 \(A_i\) が適正予算 \(B_i\) を上回っている（\(A_i > B_i\)）ケースを特定し、その「プロジェクト数」と「予算超過額（\(A_i - B_i\)）の総和」を求める問題です。

考察

各プロジェクトは独立しているため、1つずつ順番に判定を行えばよいです。

1. 条件の判定: 各プロジェクトについて、\(A_i > B_i\) であるかどうかをチェックします。

   • \(A_i > B_i\) の場合：予算オーバーです。カウントを 1 増やし、合計額に \(A_i - B_i\) を加算します。
   • \(A_i \leq B_i\) の場合：予算内です。何も行いません。

2. 数値の大きさ:

   • プロジェクト数 \(N\) は最大 \(2 \times 10^5\) です。そのため、1つずつの処理を \(O(1)\) で行い、全体で \(O(N)\) の計算量に収める必要があります。
   • 返還額の合計は、最大で \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\) 程度になる可能性があります。Pythonでは大きな整数も自動的に扱えますが、他の言語（C++など）では 64bit 整数型（long long など）を使う必要がある点に注意しましょう。

アルゴリズム

1. 予算オーバーのプロジェクト数を数える変数 over_budget_count と、返還額の合計を保持する変数 total_refund を \(0\) で初期化します。
2. 入力された \(N\) 個のペア \((A_i, B_i)\) について、以下の処理を繰り返します。
   • もし \(A_i > B_i\) ならば：
     • over_budget_count に \(1\) を加える。
     • total_refund に \(A_i - B_i\) を加える。
3. 最後に over_budget_count と total_refund を空白区切りで出力します。

計算量

• 時間計算量: \(O(N)\) \(N\) 個の要素を一度ずつ走査するため、プロジェクト数に比例した時間で処理が完了します。
• 空間計算量: \(O(N)\) 今回の実装では sys.stdin.read().split() を用いて入力を一度にリストとして読み込んでいるため、入力サイズに比例したメモリを使用します。 ※ 1行ずつ読み込んで処理するように書き換えれば、\(O(1)\) に抑えることも可能です。

実装のポイント

• 高速な入力: Pythonにおいて \(N\) が大きい（\(10^5\) 以上）場合、input() を繰り返すと実行時間が長くなることがあります。sys.stdin.read().split() を使って一括で読み込む、あるいは sys.stdin.readline を使うことで、入出力によるボトルネックを回避できます。

• 条件分岐: 「\(A_i \leq B_i\) の場合は返還の必要はない」という条件は、単に \(A_i > B_i\) のときだけ処理を行うように実装すれば自然に満たされます。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを取得し、空白で分割してリスト化する
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # プロジェクト数 N
    n = int(input_data[0])
    
    over_budget_count = 0
    total_refund = 0
    
    # 2個ずつ A_i, B_i を取り出して判定する
    for i in range(n):
        a = int(input_data[1 + 2 * i])
        b = int(input_data[2 + 2 * i])
        
        if a > b:
            over_budget_count += 1
            total_refund += a - b
            
    # 結果を出力
    print(f"{over_budget_count} {total_refund}")

if __name__ == "__main__":
    solve()

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