概要

標高 \(X\) より低い休憩スポットの中から、景観スコアが正のものをすべて選ぶことで、スコアの合計を最大化する問題です。

考察

重要な気づき：「厳密に減少する順に訪問」という制約は実質的に制約にならない

一見すると、「標高が厳密に減少する順に立ち寄らなければならない」という条件が難しそうに見えます。これは最長増加部分列 (LIS) のような動的計画法が必要な問題に見えるかもしれません。

しかし、ここで重要な観察があります：

\(A_i\) はすべて異なる

つまり、どのスポットの部分集合を選んでも、それらを標高の高い順に並べれば必ず厳密に減少する列になります。

具体例で確認

例えば、標高が \(\{100, 300, 200\}\) の3つのスポットがあったとします。この3つすべてを選んだ場合、標高の高い順に \(300 \to 200 \to 100\) と訪問すれば、厳密に減少する条件を満たします。

つまり、どの部分集合を選んでも、適切な順番で訪問すれば条件を満たせるのです。

問題の本質

条件を整理すると：

1. \(A_i < X\) を満たすスポットだけが候補
2. 候補の中から好きな部分集合を選べる（順番の制約は上述の通り自動的に満たせる）
3. 選んだスポットの \(B_i\) の合計を最大化したい

これは非常にシンプルな問題に帰着されます：

\(A_i < X\) を満たすスポットのうち、\(B_i > 0\) であるものをすべて選ぶ

\(B_i > 0\) のスポットは選べば得するので選び、\(B_i \leq 0\) のスポットは選んでも損するか変わらないので選ばない、というのが最適戦略です。どのスポットにも立ち寄らない場合のスコアは \(0\) なので、正のスコアのものだけを選べばよいです。

アルゴリズム

1. 各スポットについて、\(A_i < X\) かどうかを確認する（標高の条件フィルタ）
2. 条件を満たすスポットの中で、\(B_i > 0\) であるものの \(B_i\) をすべて合計する
3. その合計値を出力する（該当するスポットがなければ \(0\)）

計算量

• 時間計算量: \(O(N)\) — 全スポットを1回走査するだけ
• 空間計算量: \(O(N)\) — 入力の読み込み分（フィルタ後のリストを保持する場合）。合計値だけ求めるなら \(O(1)\) の追加メモリで可能

実装のポイント

• \(A_i < X\) の「厳密に低い」条件を忘れない: \(A_i = X\) のスポットは選べません。不等号が < であって <= でないことに注意。

• \(B_i\) が負の値を取りうる点: 景観スコアが負のスポットを選ぶと損をするので、正のものだけを選びます。

• 0箇所選ぶ場合もある: すべてのスポットの \(B_i\) が負、またはすべて \(A_i \geq X\) の場合、答えは \(0\) です。

• 高速な入力: \(N\) が最大 \(2 \times 10^5\) と大きいため、Python では sys.stdin.buffer.read() を用いた一括読み込みが有効です。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    X = int(input_data[idx]); idx += 1
    
    spots = []
    for i in range(N):
        a = int(input_data[idx]); idx += 1
        b = int(input_data[idx]); idx += 1
        if a < X:
            spots.append((a, b))
    
    # We need to select a subset of spots with strictly decreasing altitudes
    # and maximize the sum of B values.
    # Since altitudes are all distinct and we need strictly decreasing order,
    # the order is determined by sorting. We can pick any subset of spots
    # (sorted by decreasing altitude) and the constraint is automatically satisfied.
    # 
    # So the problem reduces to: pick a subset of the filtered spots to maximize
    # sum of B_i. This is simply the sum of all positive B_i values.
    
    result = 0
    for a, b in spots:
        if b > 0:
            result += b
    
    print(result)

main()

---

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