概要

\(N\) 個の作品から番号順を保ったまま部分列を選び、隣り合う作品の評価スコアの差が \(D\) 以下という条件のもとで、選べる作品数を最大化する問題です。条件付き最長部分列問題の一種です。

考察

問題の言い換え

作品を番号の小さい順に並べたまま部分列を選ぶので、これは最長部分列（subsequence）問題です。具体的には、数列 \(H_1, H_2, \ldots, H_N\) から部分列を選び、隣り合う要素の差の絶対値がすべて \(D\) 以下となる最長の部分列を求めます。

DP の定式化

\(\text{dp}[i]\) を「作品 \(i\) を最後に選んだときの、選べる作品数の最大値」と定義します。

遷移は以下の通りです：

\[\text{dp}[i] = \max\left(\{\text{dp}[j] \mid j < i,\ |H_j - H_i| \leq D\}\right) + 1\]

つまり、作品 \(i\) より前にあり、評価スコアが \([H_i - D,\ H_i + D]\) の範囲にある作品 \(j\) の中で、\(\text{dp}[j]\) が最大のものを見つけて \(+1\) すればよいです。

素朴なアプローチの問題点

すべての \(i\) について \(j < i\) のすべてを調べると \(O(N^2)\) かかり、\(N \leq 2 \times 10^5\) では TLE になります。

高速化のアイデア

遷移で必要なのは「\(H\) の値が \([H_i - D, H_i + D]\) の範囲にあるもののうち、\(\text{dp}\) 値の最大値」です。これは区間最大値クエリ（Range Max Query）に帰着できます。

\(H\) の値を座標圧縮してセグメント木の添字に対応させれば、各作品を左から順に処理しながら：

1. クエリ: \([H_i - D, H_i + D]\) に対応する圧縮後の区間で最大値を取得
2. 更新: \(H_i\) に対応する位置に \(\text{dp}[i]\) を書き込む

という操作を \(O(\log N)\) で行えます。

アルゴリズム

1. \(H\) の値を座標圧縮する（ソートして重複を除去し、各値に \(0, 1, 2, \ldots\) の添字を割り当てる）。
2. サイズ \(M\)（ユニークな値の個数）のセグメント木（区間最大値）を用意し、すべて \(0\) で初期化する。
3. \(i = 1, 2, \ldots, N\) の順に以下を行う：
   • 二分探索で \(H_i - D\) 以上の最小の圧縮添字 \(lo\) と、\(H_i + D\) 以下の最大の圧縮添字 \(hi\) を求める。
   • セグメント木で区間 \([lo, hi]\) の最大値 \(\text{best}\) を取得する。
   • \(\text{dp}_i = \text{best} + 1\) とする。
   • \(H_i\) の圧縮添字の位置にセグメント木上で \(\text{dp}_i\) を書き込む（既存値より大きければ更新）。
4. 全 \(i\) にわたる \(\text{dp}_i\) の最大値が答え。

具体例

\(N=5,\ D=3,\ H=[10, 8, 12, 5, 9]\) の場合：

• 作品1（\(H=10\)）: 範囲 \([7,13]\) に前の作品なし → \(\text{dp}=1\)
• 作品2（\(H=8\)）: 範囲 \([5,11]\) に \(H=10\)（dp=1）→ \(\text{dp}=2\)
• 作品3（\(H=12\)）: 範囲 \([9,15]\) に \(H=10\)（dp=1）→ \(\text{dp}=2\)
• 作品4（\(H=5\)）: 範囲 \([2,8]\) に \(H=8\)（dp=2）→ \(\text{dp}=3\)
• 作品5（\(H=9\)）: 範囲 \([6,12]\) に \(H=8\)（dp=2）,\(H=10\)（dp=1）,\(H=12\)（dp=2）→ \(\text{dp}=3\)

答えは \(3\) です。

計算量

• 時間計算量: \(O(N \log N)\)（座標圧縮のソートに \(O(N \log N)\)、各作品について二分探索とセグメント木操作に \(O(\log N)\)）
• 空間計算量: \(O(N)\)（セグメント木と座標圧縮用の配列）

実装のポイント

• 座標圧縮：\(H\) の値が最大 \(10^9\) と大きいため、そのまま配列の添字にはできません。ユニークな値だけを取り出して圧縮することでセグメント木のサイズを \(O(N)\) に抑えます。

• 二分探索で範囲を求める：bisect_left(sorted_unique, H[i] - D) と bisect_right(sorted_unique, H[i] + D) - 1 で、スコア範囲 \([H_i - D, H_i + D]\) に対応する圧縮添字の区間を正確に求められます。

• セグメント木の更新時の枝刈り：update 関数で親ノードの値が変わらなければ早期に打ち切ることで、定数倍を改善しています。

• \(lo > hi\) の場合：範囲内に該当する値がないケースでは、\(\text{best} = 0\) として \(\text{dp}_i = 1\)（その作品だけを選ぶ）とします。

  ソースコード

import sys
from sortedcontainers import SortedList

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    D = int(input_data[1])
    H = [int(input_data[i + 2]) for i in range(N)]
    
    # dp[i] = maximum number of artworks we can select ending with artwork i
    # For each i, we want max(dp[j]) + 1 where j < i and |H[j] - H[i]| <= D
    # This means H[i] - D <= H[j] <= H[i] + D
    
    # We need an efficient way to query max dp value for H values in range [H[i]-D, H[i]+D]
    # We can use a segment tree or balanced BST with coordinate compression
    
    # Coordinate compression
    sorted_unique = sorted(set(H))
    compress = {v: idx for idx, v in enumerate(sorted_unique)}
    M = len(sorted_unique)
    
    # Segment tree for range max query, point update
    seg = [0] * (2 * M)
    
    def update(pos, val):
        pos += M
        if seg[pos] >= val:
            return
        seg[pos] = val
        while pos > 1:
            pos >>= 1
            new_val = max(seg[2 * pos], seg[2 * pos + 1])
            if seg[pos] == new_val:
                break
            seg[pos] = new_val
    
    def query(l, r):
        # query max in [l, r]
        if l > r:
            return 0
        res = 0
        l += M
        r += M + 1
        while l < r:
            if l & 1:
                res = max(res, seg[l])
                l += 1
            if r & 1:
                r -= 1
                res = max(res, seg[r])
            l >>= 1
            r >>= 1
        return res
    
    import bisect
    
    ans = 0
    for i in range(N):
        h = H[i]
        # Find range of compressed indices where value is in [h-D, h+D]
        lo = bisect.bisect_left(sorted_unique, h - D)
        hi = bisect.bisect_right(sorted_unique, h + D) - 1
        
        if lo > hi:
            best = 0
        else:
            best = query(lo, hi)
        
        dp_i = best + 1
        ans = max(ans, dp_i)
        
        ci = compress[h]
        update(ci, dp_i)
    
    print(ans)

main()

---

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