概要

\(N\) 個の山頂から \(K\) 個以下を選び、標高が狭義単調増加かつ入山料の合計が予算 \(B\) 以下という条件のもとで、登頂数を最大化する問題です。「予算制約付きの最長狭義増加部分列（LIS）」を求める問題と言えます。

考察

素朴なアプローチ

まず思いつくのは、すべての部分列を列挙して条件を満たすものの中で最長のものを見つける方法ですが、部分列の数は最大 \(2^{500}\) 通りにもなり、到底間に合いません。

重要な気づき

この問題には以下の3つの軸があります：

1. 選んだ山の個数 \(k\)（\(K\) 以下）
2. 使った費用の合計 \(b\)（\(B\) 以下）
3. 最後に選んだ山の標高（次に選ぶ山は、これより大きい標高でなければならない）

通常のLIS問題では「個数を最大化」しますが、ここでは予算制約が加わっています。そこで、個数 \(k\) と費用 \(b\) を状態として持ち、「最後に選んだ山の標高」を最小化するDPを考えます。

なぜ「最後の標高を最小化」するのか？

最後に選んだ山の標高が小さいほど、今後選べる山の候補が多くなり、より多くの山頂に登頂できる可能性が高まります。つまり、同じ \((k, b)\) の状態であれば、最後の標高が小さい方が常に有利（または同等）です。

アルゴリズム

DP定義

\(dp[k][b]\) = ちょうど \(k\) 個の山を選び、入山料の合計がちょうど \(b\) 円であるような、標高が狭義単調増加な山頂列のうち、最後の山の標高の最小値。

• 初期値：\(dp[0][0] = -\infty\)（山を1つも選んでいない状態。番兵として \(-1\) などを使用）。それ以外は \(dp[k][b] = +\infty\)（達成不可能）。

遷移

山頂を \(i = 1, 2, \ldots, N\) の順に見ていきます。山頂 \(i\) のコスト \(C_i\)、標高 \(S_i\) に対して：

\[dp[k][b] = \min(dp[k][b],\ S_i) \quad \text{ただし } dp[k-1][b - C_i] < S_i\]

ここで、同じ山を2回使わないように、\(k\) を大きい方から小さい方へ、\(b\) を大きい方から小さい方へループします（0-1ナップサック型の逆順ループ）。

答え

\(dp[k][b] < +\infty\) となるような \((k, b)\)（\(b \leq B\)）の中で \(k\) の最大値が答えです。

具体例

例えば \(N=3, K=2, B=5\) で山頂が (コスト, 標高) = \((2, 100), (3, 200), (1, 150)\) の場合：

• 山1を選ぶ → \(dp[1][2] = 100\)
• 山2を選ぶ → \(dp[1][3] = 200\)、また \(dp[1][2]=100 < 200\) なので \(dp[2][5] = 200\)
• 山3を選ぶ → \(dp[1][1] = 150\)、また \(dp[1][2]=100 < 150\) なので \(dp[2][3] = 150\)

\(k=2\) が達成可能なので答えは \(2\) です。

計算量

• 時間計算量: \(O(N \times K \times B)\)
  \(N\) 個の山それぞれについて \(K \times B\) の表を更新するため。最大 \(500 \times 50 \times 500 = 12{,}500{,}000\) 回の処理。
• 空間計算量: \(O(K \times B)\)
  DP テーブルのサイズ。最大 \(50 \times 500 = 25{,}000\)。

実装のポイント

• 逆順ループ：0-1ナップサック問題と同様に、各山頂を1回しか使わないために \(k\) と \(b\) を大きい方から小さい方へループします。

• 番兵値：\(dp[0][0]\) の初期値として \(-1\)（または \(-\infty\) に相当する値）を使い、どの山の標高（\(\geq 1\)）よりも小さくしておくことで、最初の山を選ぶ遷移が自然に行えます。

• \(k\) の上限の工夫：\(k\) のループ上限を \(\min(K, i+1)\) とすることで、\(i+1\) 個の山しか見ていない段階で \(i+1\) 個より多く選ぶ無駄な計算を省けます。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    B = int(input_data[idx]); idx += 1
    
    C = []
    S = []
    for i in range(N):
        c = int(input_data[idx]); idx += 1
        s = int(input_data[idx]); idx += 1
        C.append(c)
        S.append(s)
    
    # dp[k][b] = minimum cost to select exactly k mountains with budget constraint,
    # where the last mountain's elevation is tracked.
    # Actually, let's think differently.
    
    # dp[k][b] = the minimum possible last elevation when we have selected exactly k mountains
    # using exactly cost b. But that's N*K*B states which is 500*50*500 = 12.5M, manageable.
    
    # Better approach: dp[k][b] = minimum last elevation achievable by selecting exactly k mountains
    # from the first i mountains considered so far, with total cost exactly b.
    # We iterate over mountains and update.
    
    # Actually, let's define:
    # dp[k][b] = minimum last elevation when selecting exactly k mountains with total cost b
    # Initialize dp[0][0] = -infinity (no mountain selected, any elevation is fine)
    # For each mountain i with cost C[i] and elevation S[i]:
    #   For k from K down to 1:
    #     For b from B down to C[i]:
    #       if dp[k-1][b-C[i]] < S[i]:
    #         dp[k][b] = min(dp[k][b], S[i])
    
    # Answer = max k such that any dp[k][b] for b <= B is finite.
    
    INF = float('inf')
    
    # dp[k][b] = minimum last elevation for exactly k selections with exactly cost b
    # We want to minimize last elevation to allow more future selections
    dp = [[INF] * (B + 1) for _ in range(K + 1)]
    dp[0][0] = -1  # sentinel: no mountain selected, last elevation is -infinity
    
    for i in range(N):
        ci = C[i]
        si = S[i]
        # Iterate in reverse to avoid using mountain i twice
        for k in range(min(K, i + 1), 0, -1):
            for b in range(B, ci - 1, -1):
                prev = dp[k - 1][b - ci]
                if prev < si:  # strict increase
                    if si < dp[k][b]:
                        dp[k][b] = si
    
    ans = 0
    for k in range(K + 1):
        for b in range(B + 1):
            if dp[k][b] < INF:
                ans = max(ans, k)
    
    print(ans)

main()

---

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