概要

\(M\) 日以内に納品できる案件の報酬を合計し、そこからエージェント手数料（\(P\)%）を差し引いた金額を求める問題です。

考察

• 案件 \(i\) が \(M\) 日以内に納品完了するかどうかは、\(D_i \leq M\) かどうかで判定できます。
• 条件を満たす案件の報酬を合計した後、手数料を引いた残りが答えです。
• 報酬の合計を \(S\) とすると、手数料は \(S \times \frac{P}{100}\) なので、手取りは \(S \times \frac{100 - P}{100}\) となります。
• この問題は素朴に全案件を一度走査するだけで解けるため、特別なアルゴリズムは不要です。

具体例: \(N=3, M=5, P=20\) で、案件が \((D=3, V=1000), (D=7, V=2000), (D=5, V=3000)\) の場合： - \(D \leq 5\) を満たすのは案件1（\(D=3\)）と案件3（\(D=5\)） - 報酬合計 \(S = 1000 + 3000 = 4000\) - 手取り \(= 4000 \times (100 - 20) / 100 = 4000 \times 80 / 100 = 3200\)

アルゴリズム

1. \(N, M, P\) を読み込む。
2. 各案件について \(D_i\) と \(V_i\) を読み込み、\(D_i \leq M\) ならば報酬合計 total に \(V_i\) を加算する。
3. 手取り金額を total * (100 - P) / 100 で計算する（C++の整数除算は自動的に小数点以下切り捨て）。
4. 結果を出力する。

計算量

• 時間計算量: \(O(N)\)（全案件を一度ずつ確認するだけ）
• 空間計算量: \(O(1)\)（報酬合計を保持する変数のみ）

実装のポイント

• オーバーフローに注意: \(V_i\) は最大 \(10^6\)、\(N\) は最大 \(2 \times 10^5\) なので、報酬合計は最大 \(2 \times 10^{11}\) になり得ます。int（約 \(2 \times 10^9\)）では溢れるため、long long を使用する必要があります。

• 整数除算による切り捨て: C++では整数同士の除算は自動的に小数点以下が切り捨てられるため、floor 関数を使わなくても問題の要求を満たします。ただし、これは被除数が非負の場合に正しく動作します（本問では \(0 \leq P \leq 100\) より total * (100 - P) は非負なので問題ありません）。

• 浮動小数点を避ける: 手数料計算で total * (1.0 - P/100.0) のように浮動小数点数を使うと、精度の問題で答えがずれる可能性があります。整数演算のみで処理するのが安全です。

  ソースコード

#include <iostream>
using namespace std;

int main(){
    int N, M, P;
    cin >> N >> M >> P;
    long long total = 0;
    for(int i = 0; i < N; i++){
        long long D, V;
        cin >> D >> V;
        if(D <= M) total += V;
    }
    long long ans = total * (100 - P) / 100;
    cout << ans << endl;
    return 0;
}

---

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