概要

各プロジェクトについて割り当て予算 \(A_i\) が適正予算 \(B_i\) を超えているかを判定し、予算オーバーのプロジェクト数と返還金額の合計を求める問題です。

考察

この問題は非常にシンプルで、各プロジェクトを1つずつ確認していけばよいです。

• \(A_i > B_i\) のとき：予算オーバーなので、カウントを1増やし、返還額 \(A_i - B_i\) を合計に加算する
• \(A_i \leq B_i\) のとき：何もしない

例えば、3つのプロジェクトがあり以下のようなデータだったとします。

この場合、予算オーバーのプロジェクト数は 2、返還金額の合計は \(20 + 50 = \) 70 となります。

特別なアルゴリズムやデータ構造は不要で、素朴に1つずつ調べる方法で十分間に合います。\(N\) が最大 \(2 \times 10^5\) なので、1回のループで処理すれば問題ありません。

アルゴリズム

1. \(N\) を読み込む
2. カウント用変数 count と合計返還額用変数 total を \(0\) で初期化する
3. \(N\) 回ループし、各プロジェクトの \(A_i, B_i\) を読み込む
   • \(A_i > B_i\) ならば count を \(1\) 増やし、total に \(A_i - B_i\) を加算する
4. count と total をスペース区切りで出力する

計算量

• 時間計算量: \(O(N)\) — 各プロジェクトを1回ずつ確認するだけ
• 空間計算量: \(O(1)\) — カウンタと合計値の2変数のみ使用（全データを保持する必要がない）

実装のポイント

• 返還金額の合計は最大で \(N \times (10^9 - 1) \approx 2 \times 10^{14}\) 程度になり得ます。C++ などでは long long を使う必要がありますが、Python では整数のオーバーフローが起きないため、特に気にする必要はありません。

• 全データを配列に格納する必要はなく、読み込みながら逐次処理すれば十分です。

  ソースコード

N = int(input())
count = 0
total = 0
for _ in range(N):
    A, B = map(int, input().split())
    if A > B:
        count += 1
        total += A - B
print(count, total)

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