概要

この問題は、所持金と登頂数の制限下で、標高が単調増加になるように山頂を選び、登頂数を最大化する問題です。

考察

問題の条件は以下の3つです： 1. 登頂数はK個以下 2. 登頂する山頂の標高は番号順に狭義単調増加 3. 入山料の合計がB円以下

単純に全探索すると、各山頂について登頂する/しないの2択があるため\(O(2^N)\)となり、N=500では計算不可能です。動的計画法を用いることで効率的に解く必要があります。

重要な観察は、標高の単調増加条件を満たすためには、次に選ぶ山頂の標高が直前の山頂の標高より大きくなければならないという点です。この性質を利用して、状態を「選んだ山頂数」「合計コスト」「最後に選んだ山頂の標高」で管理したいですが、標高の値が大きい（最大\(10^9\)）ため直接状態に持てません。

代わりに、「最後に選んだ山頂の標高」を最小化するように状態を設計します。同じ選び方でも最後の標高が小さい方が、次に選べる山頂の選択肢が広がるため、より良い状態と言えます。

アルゴリズム

動的計画法を用いて解きます。DPテーブルを以下のように定義します： - \(dp[j][b]\): ちょうどj個の山頂を選び、合計コストがbであるときの「最後に選んだ山頂の標高」の最小値

初期状態は、0個選んだ状態で\(dp[0][0] = 0\)とします（実際の標高は正の値なので、0より小さい山は存在しないため）。

各山頂i（コスト\(c_i\)、標高\(s_i\)）について、以下の更新を行います： - 現在j個選んで合計コストbの状態で、最後の標高\(dp[j][b] < s_i\)（標高が単調増加）ならば - j+1個選んで合計コストb+c_iの状態を\(s_i\)で更新可能 - ただし、既存の値より小さい場合のみ更新（最小化するため）

この更新を山頂1からNまで順番に行い、最終的に\(dp[j][b] \leq B\)（\(b \leq B\)）となる最大のjを見つけます。

計算量

• 時間計算量: \(O(N \times K \times B)\)
  • 山頂数N、最大選び数K、最大予算Bの3重ループ
  • N=500, K=50, B=500なので、500×50×500=12,500,000回の操作で十分高速
• 空間計算量: \(O(K \times B)\)
  • DPテーブルのサイズは(K+1)×(B+1)

実装のポイント

1. DPテーブルの初期化: 十分大きい値（INF）で初期化し、\(dp[0][0] = 0\)のみ初期状態

2. 後ろから更新: 同じ山頂を重複して数えないように、jのループは後ろから（K-1→0）回す

3. コストのループも後ろから回す: 同じ山頂のコストを重複して加算しないため

4. 答えの探索: 最終的にDPテーブルを走査し、有効な状態の中で最大のjを探す

   ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    it = iter(data)
    N = int(next(it)); K = int(next(it)); B = int(next(it))
    costs = []
    heights = []
    for i in range(N):
        c = int(next(it)); s = int(next(it))
        costs.append(c)
        heights.append(s)
    
    # dp[j][b]: 合計j個選び、合計コストがbであるときの最後の標高の最小値（より小さい方が良い）
    INF = 10**18
    dp = [[INF] * (B+1) for _ in range(K+1)]
    dp[0][0] = 0   # 0個選んだとき、コスト0、最後の標高は0（実際の標高は正なので0より小さい山はない）
    
    ans = 0
    for i in range(N):
        c = costs[i]
        s = heights[i]
        # 後ろから更新（同じ山を2回使わないように）
        for j in range(K-1, -1, -1):
            for b in range(B - c, -1, -1):
                if dp[j][b] < s:
                    if dp[j+1][b+c] > s:
                        dp[j+1][b+c] = s
        # 直接更新しないで、ループの後で確認する
    
    # 答えを探す: jが最大で、b<=Bのもの
    for j in range(K, -1, -1):
        for b in range(B+1):
            if dp[j][b] < INF:
                if j > ans:
                    ans = j
    print(ans)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。