概要

\(N\) 台のトラックに対し、荷物の重さによる制限（合計 \(T\) キロ以下）と、個数による制限（最大 \(R\) 個）の 2 つの制約を満たしつつ、積み込める荷物の最大個数を求める問題です。

考察

各トラック \(i\) について、積み込む荷物の個数を \(k\) としたとき、満たすべき条件は以下の 2 つです。

1. 重量制限: 荷物 1 個の重さが \(P_i\) なので、合計重量は \(P_i \times k\) です。これが \(T\) 以下である必要があるため、\(P_i \times k \leq T\) を満たす必要があります。
2. 個数制限: 個数そのものに上限があるため、\(k \leq R\) を満たす必要があります。

まず、条件 1 の重量制限から \(k\) の最大値を考えます。 \(P_i \times k \leq T\) という不等式を \(k\) について解くと、\(k \leq \frac{T}{P_i}\) となります。\(k\) は整数なので、この条件から得られる \(k\) の最大値は \(T\) を \(P_i\) で割ったときの商（小数点以下切り捨て）となります。これを \(k_{weight} = \lfloor T / P_i \rfloor\) と置きます。

次に、条件 2 の個数制限 \(k \leq R\) を考慮します。 求める最大個数 \(r_i\) は、これら 2 つの制限を同時に満たす最大の整数なので、 $\(r_i = \min(R, \lfloor T / P_i \rfloor)\)$ となります。

\(N\) が最大 \(2 \times 10^5\) と大きいため、各トラックの計算を効率的に行う必要があります。今回の式は \(O(1)\) で計算できるため、全体で \(O(N)\) となり、十分に実行時間制限内に間に合います。

アルゴリズム

1. 入力から \(N, R, T\) および各 \(P_i\) を取得します。
2. 各 \(i = 1, \dots, N\) について、以下の計算を行います。
   • 重量制限による最大個数 \(k_{weight} = T \text{ // } P_i\) （整数の切り捨て除算）を計算する。
   • \(k_{weight}\) と \(R\) のうち、小さい方の値を \(r_i\) とする。
3. 求めた \(r_i\) を順番にスペース区切りで出力します。

計算量

• 時間計算量: \(O(N)\)
  • 各トラックに対して定数時間で計算が終わるため、トラックの台数 \(N\) に比例した時間で処理が完了します。
• 空間計算量: \(O(N)\)
  • 入力された \(P_i\) の保持および出力する結果の格納に \(O(N)\) のメモリを使用します。

実装のポイント

• 大きな数値の扱い: \(T\) が最大 \(10^{18}\) と非常に大きいため、プログラミング言語によっては 64 ビット整数型（long long など）を使用する必要があります。Python の場合は標準で多倍長整数をサポートしているため、オーバーフローを気にせず計算できます。

• 高速な入出力: \(N\) が大きいため、Python では input() を繰り返すよりも sys.stdin.read().split() などで一括して入力を読み込み、sys.stdout.write() でまとめて出力する手法が実行時間の短縮に有効です。

  ソースコード

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストに格納します。
    # Nが最大2*10^5と大きいため、一括読み込みが効率的です。
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は終了します。
    if not input_data:
        return
    
    # 最初の3つの要素は N (トラック台数), R (積み込み回数上限), T (積載制限) です。
    n = int(input_data[0])
    r_limit = int(input_data[1])
    t_limit = int(input_data[2])
    
    # 各トラックの結果を格納するためのリストを事前に確保します。
    results = [None] * n
    
    # 各トラック i について、過積載にならずに積み込める最大回数 r_i を計算します。
    # k 回目の積み込みが完了した時点での重さは P_i * k です。
    # 過積載にならない条件は P_i * k <= T なので、k <= T / P_i となります。
    # したがって、最大回数は floor(T / P_i) と R の小さい方になります。
    for i in range(n):
        # input_data[i + 3] が各トラックの P_i に対応します。
        p_i = int(input_data[i + 3])
        
        # Pythonの // 演算子は整数の切り捨て除算（floor division）を行います。
        max_possible_loads = t_limit // p_i
        
        # 積み込み回数上限 R を超えないように制限します。
        if max_possible_loads > r_limit:
            r_i = r_limit
        else:
            r_i = max_possible_loads
        
        # 出力用に文字列に変換してリストに格納します。
        results[i] = str(r_i)
    
    # 全ての結果をスペース区切りで1行に出力します。
    sys.stdout.write(" ".join(results) + "\n")

if __name__ == "__main__":
    main()

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