概要

乾燥耐性が閾値以上の植物は自動的に生存し、閾値未満の植物に対して予算内で給水設備を設置する 0-1ナップサック問題 を解く問題です。

考察

重要な気づき

植物は乾燥耐性 \(B_i\) と閾値 \(T\) の関係によって、2つのグループに分けられます：

1. 安全な植物 (\(B_i \geq T\)): 給水設備がなくても枯れない → 必ず生存する
2. 脆弱な植物 (\(B_i < T\)): 給水設備がないと枯れる → 設備を設置した場合のみ生存

安全な植物は何もしなくても生存するため、その観賞価値は無条件で得られます。

脆弱な植物については、「予算 \(M\) 以内で、どの植物に給水設備を設置すれば観賞価値の合計が最大になるか」という選択問題になります。

素朴なアプローチの問題点

脆弱な植物が \(K\) 個あるとき、全ての組み合わせを試すと \(2^K\) 通りになります。\(K\) が最大100の場合、\(2^{100}\) は天文学的な数になり、到底計算できません。

解決策

これは典型的な 0-1ナップサック問題 です。各脆弱な植物について「設置する/しない」の2択があり、コストの合計が予算 \(M\) 以内で、価値の合計を最大化します。動的計画法（DP）を使えば効率的に解けます。

アルゴリズム

ステップ1: 植物の分類

各植物を乾燥耐性で2グループに分けます。 - \(B_i \geq T\) なら安全 → 観賞価値を safe_value に加算 - \(B_i < T\) なら脆弱 → リスト vulnerable に追加

ステップ2: 0-1ナップサックDP

脆弱な植物に対して、以下のDPを行います：

• \(dp[j]\) = コスト \(j\) 以内で得られる最大価値

遷移式（植物 \((価値, コスト) = (v, c)\) を考慮するとき）： $\(dp[j] = \max(dp[j], dp[j - c] + v) \quad (j \geq c)\)$

重要: 各植物は1回しか選べないので、\(j\) を大きい方から小さい方へ更新します（逆順更新）。

具体例

\(M = 5\)、脆弱な植物が \((価値=10, コスト=3)\)、\((価値=7, コスト=2)\) の2つの場合：

初期状態: \(dp = [0, 0, 0, 0, 0, 0]\)

植物1 \((10, 3)\) 処理後: \(dp = [0, 0, 0, 10, 10, 10]\)

植物2 \((7, 2)\) 処理後: \(dp = [0, 0, 7, 10, 10, 17]\)

答えは \(dp[5] = 17\)（両方選択、コスト \(3+2=5\)）

ステップ3: 最終結果

\[\text{答え} = \text{safe\_value} + dp[M]\]

計算量

• 時間計算量: \(O(N \cdot M)\)
  • 各脆弱な植物（最大 \(N\) 個）に対して、コスト \(M\) までループ
• 空間計算量: \(O(M)\)
  • DPテーブルのサイズ

実装のポイント

• 逆順更新が必須: 0-1ナップサックでは、同じ植物を複数回選ばないために for j in range(M, cost - 1, -1) と逆順でループします。順方向だと同じ植物を何度も選んでしまう可能性があります。

• 1次元DPで十分: 逆順更新を使えば、2次元配列ではなく1次元配列で実装でき、空間効率が良くなります。

  ソースコード

def solve():
    N, M, T = map(int, input().split())
    
    plants = []
    for i in range(N):
        A, B, C = map(int, input().split())
        plants.append((A, B, C))
    
    # 植物を2つのグループに分ける
    # グループ1: 乾燥耐性 >= T (給水設備なしでも枯れない)
    # グループ2: 乾燥耐性 < T (給水設備がないと枯れる)
    
    safe_value = 0  # 給水設備なしでも生き残る植物の価値合計
    vulnerable = []  # 給水設備がないと枯れる植物のリスト (価値, コスト)
    
    for A, B, C in plants:
        if B >= T:
            # この植物は給水設備なしでも枯れない
            safe_value += A
        else:
            # この植物は給水設備がないと枯れる
            vulnerable.append((A, C))
    
    # vulnerable の植物に対してナップサック問題を解く
    # 予算 M 以内で選べる植物の価値の最大値を求める
    
    # dp[j] = コスト j 以内で得られる最大価値
    dp = [0] * (M + 1)
    
    for value, cost in vulnerable:
        # 逆順で更新（0-1ナップサック）
        for j in range(M, cost - 1, -1):
            dp[j] = max(dp[j], dp[j - cost] + value)
    
    # 最大値は safe_value + dp[M]
    print(safe_value + dp[M])

solve()

---

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