概要

高橋君が山を下るときに、標高が厳密に減少する順で休憩スポットを訪問し、得られる景観スコアの合計を最大化する問題。

考察

この問題では、以下の2つの制約があります：

1. 立ち寄る休憩スポットの標高はすべて現在地 \(X\) よりも厳密に低い必要がある。
2. 立ち寄る順番は、標高が厳密に減少する順でなければならない。

まず、条件1を満たさないスポット（\(A_i \geq X\)）は無視できます。

次に、残ったスポットを標高の昇順にソートします。こうすることで、左から右へ進むにつれて標高が高くなるように並び替えられ、後は「左から右に選んでいく中で、スコアの合計を最大化する増加部分列」を探す問題に変わります。

これは典型的な最長増加部分列（LIS）の亜種であり、「スコア和最大の増加部分列」を求める問題です。

ナイーブなDP（動的計画法）では、各要素ごとにそれより前のすべての要素を見て更新するため、計算量が \(O(N^2)\) となり、\(N\) が最大 \(2 \times 10^5\) なのでTLEになります。

そこで、BIT（Binary Indexed Tree）やセグメント木を使って高速化します。これにより、ある位置より前での最大スコアを効率的に取得・更新でき、全体で \(O(N \log N)\) にできます。

アルゴリズム

1. 条件 \(A_i < X\) を満たす休憩スポットのみを抽出し、標高の昇順にソートします。
2. 各休憩スポットに対応する標高を座標圧縮し、BIT上で管理できるようにします。
3. BITを用意し、各スポットについて以下を行います：
   • そのスポットより標高が低い中での最大スコアをBITから取得。
   • そのスコアに現在のスポットのスコアを足した値と、単体のスコアを比較して良い方を採用。
   • BITを更新。
4. 全体での最大スコアを記録しながら答えを求めます。

このアルゴリズムにより、標高が減少する順に訪れる制約を守りつつ、得られるスコアの和を最大化できます。

計算量

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

実装のポイント

• 標高の大小関係を保ちつつ、座標圧縮を行うことでBITのサイズを小さく保つ。

• BITの update と query は1-indexedで行う必要があることに注意。

• スポットのスコアが負の場合もあるため、初期値を \(-\infty\) として適切に扱う。

• 「その場所だけ選ぶ」場合と「前の続きに繋げる」場合の両方を比較して更新すること。

  ソースコード

import sys
from bisect import bisect_left, bisect_right
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    X = int(data[1])
    
    spots = []
    for i in range(N):
        a = int(data[2 + 2*i])
        b = int(data[2 + 2*i + 1])
        if a < X:
            spots.append((a, b))
    
    # 標高でソート
    spots.sort()
    
    # dp[i] := 標高が低い方からi番目までのスポットを使ってできる最大スコア
    # 実際に使うのは座標圧縮されたインデックスに対してのDP
    # しかし、この問題では、連続した部分列の中で降順になっているものを選ぶ必要がある
    # つまり、標高順にソートした後、部分列でスコアの和を最大化するような増加部分列（ただしスコアの和を最大化）
    # => 最長増加部分列(LIS)の変形：最大和LIS
    
    n = len(spots)
    if n == 0:
        print(0)
        return

    # 座標圧縮の準備（標高について）
    heights = [spot[0] for spot in spots]
    unique_heights = sorted(set(heights))
    k = len(unique_heights)
    
    # BIT or Segment Tree を使って効率的に処理する
    # dp[h] := 標高 h で終わる経路の最大スコア
    # ただし、h の範囲が大きいので、座標圧縮 + BIT で管理する
    
    class BITMax:
        def __init__(self, size):
            self.size = size
            self.tree = [-float('inf')] * (size + 1)
        
        def update(self, i, x):
            while i <= self.size:
                self.tree[i] = max(self.tree[i], x)
                i += i & -i
        
        def query(self, i):
            res = -float('inf')
            while i > 0:
                res = max(res, self.tree[i])
                i -= i & -i
            return res
    
    bit = BITMax(k)
    max_score = 0
    
    # スポットを標高順に処理（すでにソート済み）
    for a, b in spots:
        idx = bisect_left(unique_heights, a) + 1  # 1-indexed
        # idx よりも標高が低い中での最大値を取得
        prev_max = bit.query(idx - 1)
        current = max(b, prev_max + b)
        bit.update(idx, current)
        max_score = max(max_score, current)
    
    print(max_score)

if __name__ == "__main__":
    main()

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