概要

\(M\) 台の独立した機械それぞれで、稼働時間 \(K\) 分以内に利益を最大化する製品の組み合わせを求める問題。各機械は同じ条件なので、1台あたりの最大利益を求めて \(M\) 倍すればよい。1台の問題は個数制限なしナップサック問題に帰着される。

考察

重要な気づき①：機械ごとに独立

\(M\) 台の機械はすべて同じ稼働時間 \(K\) を持ち、互いに独立に動作します。また原材料に制限がないため、各機械で製造できる製品に個数上限がありません。したがって、1台の機械で得られる最大利益を求め、それを \(M\) 倍するだけで答えが得られます。

重要な気づき②：ナップサック問題への帰着

1台の機械について考えると： - 容量（時間）\(K\) のナップサックがある - 各製品 \(i\) は重さ \(T_i\)（製造時間）、価値 \(P_i - C_i\)（利益）を持つ - 同じ製品を何個でも製造できる

これはまさに個数制限なしナップサック問題（Unbounded Knapsack Problem）です。

利益が負の製品は無視してよい

\(P_i - C_i \leq 0\) の製品は作れば作るほど損をする（または利益ゼロ）ので、最初から候補に入れる必要がありません。

アルゴリズム

個数制限なしナップサック問題を動的計画法（DP）で解きます。

\(dp[w]\) = 製造時間の合計がちょうど \(w\) 分以下のときに得られる最大利益

遷移式：各製品 \((T_i, profit_i)\) について、 $\(dp[w] = \max(dp[w],\ dp[w - T_i] + profit_i) \quad (w \geq T_i)\)$

通常の 0-1 ナップサックでは \(w\) を大きい方からループしますが、個数制限なしの場合は小さい方からループすることで、同じ製品を繰り返し選べるようになります。

具体例として、\(K = 10\), 製品A（時間3, 利益5）, 製品B（時間7, 利益11）の場合： - \(dp[3] = 5\)（A×1） - \(dp[6] = 10\)（A×2） - \(dp[7] = 15\)（A×3… ではなく確認）→ \(\max(dp[4]+11, dp[7]) = \max(5+11, 15) = 16\)? - 実際には \(dp[7] = \max(dp[7-3]+5, dp[7-7]+11) = \max(dp[4]+5, 11)\)

最終的に \(dp[K]\) が1台あたりの最大利益となり、答えは \(dp[K] \times M\) です。

計算量

• 時間計算量: \(O(N \times K)\)
  • 製品数 \(N \leq 500\)、容量 \(K \leq 200{,}000\) なので、最大 \(10^8\) 程度の計算
• 空間計算量: \(O(K)\)
  • DP配列のサイズ

\(M\) は最大 \(10^9\) と非常に大きいですが、1台分の最大利益を求めてから掛け算するだけなので、計算量には影響しません。

実装のポイント

• 利益が正の製品のみを候補に残すことで、無駄な計算を省く

• 個数制限なしナップサックでは、DP の内側ループを \(w = T_i\) から \(K\) まで昇順に回す（これにより同じアイテムを複数回使える）

• \(M\) が最大 \(10^9\)、1台あたりの利益が最大で約 \(2 \times 10^8\)（\(K/1 \times 10^6\)）程度になりうるため、答えは非常に大きくなる可能性がある。64ビット整数に収まることは保証されているが、Python では整数のオーバーフローを気にする必要がない

  ソースコード

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    items = []
    for i in range(N):
        C = int(input_data[idx]); idx += 1
        T = int(input_data[idx]); idx += 1
        P = int(input_data[idx]); idx += 1
        profit = P - C
        # Only consider items with positive profit
        if profit > 0:
            items.append((T, profit))
    
    # This is an unbounded knapsack problem for a single machine with capacity K
    # Then multiply by M machines
    
    # dp[w] = max profit achievable with exactly w minutes capacity
    # We want max over w <= K of dp[w]
    
    # Unbounded knapsack with capacity K
    # N <= 200, K <= 5000, so O(N*K) = O(1,000,000) which is fine
    
    dp = [0] * (K + 1)
    
    for t, p in items:
        for w in range(t, K + 1):
            if dp[w - t] + p > dp[w]:
                dp[w] = dp[w - t] + p
    
    # The best profit for one machine is max(dp[0..K])
    # Since dp is monotonically non-decreasing (we can always choose to not use extra time),
    # actually dp[K] should be the max, but let's be safe
    best_single = max(dp)
    
    print(best_single * M)

solve()

---

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