概要

\(N\) 人の納税者に対し、所得が境界額 \(L\) 以下の部分と \(L\) を超える部分で異なる税率を適用し、それぞれの合計税額（小数点以下切り捨て）を求める問題です。

考察

この問題のポイントは、与えられた計算式を正確にプログラムに落とし込むことです。

1. 計算式の確認

所得 \(S\) に対する税額 \(T\) は以下の条件分岐で計算されます。

• 所得が \(L\) 円以下 (\(S \leq L\)) のとき $\(T = \lfloor (S \times P) / 100 \rfloor\)$
• 所得が \(L\) 円を超える (\(S > L\)) のとき $\(T = \lfloor (L \times P + (S - L) \times Q) / 100 \rfloor\)$

ここで重要なのは、所得が \(L\) 円を超えた場合、「\(L\) 円までの税」と「\(L\) 円を超えた分の税」を合算してから最後に切り捨てを行うという点です。途中で個別に切り捨てを行うと誤差が出てしまう可能性があるため、分子をすべて計算してから 100 で割る必要があります。

2. 制約とデータ型

• 納税者数 \(N\) は最大 \(10^5\) なので、各納税者に対して \(O(1)\)（定数時間）で計算し、全体で \(O(N)\) で解く必要があります。
• 所得 \(S\) や境界 \(L\) は最大 \(10^9\) であり、計算の過程（\(S \times P\) など）で値が \(10^{11}\) 程度まで大きくなります。Python の整数型（int）は自動的に多倍長整数として扱われるためオーバーフローの心配はありませんが、他の言語（C++など）では 64bit 整数型（long long）を使用する必要があります。

アルゴリズム

1. 入力から \(N, L, P, Q\) を取得します。
2. \(N\) 人の所得 \(S_i\) について、以下の処理を繰り返します。
   • もし \(S_i \leq L\) なら、tax = (S_i * P) // 100 を計算する。
   • そうでなければ（\(S_i > L\) なら）、tax = (L * P + (S_i - L) * Q) // 100 を計算する。
   • 計算した tax を記録する。
3. 全員の計算が終わったら、結果を順番に出力します。

※ Python の // 演算子は、正の数に対しては床関数（切り捨て）と同じ動作をします。

計算量

• 時間計算量: \(O(N)\) \(N\) 人の所得に対してそれぞれ 1 回ずつ計算を行うため、人数に比例した時間で処理が完了します。
• 空間計算量: \(O(N)\) 入力を一括で読み込み、結果をリストに保持して出力する場合、人数に比例したメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) が \(10^5\) と比較的大きいため、Python では input() を繰り返すよりも sys.stdin.read().split() で一括で読み込み、sys.stdout.write() で一括で出力することで、実行時間を大幅に短縮できます。

• 共通部分の事前計算: \(S > L\) の計算式に出てくる \(L \times P\) はすべての納税者で共通の値です。ループの外であらかじめ計算しておくことで、わずかですが効率を上げることができます。

• 浮動小数点数の回避: / 100 をして math.floor() を使うのではなく、整数同士の計算 // 100 を使うことで、浮動小数点数による精度の問題を完全に回避できます。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白文字で分割します。
    # Nが10^5程度であれば、一括で読み込むのが効率的です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 1行目のパラメータ（N, L, P, Q）を取得します。
    # N: 納税者の人数
    # L: 税率が変わる境界の所得額
    # P: L円以下の部分に適用される税率 (%)
    # Q: L円を超える部分に適用される税率 (%)
    n = int(input_data[0])
    l = int(input_data[1])
    p = int(input_data[2])
    q = int(input_data[3])
    
    # 所得がLを超える場合の計算で繰り返し使われる L * P をあらかじめ計算しておきます。
    lp = l * p
    
    # 各納税者の税額を計算し、結果を格納するリストです。
    results = []
    
    # 各納税者の所得額 S_i は input_data の 5番目（インデックス4）から順に格納されています。
    for i in range(n):
        s = int(input_data[4 + i])
        
        if s <= l:
            # 所得が L 円以下の場合：
            # 税額 = floor(所得 * P / 100)
            tax = (s * p) // 100
        else:
            # 所得が L 円を超える場合：
            # L円以下の部分に P%、それを超える部分 (s - L) に Q% を適用します。
            # 税額 = floor((L * P + (s - L) * Q) / 100)
            tax = (lp + (s - l) * q) // 100
        
        # 数値を文字列に変換してリストに追加します（最後の一括出力のため）。
        results.append(str(tax))
    
    # すべての計算結果を改行で連結し、一括で標準出力に書き出します。
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

---

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