概要

各トラックについて、荷物の重量上限 \(T\) と個数上限 \(R\) の両方を満たす範囲で、積み込める荷物の最大個数を求める問題です。

考察

トラック \(i\) に荷物を \(k\) 個積むとき、以下の2つの条件を同時に満たす必要があります：

1. 重量制限: \(P_i \times k \leq T\)（合計重量が積載上限以下）
2. 個数制限: \(k \leq R\)（個数が上限以下）

条件1から、重量だけを考えたときに積める最大個数は \(k \leq \lfloor T / P_i \rfloor\) です。ここで \(\lfloor \cdot \rfloor\) は切り捨て（整数除算）を表します。

例えば、\(T = 100\)、\(P_i = 30\) のとき、\(\lfloor 100 / 30 \rfloor = 3\) なので重量的には最大3個積めます（\(30 \times 3 = 90 \leq 100\)、\(30 \times 4 = 120 > 100\)）。

最終的な答えは、重量制限から求めた最大個数 \(\lfloor T / P_i \rfloor\) と個数上限 \(R\) の小さい方になります：

\[r_i = \min\left(\left\lfloor \frac{T}{P_i} \right\rfloor, R\right)\]

この計算は各トラックについて独立に \(O(1)\) で行えるため、素朴に全トラックについてループすれば十分高速です。特別なアルゴリズムは必要ありません。

アルゴリズム

1. \(N\), \(R\), \(T\) を入力から読み取る。
2. 各トラック \(i\)（\(1 \leq i \leq N\)）について：
   • 荷物1個の重さ \(P_i\) を読み取る。
   • 重量制限による最大個数 \(\lfloor T / P_i \rfloor\) を計算する。
   • \(r_i = \min(\lfloor T / P_i \rfloor, R)\) を求める。
3. \(r_1, r_2, \ldots, r_N\) をスペース区切りで出力する。

具体例: \(N=3\), \(R=5\), \(T=100\), \(P = [30, 10, 50]\) の場合

計算量

• 時間計算量: \(O(N)\)（各トラックについて \(O(1)\) の計算を \(N\) 回）
• 空間計算量: \(O(N)\)（結果を格納する配列）

実装のポイント

• \(T\) は最大 \(10^{18}\) と非常に大きいため、C++ などでは long long 型を使う必要があります。Python では整数のオーバーフローがないため、その心配は不要です。

• T // P は Python の整数除算で、自動的に切り捨てが行われます。

• 入力が大きくなる可能性があるため、sys.stdin.buffer.read() でまとめて読み込むことで高速化しています。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    R = int(input_data[1])
    T = int(input_data[2])
    
    results = []
    for i in range(N):
        P = int(input_data[3 + i])
        # Maximum k such that P * k <= T, i.e., k <= T // P
        max_k = T // P
        if max_k >= R:
            results.append(R)
        else:
            results.append(max_k)
    
    sys.stdout.write(' '.join(map(str, results)) + '\n')

main()

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