概要

この問題は、与えられた数列 \(H\) から、隣り合う要素の差の絶対値がちょうど \(1\) で、かつすべての要素が非負整数であるという条件を満たすように変更した数列 \(H'\) を作るとき、元の値をそのまま残せる（\(H_i = H'_i\) となる）要素の最大個数を求める問題です。

条件を数式で整理することで、この問題は最長増加部分列（LIS: Longest Increasing Subsequence）の形に帰着でき、効率的に解くことができます。

---

考察

1. 2つのチェックポイントをそのまま残せる条件

ある \(2\) つのチェックポイント \(i, j\)（ただし \(i < j\)）の標高 \(H_i, H_j\) を変更せずにそのまま残せる条件を考えます。

隣り合うチェックポイントの標高差がちょうど \(1\) であるため、位置が \(1\) 進むごとに標高は最大でも \(1\) しか変化できません。したがって、位置 \(i\) から \(j\) まで移動する間に、標高の変化量はインデックスの差 \(j - i\) 以下である必要があります。 すなわち、以下の不等式が成り立たなければなりません。

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

この絶対値を外して整理します。

1. \(H_j - H_i \le j - i \iff i - H_i \le j - H_j\)
2. \(-(H_j - H_i) \le j - i \iff i + H_i \le j + H_j\)

ここで、各 \(i\) に対して以下の \(2\) つの値を定義します。 - \(x_i = i - H_i\) - \(y_i = i + H_i\)

すると、元の標高を残せるための条件は、\(i < j\) において \(x_i \le x_j\) かつ \(y_i \le y_j\) が成り立つことと言い換えることができます。

2. パリティ（偶奇）の条件

さらに、隣り合う標高の差が「ちょうど \(1\)」であることから、標高の偶奇は \(1\) つ進むごとに必ず反転します。 これは、すべての \(i\) について \(i + H'_i\) の偶奇（パリティ）が一致していなければならないことを意味します。

したがって、元の標高を残すチェックポイント同士は、すべて \(i - H_i\)（または \(i + H_i\)）の偶奇が一致している必要があります。

3. 問題の帰着

以上の考察から、問題を以下のように分解できます。

1. 各チェックポイントを \(x_i = i - H_i\) の偶奇によって 偶数グループ と 奇数グループ の \(2\) つに分類する。
2. それぞれのグループにおいて、条件「\(i < j\) のとき \(x_i \le x_j\) かつ \(y_i \le y_j\)」を満たすように、残せるチェックポイントの最大数を求める。
3. \(2\) つのグループのうち、最大値が大きい方を答えとする。

グループ内では、まず要素を \(x_i\) の昇順でソートします（\(x_i\) が同じ場合は \(y_i\) の昇順）。 ソートした状態で、 \(y_i\) の値が減少せずに増加していく部分列、すなわち広義最長増加部分列（広義LIS）の長さを求めれば、それがそのグループで残せる最大個数になります。

※なお、標高が非負整数（\(H'_i \ge 0\)）でなければならないという条件は、パリティが一致し、上記の条件を満たすように繋ぐ過程で、標高が \(0\) 未満になる前に \(0\) と \(1\) を往復させることで常に達成可能です。

---

アルゴリズム

1. 初期化とグループ分け 各 \(i = 1, 2, \ldots, N\) について、 \(x_i = i - H_i\) と \(y_i = i + H_i\) を計算します。 \(x_i\) の偶奇に応じて、座標のペア \((x_i, y_i)\) を g0（偶数）と g1（奇数）のリストに振り分けます。

2. ソート g0 と g1 をそれぞれ昇順にソートします。これにより、自動的に \(x_i\) の昇順（同じ場合は \(y_i\) の昇順）に並びます。

3. 最長増加部分列（LIS）の計算 ソートされた各グループから \(y_i\) のみを抽出した配列に対し、二分探索を用いた高速な LIS アルゴリズムを適用します。 今回は「広義単調増加（等号を許す）」のため、二分探索には bisect_right を使用します。

4. 答えの出力 g0 から得られた LIS の長さと、g1 から得られた LIS の長さの最大値を出力します。

---

計算量

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

  • グループ分けに \(O(N)\)
  • ソートに \(O(N \log N)\)
  • 二分探索を用いた LIS の計算に \(O(N \log N)\)
  • 全体として \(O(N \log N)\) となり、 \(N \le 2 \times 10^5\) に対して十分高速に動作します。

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

  • 各グループの配列や LIS 計算用の DP 配列を保持するために、 \(O(N)\) のメモリを使用します。

---

実装のポイント

• 1-indexed への変換 問題文のチェックポイントは \(1\) から \(N\) までなので、実装時に \(i\) 番目の要素のインデックスを i + 1 として扱う必要があります。

• 広義単調増加の処理 通常の LIS（厳密に増加）では二分探索に bisect_left を使いますが、今回は \(y_i\) が同じ値であっても両方残すことができる（\(x_i\) が異なるため）ので、等号を許す広義単調増加にするために bisect_right を使用します。

  ソースコード

import sys
from bisect import bisect_right

def solve_lis(arr):
    dp = []
    for x in arr:
        idx = bisect_right(dp, x)
        if idx == len(dp):
            dp.append(x)
        else:
            dp[idx] = x
    return len(dp)

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    H = [int(x) for x in data[1:]]
    
    g0 = []
    g1 = []
    
    for i in range(N):
        h = H[i]
        idx = i + 1
        x = idx - h
        y = idx + h
        if x % 2 == 0:
            g0.append((x, y))
        else:
            g1.append((x, y))
            
    g0.sort()
    g1.sort()
    
    y0 = [p[1] for p in g0]
    y1 = [p[1] for p in g1]
    
    ans0 = solve_lis(y0)
    ans1 = solve_lis(y1)
    
    print(max(ans0, ans1))

if __name__ == '__main__':
    main()

---

この解説は gemini-3.5-flash-high によって生成されました。