概要

この問題は、いくつかの制約（登頂数・標高の狭義単調増加・予算）を満たしながら、登頂する山の数を最大化する動的計画法の問題です。

考察

まず、この問題では以下の3つの条件があります： 1. 登頂する山の数は最大 \(K\) 個。 2. 登頂する山の標高は番号順に狭義単調増加であること。 3. 登頂する山の入山料の合計は \(B\) 円以下。

これらの条件をすべて満たしながら、登頂数 \(m\) を最大化することが目的です。

素朴なアプローチとその問題

最も素朴な方法は、全組み合わせを試すことですが、山の数 \(N\) が最大500あるため、現実的ではありません。また、山は番号順にしか進めないため、「すでに登頂した山より標高が低い山には登頂できない」という制約が重要になります。

この「標高が狭義単調増加」という点に注目すると、最後に登頂した山の標高を管理しておくことで、次の山に登頂できるかどうか判定できます。

解決策：動的計画法（DP）

そこで、以下のようなDPテーブルを考えます：

dp[k][b] := \(k\) 個の山に登頂し、合計コストが \(b\) 円以下であるような選び方の中で、最後に登頂した山の標高の最小値

• 「標高の最小値」を持つ理由は、より多くの山に登頂できる可能性を残すためです。
• 標高が低い山に登頂済みであれば、その後により高い山に登頂できる選択肢が広がります。

更新方法

各山 \(i\)（入山料 \(c\)、標高 \(s\)）に対して、次のようにDPテーブルを更新します：

• 既に \(k-1\) 個登頂し、コスト \(b - c\) で達成可能な状態があり、かつそのときの最後の標高が \(s\) より小さければ、新しい状態 \((k, b)\) でも標高 \(s\) で更新可能です。

ただし、同じ山を複数回選ばないようにするために、逆順（後ろから）に更新する必要があります。

アルゴリズム

1. DPテーブル dp[k][b] を初期化します。dp[0][0] = -1（標高が正のため）、それ以外は \(\infty\)。
2. 各山 \(i\) に対して：
   • 逆順で \(k = K\) から \(1\) まで、\(b = B\) から \(c\) までループ。
   • dp[k-1][b - c] < s ならば、dp[k][b] = min(dp[k][b], s) で更新。
3. 最終的に dp[k][b] != INF となる最大の \(k\) を答えとする。

計算量

• 時間計算量: \(O(N \cdot K \cdot B)\)
• 空間計算量: \(O(K \cdot B)\)

※ \(K \leq 50\), \(B \leq 500\) なので、十分高速に動作します。

実装のポイント

• DPテーブルの更新は必ず逆順に行うこと。これにより、同じ山を複数回使うのを防ぎます。

• dp[0][0] = -1 としておくことで、最初の山への遷移が簡単になります。

• 「最後に登頂した山の標高の最小値」を持つのがポイントで、これにより後の選択肢を広げることができます。

  ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1
    B = int(data[idx])
    idx += 1
    
    C = [0] * N
    S = [0] * N
    for i in range(N):
        C[i] = int(data[idx])
        idx += 1
        S[i] = int(data[idx])
        idx += 1

    # dp[i][k][b] = 最初のi個の山について、k個登頂し、コスト合計がb以下であるような
    #                最後に登頂した山の標高の最小値（不可能ならINF）
    INF = float('inf')
    # dpは3次元だが、KとBが小さいのでOK
    # dp[k][b] = 最後に登頂した山の標高の最小値（可能なら）、k個登頂、コストb
    dp = [[INF] * (B + 1) for _ in range(K + 1)]
    dp[0][0] = -1  # 標高が正なので-1で初期化

    for i in range(N):
        c = C[i]
        s = S[i]
        # 後ろから更新することで同じ山を複数回使わないようにする
        for k in range(K, 0, -1):
            for b in range(B, c - 1, -1):
                prev_b = b - c
                # 以前の状態でk-1個選んで、最後の標高がs未満なら遷移可能
                if dp[k-1][prev_b] < s:
                    if dp[k][b] > s:
                        dp[k][b] = s

        # k=0のときはコストだけ更新
        for b in range(B, c - 1, -1):
            if dp[0][b - c] < s:  # 実際にはk=0では標高の制約はないが、dp[0][*] = -1で十分
                pass
            # 実際にはdp[0][b]は常に-1で良いが、念のため更新しない

    # 最大のkを見つける
    max_k = 0
    for k in range(K + 1):
        for b in range(B + 1):
            if dp[k][b] != INF:
                max_k = max(max_k, k)
    print(max_k)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。