概要

この問題は、番号順に並べたときに隣り合う作品の評価スコアの差が \(D\) 以下になるような最長の部分列の長さを求める問題です。

考察

素朴なアプローチとしては、各作品について、それ以前の作品の中で条件を満たすものから最大の連鎖長を見つける動的計画法（DP）が考えられます。しかし、この方法では各作品に対して \(O(N)\) の計算が必要になるため、全体で \(O(N^2)\) の計算量となり、\(N\) が最大 \(2 \times 10^5\) の制約では時間がかかりすぎます。

効率的に解くためには、DPの更新を高速化する必要があります。具体的には、各作品 \(i\) について、評価スコアが \([H_i - D, H_i + D]\) の範囲にある作品の中で最大のDP値を見つける操作を高速に行う必要があります。このような範囲最大値クエリは、セグメント木やFenwick木などのデータ構造を用いることで効率的に処理できます。

アルゴリズム

1. 動的計画法（DP）の設定:

   • \(dp[i]\) を、作品 \(i\) を最後に選んだときの最長部分列の長さと定義します。
   • 各作品 \(i\) について、\(dp[i] = \max\{dp[j] + 1 \mid j < i, |H_j - H_i| \leq D\}\) と更新します。

2. 高速化のためのデータ構造:

   • 評価スコアの値域が広いため、まず座標圧縮を行います。
   • セグメント木を構築し、評価スコアの値に対応するインデックスにDP値を保持します。
   • 各作品 \(i\) について、評価スコアの範囲 \([H_i - D, H_i + D]\) に対応する圧縮後のインデックス範囲を二分探索で求め、セグメント木からその範囲の最大DP値を取得します。

3. 処理の流れ:

   • 評価スコアのリストを座標圧縮します。
   • セグメント木を初期化します。
   • 作品を前から順に処理します:
     • 現在の作品の評価スコア \(H_i\) から許容範囲 \([H_i - D, H_i + D]\) を計算します。
     • 二分探索でこの範囲に対応する圧縮後のインデックス範囲 \([l, r]\) を求めます。
     • セグメント木から範囲 \([l, r]\) の最大DP値を取得し、\(dp[i] = \text{最大値} + 1\) とします。
     • セグメント木の現在の評価スコアに対応する位置を \(dp[i]\) で更新します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 座標圧縮: \(O(N \log N)\)
  • 各作品の処理: 二分探索とセグメント木のクエリ/更新がそれぞれ \(O(\log N)\)
• 空間計算量: \(O(N)\)
  • セグメント木: \(O(N)\)
  • DP配列と圧縮用配列: \(O(N)\)

実装のポイント

• 座標圧縮を行うことで、セグメント木のサイズを \(O(N)\) に抑えています。

• セグメント木は範囲最大値クエリと一点更新をサポートするように実装します。

• 二分探索では、許容範囲の下限以上の最小インデックスと上限以下の最大インデックスを正しく求める必要があります。

• セグメント木の更新時には、現在の値より大きい場合のみ更新するようにします（最大値の維持）。

  ソースコード

import sys

class SegmentTree:
    def __init__(self, n):
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.data = [0] * (2 * self.size)
    
    def update(self, index, value):
        i = index + self.size
        self.data[i] = value
        while i > 1:
            i //= 2
            self.data[i] = max(self.data[2*i], self.data[2*i+1])
    
    def query(self, l, r):
        l += self.size
        r += self.size
        res = 0
        while l < r:
            if l % 2 == 1:
                res = max(res, self.data[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = max(res, self.data[r])
            l //= 2
            r //= 2
        return res

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    n = int(data[0])
    D = int(data[1])
    H = list(map(int, data[2:2+n]))
    
    # 座標圧縮
    sorted_H = sorted(set(H))
    comp_map = {}
    for idx, val in enumerate(sorted_H):
        comp_map[val] = idx
    comp_size = len(sorted_H)
    
    seg_tree = SegmentTree(comp_size)
    dp = [0] * n
    ans = 0
    
    for i in range(n):
        h_val = H[i]
        comp_idx = comp_map[h_val]
        low_val = h_val - D
        high_val = h_val + D
        
        # 二分探索で範囲の境界を求める
        left = 0
        right = comp_size
        # low_val以上の最小のインデックス
        l_idx = comp_size
        low = 0
        high = comp_size - 1
        while low <= high:
            mid = (low + high) // 2
            if sorted_H[mid] >= low_val:
                l_idx = mid
                high = mid - 1
            else:
                low = mid + 1
                
        # high_val以下の最大のインデックス
        r_idx = -1
        low = 0
        high = comp_size - 1
        while low <= high:
            mid = (low + high) // 2
            if sorted_H[mid] <= high_val:
                r_idx = mid
                low = mid + 1
            else:
                high = mid - 1
        
        max_val = 0
        if l_idx <= r_idx:
            max_val = seg_tree.query(l_idx, r_idx+1)
        
        dp[i] = max_val + 1
        if dp[i] > ans:
            ans = dp[i]
            
        # 現在のdp値でセグメント木を更新
        current_max = seg_tree.query(comp_idx, comp_idx+1)
        if dp[i] > current_max:
            seg_tree.update(comp_idx, dp[i])
            
    print(ans)

if __name__ == "__main__":
    main()

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