概要

各プロジェクトの割り当て予算と適正予算を比較し、予算オーバーとなっているプロジェクト数と返還必要額の合計を求める問題です。

考察

この問題は各プロジェクトについて \(A_i > B_i\) かどうかを判定するだけの単純な問題です。各プロジェクトを独立にチェックすればよく、プロジェクト間の関係性を考慮する必要はありません。入力サイズが最大 \(2 \times 10^5\) と大きいため、効率的な読み込みと処理が求められますが、各プロジェクトの処理が定数時間で完了するため、問題なく処理できます。

アルゴリズム

1. プロジェクト数 \(N\) を読み込む
2. 各プロジェクトについて \(A_i\) と \(B_i\) を読み込む
3. 各プロジェクトについて \(A_i > B_i\) かどうかを判定する
   • 条件を満たす場合、カウンタを1増やし、超過金額 \((A_i - B_i)\) を合計に加算する
4. 最終的なカウンタ値と超過金額の合計を出力する

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 個のプロジェクトをそれぞれ定数時間で処理するため
• 空間計算量: \(O(N)\)
  • 入力データを格納するためのメモリが必要

実装のポイント

• 標準入力からの効率的な読み込みのために sys.stdin.read().split() を使用

• 一度にすべてのデータを読み込むことで、複数回の読み込み操作を回避

• インデックス管理でデータを順次処理

• 文字列フォーマットを使用して出力を整形

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    count = 0
    total = 0
    index = 1
    for _ in range(n):
        a = int(data[index])
        b = int(data[index + 1])
        index += 2
        if a > b:
            count += 1
            total += (a - b)
    print(f"{count} {total}")

if __name__ == "__main__":
    main()

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