概要

条件を満たす整備後の標高列は、隣り合う標高が必ず \(1\) ずつ変化する「山道」です。
元の標高のまま残すチェックポイントの集合を選び、その集合が同時に実現可能かを判定できる形に変換して、最大個数を求めます。

考察

まず、ある \(2\) つのチェックポイント \(i < j\) を両方そのまま残すことを考えます。
コードに合わせて、位置は \(0\) 始まりで考えます。

それぞれの標高を \(H_i, H_j\) とすると、\(i\) から \(j\) までの間には \(j-i\) 回の移動があります。
隣り合う標高差は必ず \(1\) なので、\(H_i\) から \(H_j\) へ \(j-i\) 歩で到達できるための条件は次の \(2\) つです。

1. 高さの差が歩数以下
   $\( |H_i - H_j| \le j-i \)$

2. パリティが合う
   \(j-i\) 回、\(\pm 1\) するので、高さの偶奇は毎回反転します。
   よって、 $\( (i + H_i) \bmod 2 = (j + H_j) \bmod 2 \)$

ここで、次のように変換します。

\[ x_i = i + H_i \]

\[ y_i = i - H_i \]

すると、条件 \(|H_i - H_j| \le j-i\) は次の \(2\) つに分解できます。

\[ H_i - H_j \le j-i \]

これは

\[ i + H_i \le j + H_j \]

つまり

\[ x_i \le x_j \]

です。

また、

\[ H_j - H_i \le j-i \]

これは

\[ i - H_i \le j - H_j \]

つまり

\[ y_i \le y_j \]

です。

したがって、同じパリティの点だけを見たとき、残せるチェックポイントは

\[ x_i \le x_j \]

かつ

\[ y_i \le y_j \]

を満たすような列、つまり \(2\) 次元上の単調増加列になります。

---

素朴に「どのチェックポイントを残すか」を全探索すると \(2^N\) 通りあり、当然間に合いません。
また、標高を状態にした DP も \(H_i \le 10^9\) なので不可能です。

そこで、各チェックポイントを \((x_i, y_i)\) に変換し、同じパリティごとに分けた上で、
「\(x\) 昇順に並べたときの \(y\) の最長非減少部分列」を求めればよいです。

ここで「非減少」であることが重要です。
\(y\) が等しい場合も条件 \(y_i \le y_j\) を満たすため、同時に残せます。

アルゴリズム

1. 各チェックポイント \(i\) について、以下を計算します。

$\( x = i + H_i \)$

$\( y = i - H_i \)$

1. \(x\) の偶奇、つまり \((i + H_i) \bmod 2\) ごとに \(2\) つのグループに分けます。

2. 各グループについて、点 \((x, y)\) を \(x\) 昇順にソートします。

3. ソート後の \(y\) 列に対して、最長非減少部分列、つまり LNDS を求めます。

Python では bisect_right を使うことで、非減少部分列を求められます。

   pos = bisect_right(tails, v)

tails[k] は「長さ \(k+1\) の非減少部分列の末尾としてあり得る最小の値」を表します。

1. 2 つのパリティグループそれぞれの LNDS 長の最大値が答えです。

計算量

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

実装のポイント

• 位置 \(i\) はコードでは enumerate(H) により \(0\) 始まりで扱っています。

• \((i + H_i) \bmod 2\) が異なるチェックポイント同士は同時に残せないので、必ずグループを分けます。

• 条件は \(y_i \le y_j\) なので、LIS ではなく LNDS です。
  そのため bisect_left ではなく bisect_right を使います。

• \(y = i - H_i\) は負になることがありますが、ソートや比較だけに使うので問題ありません。

  ソースコード

import sys
from bisect import bisect_right

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N = data[0]
    H = data[1:]

    groups = [[], []]
    for i, h in enumerate(H):
        groups[(i + h) & 1].append((i + h, i - h))

    ans = 0
    for g in groups:
        g.sort()
        tails = []
        for _, v in g:
            pos = bisect_right(tails, v)
            if pos == len(tails):
                tails.append(v)
            else:
                tails[pos] = v
        ans = max(ans, len(tails))

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。