概要

この問題は、与えられた \(N\) 個の山から、「標高が単調増加」「費用の合計が \(B\) 以下」「個数が \(K\) 以下」という条件を満たしつつ、登頂する山の数を最大化する問題です。

典型的な「最長増加部分列（LIS）」の問題に、費用の制約と個数の制約が加わった形式になっています。

考察

基本的な考え方

まず、山の番号の順にしか進めないため、動的計画法（DP）が有効です。 単純な LIS であれば「\(dp[i] = \) 山 \(i\) を最後に選んだときの最大個数」としますが、今回は合計費用という制約があるため、費用を状態に含めるか、あるいは個数ごとに最小費用を管理する必要があります。

DPの状態定義

制約を見ると \(N \leq 500, K \leq 50, B \leq 500\) と、全体的に数値が小さめです。 そこで、以下のような DP を考えます。

• \(dp[k][i] = \) 山 \(i\) を最後に選び、合計 \(k\) 個の山に登ったときの最小の合計費用

もし、ある \(k\) について \(dp[k][i] \leq B\) となる \(i\) が一つでも存在すれば、\(k\) 個の山に登ることが可能であると判断できます。

遷移と高速化

\(dp[k][i]\) を求めるための遷移は以下のようになります。 - \(dp[k][i] = \min \{ dp[k-1][j] \mid j < i, S_j < S_i \} + C_i\)

このまま計算すると、各 \(k\) について \(O(N^2)\) かかり、全体で \(O(K \cdot N^2)\) となります。今回の制約（\(50 \times 500^2 = 1.25 \times 10^7\)）では Python だと少し工夫が必要な計算量です。

そこで、フェニック木（Binary Indexed Tree, BIT）を用いて高速化します。 標高 \(S_i\) を座標圧縮して \(1 \sim N\) の範囲に収めることで、「自分より標高が低い山の中での最小費用」を \(O(\log N)\) で取得できるようになります。これにより、全体の計算量を \(O(K \cdot N \log N)\) まで落とすことができます。

アルゴリズム

1. 座標圧縮: 標高 \(S_i\) は最大 \(10^9\) と大きいため、ソートして順位（\(1 \sim N\)）に変換します。これにより、BIT のインデックスとして利用可能になります。
2. 初期化: \(k=1\) の場合（1つだけ登る場合）の最小費用を計算します。\(C_i \leq B\) を満たす山 \(i\) について、\(dp[i] = C_i\) とします。
3. DPの更新（個数 \(k = 2\) から \(K\) まで）: 各 \(k\) について、以下の処理を行います。
   • BIT を初期化する。
   • 山 \(i = 1 \ldots N\) について順に：
     1. BIT から、標高が \(S_i\) 未満の範囲における「長さ \(k-1\) の最小費用」を取得する。
     2. （取得した費用 \(+ C_i\)）が予算 \(B\) 以下なら、それを \(dp\_next[i]\) とする。
     3. 前ステップの \(dp[i]\)（長さ \(k-1\) の費用）を BIT に追加する。
   • \(dp\_next\) に有効な値が一つもなければ、それ以上山を増やすことはできないため終了。
4. 答えの出力: 有効な値が存在した最大の \(k\) を出力します。

計算量

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

  • 座標圧縮に \(O(N \log N)\)
  • \(K\) 回のループの中で、各 \(N\) 個の要素に対して BIT の操作（\(O(\log N)\)）を行うため。
  • \(50 \times 500 \times \log_2(500) \approx 2.25 \times 10^5\) 程度の計算量となり、十分に高速です。

• 空間計算量: \(O(N)\)

  • DP テーブル（直前の \(k-1\) 分のみ保持する場合）と BIT のサイズに依存します。

実装のポイント

• BIT で最小値を扱う: 通常の BIT は「和」を求めますが、今回は「最小値」を管理するように実装します。初期値は無限大（inf）にしておきます。

• 更新とクエリのタイミング: 山 \(i\) の処理において、まずクエリ（\(j < i\) の探索）を行い、その後に更新（自分を BIT に入れる）を行うことで、「自分より手前にある山」のみを対象にできます。

• 早期終了: ある個数 \(k\) で予算内に収まる組み合わせが一つも作れなかった場合、それ以降の \(k+1, k+2 \ldots\) も作れないため、ループを抜けることで効率化できます。

  ソースコード

import sys

def solve():
    # Read all input data at once for faster processing
    try:
        data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not data:
        return
    
    # N: Number of mountains, K: Maximum climbing limit, B: Budget
    N = int(data[0])
    K = int(data[1])
    B = int(data[2])
    
    C = [] # Entry fees
    S = [] # Altitudes
    for i in range(N):
        C.append(int(data[3 + 2*i]))
        S.append(int(data[4 + 2*i]))
        
    # Coordinate compression for altitudes to map them to the range [1, N]
    # Since all S_i are distinct as per the constraints, we can simply sort and rank them.
    sorted_S = sorted(S)
    rank = {val: i + 1 for i, val in enumerate(sorted_S)}
    compressed_S = [rank[val] for val in S]
    
    # dp[i] will store the minimum cost to climb 'k' mountains ending with mountain 'i'.
    # We iterate through the possible sequence lengths k from 1 up to K.
    
    # Initial case: k = 1 (sequences of length 1)
    dp = [float('inf')] * N
    found_any = False
    for i in range(N):
        if C[i] <= B:
            dp[i] = C[i]
            found_any = True
    
    # If no single mountain can be climbed within the budget, the maximum m is 0.
    if not found_any:
        print(0)
        return
        
    max_m = 1
    
    # If the limit K is 1, the maximum possible length is already found.
    if K == 1:
        print(1)
        return

    # Iterate for each sequence length k from 2 up to K.
    for k in range(2, K + 1):
        dp_next = [float('inf')] * N
        # We use a Fenwick tree (BIT) to efficiently find the minimum cost
        # among mountains j < i that satisfy the altitude condition S[j] < S[i].
        bit = [float('inf')] * (N + 1)
        found_any_k = False
        
        for i in range(N):
            # Step 1: Query the BIT for the minimum cost of a sequence of length k-1
            # that ends at any mountain j < i with altitude S[j] < S[i].
            # The rank of S[i] is compressed_S[i], so we query the range [1, rank-1].
            res = float('inf')
            curr_q = compressed_S[i] - 1
            while curr_q > 0:
                if bit[curr_q] < res:
                    res = bit[curr_q]
                curr_q -= curr_q & (-curr_q)
            
            # Step 2: If such a sequence exists and adding mountain i is within budget:
            if res + C[i] <= B:
                dp_next[i] = res + C[i]
                found_any_k = True
            
            # Step 3: Update the BIT with the minimum cost to reach mountain i with length k-1.
            # This information will be available for mountains i' > i in this loop.
            val = dp[i]
            if val <= B:
                curr_u = compressed_S[i]
                while curr_u <= N:
                    if val < bit[curr_u]:
                        bit[curr_u] = val
                    curr_u += curr_u & (-curr_u)
        
        # If we successfully formed at least one valid sequence of length k:
        if found_any_k:
            max_m = k
            dp = dp_next
        else:
            # If no valid sequence of length k can be formed, no longer sequences are possible.
            break
            
    # Output the maximum number of mountains climbed.
    print(max_m)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。