概要

本問題は、与えられた \(N\) 件の案件のうち、納品日数が \(M\) 日以下である案件の報酬の合計を求め、そこから指定された手数料 \(P\) %を差し引いた手取り額を計算する問題です。

考察

まず、高橋君が \(M\) 日以内に納品できる案件の条件を整理します。 ある案件 \(i\) が \(M\) 日以内に完了するためには、その案件の納品にかかる日数 \(D_i\) が \(M\) 以下（\(D_i \le M\)）である必要があります。

したがって、問題を解く手順は以下の2ステップに分解できます。 1. \(N\) 個の案件を順番に確認し、\(D_i \le M\) を満たす案件の報酬 \(V_i\) の総和 \(S\) を計算する。 2. 総和 \(S\) から手数料 \(P\) %を差し引いた金額を計算する。

手数料の計算方法

手数料が \(P\) %であるため、高橋君の手元に残る金額は全体の \((100 - P)\) %となります。 これを数式で表すと以下のようになります。 $\( \text{手取り額} = S \times \frac{100 - P}{100} \)\( 問題文より、小数点以下は切り捨てる必要があります。C++などの多くのプログラミング言語における整数の割り算（`/` 演算子）は、正の数同士の演算において自動的に小数点以下を切り捨てる（床関数 \)\lfloor \dots \rfloor$ と同じ挙動になる）ため、 S * (100 - P) / 100 をそのまま計算すれば正しい答えが得られます。

オーバーフローへの注意（重要）

制約を確認すると、案件数 \(N\) は最大で \(2 \times 10^5\)、各案件の報酬 \(V_i\) は最大で \(10^6\) です。 すべての案件が条件を満たす場合、報酬の総和 \(S\) は最大で \(2 \times 10^5 \times 10^6 = 2 \times 10^{11}\) に達します。 一般的な32ビット整数型（C++の int 型など）が表現できる最大値は約 \(2 \times 10^9\) であるため、int 型を使用するとオーバーフロー（数値が溢れて不正な値になる現象）が発生してしまいます。 そのため、総和を保持する変数や計算の過程では、より大きな値を扱える64ビット整数型（C++の long long 型）を使用する必要があります。

アルゴリズム

1. 報酬の総和を保持する変数 total_reward を 0 で初期化します（型は long long）。
2. 各案件の情報 \(D_i, V_i\) を順に入力から受け取ります。
3. もし \(D_i \le M\) を満たすならば、 total_reward に \(V_i\) を加算します。
4. すべての案件の処理が終わった後、 total_reward * (100 - P) / 100 を計算し、その結果を出力します。

計算量

• 時間計算量: \(O(N)\) 各案件の情報を1回ずつループで確認するため、案件数 \(N\) に比例した時間で処理が完了します。\(N \le 2 \times 10^5\) であるため、実行時間制限に対して十分に高速です。
• 空間計算量: \(O(1)\) 入力を配列などに保存せず、その都度判定して加算しているため、使用するメモリ量は変数数個分の定数空間で済みます。

実装のポイント

• 高速な入出力: C++では、入力データの件数 \(N\) が \(2 \times 10^5\) と多いため、 cin.tie(NULL) や ios_base::sync_with_stdio(false) を用いて入出力を高速化しておくことで、実行時間を短縮できます。

• 適切な型選択: 報酬の合計値だけでなく、計算の途中で用いる変数 \(M\) や \(P\) も long long 型で宣言しておくことで、型変換によるバグやオーバーフローを未然に防ぐことができます。

  ソースコード

#include <iostream>

using namespace std;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long M, P;
    if (!(cin >> N >> M >> P)) return 0;

    long long total_reward = 0;
    for (int i = 0; i < N; ++i) {
        long long D, V;
        cin >> D >> V;
        if (D <= M) {
            total_reward += V;
        }
    }

    // 手数料を差し引いた金額を計算（小数点以下切り捨て）
    long long ans = total_reward * (100 - P) / 100;

    cout << ans << "\n";

    return 0;
}

---

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