概要

整備後の標高列は、隣同士で必ず \(+1\) または \(-1\) だけ変化する列です。
現在の標高 \(H_i\) をそのまま残せるチェックポイントをなるべく多く選び、それらを通るような「上下に \(1\) ずつ動く道」が存在するかを考えます。

考察

チェックポイント \(i\) の標高 \(H_i\) を残すことを、「点 \((i, H_i)\) を通る」と考えます。

ある \(2\) つのチェックポイント \(i < j\) を両方残せる条件を考えます。
\(i\) から \(j\) までは \(j-i\) 回移動でき、各移動で標高は \(+1\) または \(-1\) 変わります。

したがって、\((i, H_i)\) から \((j, H_j)\) に到達できる条件は次の通りです。

• 必要な標高差が移動回数以内である
  \(|H_j - H_i| \le j - i\)
• パリティが合う
  \((H_j - H_i)\) と \((j-i)\) の偶奇が一致する

ここで、次の変数を定義します。

\(u_i = H_i + i\)

\(v_i = i - H_i\)

すると、\(i < j\) に対して

\(u_j - u_i = (H_j - H_i) + (j - i)\)

\(v_j - v_i = (j - i) - (H_j - H_i)\)

です。

よって、\(|H_j - H_i| \le j-i\) は

\(u_i \le u_j\) かつ \(v_i \le v_j\)

と言い換えられます。

また、パリティ条件は \(u_i\) の偶奇が同じであることに対応します。
実際、整備後の列では隣に進むたびに標高も \(1\) 変わるので、\(H'_i + i\) の偶奇は常に一定です。

つまり、残せるチェックポイントたちは

• \(u_i = H_i + i\) の偶奇がすべて同じ
• \(u_i\) が非減少
• \(v_i\) が非減少

となるように選ぶ必要があります。

これは、各偶奇ごとに「2次元の最長非減少列」を求める問題になります。

素朴にすべてのペアを見て DP すると \(O(N^2)\) かかり、\(N \le 2 \times 10^5\) では間に合いません。
そこで、\(u\) でソートした後、\(v\) について最長非減少部分列を求めます。

アルゴリズム

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

\(u = H_i + i\)

\(v = i - H_i\)

そして、\(u\) の偶奇ごとに点 \((u, v)\) を分けます。

各偶奇グループについて、次の処理を行います。

1. 点を \(u\) の昇順にソートする
   同じ \(u\) の場合は \(v\) の昇順に並ぶ
2. その順番で \(v\) の最長非減少部分列を求める
3. その長さが、その偶奇で残せる最大個数になる

最後に、偶数グループと奇数グループの答えの最大値を出力します。

最長非減少部分列は、通常の LIS と同様に dp 配列を使って求めます。

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

各 \(v\) に対して、dp の中で初めて \(v\) より大きい要素を upper_bound で探します。

• 見つからなければ末尾に追加
• 見つかればその位置を \(v\) で置き換える

非減少列なので、等しい値を続けて使ってよいです。
そのため lower_bound ではなく upper_bound を使います。

計算量

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

実装のポイント

• \(H_i\) は最大 \(10^9\) なので、\(u = H_i + i\) や \(v = i - H_i\) は long long で扱うと安全です。

• \(v\) は負になる可能性があります。

• 最長「非減少」部分列を求めるため、二分探索には upper_bound を使います。

• 整備後の列では \(H'_i + i\) の偶奇が一定なので、偶奇が異なる点を同時に残すことはできません。そのため、偶奇ごとに処理して最大値を取ります。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    array<vector<pair<ll, ll>>, 2> pts;

    for (int i = 1; i <= N; i++) {
        ll h;
        cin >> h;
        ll u = h + i;
        ll v = (ll)i - h;
        pts[u & 1].push_back({u, v});
    }

    auto solve = [](vector<pair<ll, ll>>& a) -> int {
        sort(a.begin(), a.end());

        vector<ll> dp;
        for (auto [u, v] : a) {
            auto it = upper_bound(dp.begin(), dp.end(), v);
            if (it == dp.end()) dp.push_back(v);
            else *it = v;
        }
        return (int)dp.size();
    };

    cout << max(solve(pts[0]), solve(pts[1])) << '\n';

    return 0;
}

---

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