概要

この問題は、与えられた \(N\) 件の案件のうち、期日 \(M\) 日以内に納品可能な案件の報酬を足し合わせ、そこから \(P\) %の手数料を差し引いた最終的な手取り額を求める問題です。

考察

1. どの案件を受けるべきか？

高橋君は今後 \(M\) 日間の収支を計算したいと考えています。 案件 \(i\) を完了するには \(D_i\) 日かかります。したがって、 \(M\) 日以内に納品が完了する条件は以下のようになります。 $\(D_i \leq M\)$

この条件を満たす案件の報酬 \(V_i\) をすべて足し合わせたものを、全体の報酬の総和 \(S\) とします。条件を満たさない（\(D_i > M\)）案件は期間内に終わらないため、報酬を得ることはできず、無視して構いません。

2. 手数料の計算と小数による誤差の回避

全体の報酬 \(S\) から \(P\) %の手数料を引いた金額を計算します。 手元に残る金額の割合は \((100 - P)\) % です。したがって、求める金額は以下の式で表されます。 $\(\text{手取り額} = S \times \frac{100 - P}{100}\)$

プログラミングにおいて、この計算を S * (100 - P) / 100 のように浮動小数点数（小数）を使って計算すると、丸め誤差が発生し、正しい整数値が得られない原因になります。 今回の問題では「小数点以下を切り捨てた整数」を出力する必要があるため、整数型同士の割り算（切り捨て除算）を用いて以下のように計算することで、誤差を完全に防ぐことができます。 $\(\text{ans} = (S \times (100 - P)) \text{ // } 100\)$ ※ // はPythonにおける切り捨て除算の演算子です。

アルゴリズム

1. 報酬の合計を保持する変数 \(S\) を \(0\) で初期化します。
2. 各案件 \(i\) (\(1 \leq i \leq N\)) について、順に以下の処理を行います。
   • もし \(D_i \leq M\) であれば、 \(S\) に \(V_i\) を加算します。
3. すべての案件を走査し終えたら、 \(S \times (100 - P) \text{ // } 100\) を計算し、出力します。

計算量

• 時間計算量: \(O(N)\) 案件の数 \(N\) に対して、ループを1回だけ回して各案件を判定するため、 \(O(N)\) の時間で処理が完了します。 \(N \le 2 \times 10^5\) であるため、実行時間制限（通常2秒）に対して十分高速に動作します。
• 空間計算量: \(O(N)\) 入力を一括で取得してリストに格納しているため、入力のサイズに比例したメモリを使用します。

実装のポイント

• 高速な入力処理: Pythonで入力数が多い（\(N \le 2 \times 10^5\)）場合、 input() を何度も呼び出すと実行時間が長くなってしまいます。 sys.stdin.read().split() を使用して入力を一度にすべて読み込むことで、高速に処理を行うことができます。

• 整数型による計算: 考察で述べた通り、小数の計算を挟まずに S * (100 - P) // 100 とすることで、安全かつ正確に小数点以下を切り捨てた整数を得ることができます。

  ソースコード

import sys

def main():
    # 入力をすべて取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    P = int(input_data[2])
    
    S = 0
    # 各案件の情報を処理
    for i in range(3, 3 + 2 * N, 2):
        d = int(input_data[i])
        v = int(input_data[i+1])
        if d <= M:
            S += v
            
    # 手数料を差し引いた金額を計算（小数点以下切り捨て）
    ans = S * (100 - P) // 100
    print(ans)

if __name__ == '__main__':
    main()

---

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