概要

累進課税の計算式に従い、各納税者の所得額に対して税額を求める問題です。所得が境界額 \(L\) 以下か超えるかで場合分けし、床関数（切り捨て）を適用して税額を計算します。

考察

問題の整理

この問題は、2段階の税率を持つ累進課税のシミュレーションです。ポイントは以下の通りです：

• 所得 \(S\) が \(L\) 以下なら、全額に税率 \(P\) % を適用
• 所得 \(S\) が \(L\) を超えるなら、最初の \(L\) 円には税率 \(P\) %、超過分 \((S - L)\) 円には税率 \(Q\) % を適用
• 切り捨ては最後に一度だけ行う（各部分ごとに個別に切り捨てるのではない）

具体例で確認

\(L = 100\), \(P = 10\), \(Q = 23\), \(S = 150\) のとき：

\[T = \left\lfloor \frac{100 \times 10 + 50 \times 23}{100} \right\rfloor = \left\lfloor \frac{1000 + 1150}{100} \right\rfloor = \left\lfloor 21.5 \right\rfloor = 21\]

素朴なアプローチで十分か？

各納税者に対して定数時間で税額を計算できるため、\(N\) 人分をループで処理すれば \(O(N)\) で済みます。\(N \leq 10^5\) なので十分高速です。

オーバーフローに注意

\(S\) や \(L\) は最大 \(10^9\)、\(P, Q\) は最大 \(100\) なので、\(L \times P\) や \((S - L) \times Q\) は最大で \(10^{11}\) 程度になります。Python では整数に上限がないため問題ありませんが、C++ などでは 64 ビット整数を使う必要があります。

アルゴリズム

1. \(N, L, P, Q\) を読み込む
2. 各納税者 \(i\) について所得 \(S_i\) を読み込み、以下の場合分けで税額を計算する：
   • \(S_i \leq L\) のとき：\(T_i = \lfloor S_i \times P \div 100 \rfloor\)
   • \(S_i > L\) のとき：\(T_i = \lfloor (L \times P + (S_i - L) \times Q) \div 100 \rfloor\)
3. Python の整数除算 // は非負整数に対して床関数と一致するので、そのまま使える
4. 各税額を出力する

計算量

• 時間計算量: \(O(N)\) — 各納税者について定数時間の計算を行う
• 空間計算量: \(O(N)\) — 出力用のリストに結果を格納（逐次出力なら \(O(1)\) も可能）

実装のポイント

• 入力の高速化: sys.stdin.read() で一括読み込みし、split() で分割することで、大量の入力を高速に処理しています。input() を \(N\) 回呼ぶよりも高速です。

• 出力の高速化: 各結果をリストに溜めておき、最後に '\n'.join(out) で一括出力しています。print() を \(N\) 回呼ぶオーバーヘッドを避けられます。

• 整数除算 // の挙動: Python の // 演算子は負の方向へ切り捨てますが、\(S \times P\) や \(L \times P + (S-L) \times Q\) はすべて非負なので、通常の切り捨て（床関数）と一致し問題ありません。

• 切り捨てのタイミング: 問題文にも注意書きがある通り、\(L \times P\) と \((S-L) \times Q\) を足してから \(100\) で割ります。個別に割ってから足すと結果が異なる場合があるので注意が必要です。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    L = int(input_data[idx]); idx += 1
    P = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    out = []
    for i in range(N):
        S = int(input_data[idx]); idx += 1
        if S <= L:
            tax = S * P // 100
        else:
            tax = (L * P + (S - L) * Q) // 100
        out.append(str(tax))
    
    print('\n'.join(out))

main()

---

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