概要

各プロジェクトについて「割り当て予算 \(A_i\) が適正予算 \(B_i\) を超えているか」を判定し、超えている件数と超過分の合計 \(\sum (A_i-B_i)\) を求める問題です。

考察

重要な観察は次の1点です。

• 返還が必要なのは \(A_i > B_i\) のときだけで、その返還額はちょうど \(A_i - B_i\) になる。

したがって、各行を独立に処理して - \(A_i > B_i\) なら件数を \(+1\) - 合計返還額に \((A_i-B_i)\) を加算
すればよいだけです。
プロジェクト間での依存関係はなく、並べ替えや複雑なデータ構造も不要です。

素朴にやっても \(N \le 2 \times 10^5\) なので \(O(N)\) で十分間に合いますが、Python では入力が多いと input() を繰り返す実装で遅くなることがあります。そのため、高速入力（sys.stdin.buffer.read()）でまとめて読み込むと安全です。

例： - \((A,B)=(120,100)\) なら予算オーバーで返還額 \(20\) - \((A,B)=(80,100)\) なら返還不要（\(A \le B\)）

このように全てのプロジェクトをチェックし、件数と合計を集計します。

アルゴリズム

1. \(N\) を読む。
2. cnt = 0（予算オーバーの件数）、total = 0（返還額合計）を用意する。
3. \(i=1\) から \(N\) まで繰り返す：
   • \(A_i, B_i\) を読む
   • もし \(A_i > B_i\) なら
     • cnt += 1
     • total += A_i - B_i
4. cnt と total を出力する。

計算量

• 時間計算量: \(O(N)\)（各プロジェクトを1回ずつ見るだけ）
• 空間計算量: \(O(1)\)（集計用の変数のみ。※入力を一括読み込みする実装では入力分を保持するため実質 \(O(N)\)）

実装のポイント

• \(N\) が最大 \(2 \times 10^5\) なので、Python では高速入力（sys.stdin.buffer.read().split()）を使うと安心です。

• 合計 total は最大で \(N \times 10^9\) 程度になり得ますが、Python の整数は桁あふれしないためそのままで問題ありません。

  ソースコード

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    n = int(next(it))
    cnt = 0
    total = 0
    for _ in range(n):
        a = int(next(it))
        b = int(next(it))
        if a > b:
            cnt += 1
            total += a - b
    sys.stdout.write(f"{cnt} {total}")

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。