概要

与えられた数列 \(H\) から、隣り合う要素の差の絶対値が \(1\) かつすべて非負整数という条件を満たすように変更した数列 \(H'\) を作るとき、元の値を維持できる要素数の最大値を求める問題です。

考察

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

隣り合う要素の差の絶対値がちょうど \(1\) であることから、インデックス \(i\) と標高 \(H'_i\) の偶奇（パリティ）には強い制約があります。 具体的には、\(H'_{i+1} = H'_i \pm 1\) なので、インデックスが \(1\) 増えるごとに標高の偶奇は必ず反転します。

したがって、すべての \(1 \le i \le N\) について、 $\(H'_i \equiv i + C \pmod 2\)\( となるような定数 \)C \in {0, 1}\( が必ず存在します。 元の標高を維持できる（変更しない）点 \)i\( については \)H’_i = H_i\( となるため、その点も \)H_i \equiv i + C \pmod 2$ を満たす必要があります。

このことから、\(C = 0\) の場合と \(C = 1\) の場合のそれぞれについて独立に問題を解き、その最大値を求めればよいことが分かります。

2. 変更しない点同士の条件

２つのインデックス \(i < j\) において、元の標高を維持する（\(H'_i = H_i, H'_j = H_j\) とする）ことができる条件を考えます。 隣り合う差の絶対値が \(1\) であることから、任意の \(i < j\) について、 $\(|H'_j - H'_i| \le j - i\)\( が成り立つ必要があります。逆に、この条件（およびパリティの条件）を満たす点の集合を選べば、その間を「差がちょうど \)1\(、かつ非負」となるように補間して数列 \)H’\( を構成することが常に可能です（元の標高 \)H_i\( が非負であるため、補間する過程で \)0$ 未満になることはありません）。

したがって、問題は以下の条件を満たすインデックスの集合 \(S\) の最大サイズを求めることに帰着されます。 - 任意の \(i, j \in S\) (\(i < j\)) について、 \(|H_j - H_i| \le j - i\) が成り立つ。

3. 条件の言い換え（2次元への帰着）

絶対値の不等式 \(|H_j - H_i| \le j - i\) は、絶対値を外すと以下の2つの不等式に分解できます。 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 H_i + i \le H_j + j\)

ここで、各チェックポイント \(i\) に対して、次のような2次元平面上の座標 \((x_i, y_i)\) を定義します。 - \(x_i = H_i + i\) - \(y_i = i - H_i\)

すると、先ほどの条件は以下のように非常にシンプルな形に言い換えることができます。 - 任意の \(i, j \in S\) (\(i < j\)) について、 \(x_i \le x_j\) かつ \(y_i \le y_j\) が成り立つ。

これは、2次元平面上の点 \((x_i, y_i)\) の集合から、右斜め上（または真上・真右）に並ぶ点をできるだけ多く選ぶ問題、すなわち「最長非減少部分列 (Longest Non-Decreasing Subsequence, LNDS)」を求める問題に帰着されます。

アルゴリズム

\(C \in \{0, 1\}\) のそれぞれについて、以下の手順で最大値を求めます。

1. 点の抽出: \(H_i \equiv i + C \pmod 2\) を満たす \(i\) について、座標 \((x_i, y_i) = (H_i + i, i - H_i)\) を計算し、配列 points に追加します。
2. ソート: points を \(x_i\) の昇順でソートします。\(x_i\) が等しい場合は、 \(y_i\) の昇順でソートします。
   • 注意: \(x_i = x_j\) のとき、\(y_i \le y_j\) も同時に満たすため、これらの点はすべて同時に選ぶことができます。そのため、\(y_i\) も昇順にソートしておくことで、LNDSの計算で同じ \(x\) 座標を持つ複数の点を正しくすべて選択できるようになります。
3. LNDSの計算: ソートされた点列の \(y\) 座標の配列に対して、最長非減少部分列 (LNDS) の長さを求めます。
   • 通常の LIS (最長増加部分列) と同様に、二分探索（C++では std::upper_bound）を用いた動的計画法 (DP) を使用することで、効率的に計算できます。

\(C = 0\) と \(C = 1\) の場合で求めた LNDS の長さの最大値が、最終的な答えとなります。

計算量

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

  • パリティの判定および座標の計算に \(O(N)\)。
  • 点のソートに \(O(N \log N)\)。
  • LNDS の計算（二分探索を用いた DP）に \(O(N \log N)\)。
  • これらを \(C=0, 1\) の2回行うため、全体の時間計算量は \(O(N \log N)\) となり、制約 \(N \le 2 \times 10^5\) に対して十分高速に動作します。

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

  • 点を格納する配列や DP テーブルのサイズは最大でも \(N\) であるため、空間計算量は \(O(N)\) です。

実装のポイント

• std::upper_bound の使用: 最長「非減少」部分列（同じ値の連続を許す）を求めるため、二分探索には std::lower_bound ではなく std::upper_bound を使用します。これにより、同じ \(y\) 座標を持つ点（＝元の数列で隣り合っていて、標高の差が \(1\) の関係にある点など）を重ねて選択することができます。

• オーバーフローの防止: \(H_i \le 10^9\) かつ \(N \le 2 \times 10^5\) であるため、座標 \(x_i = H_i + i\) は \(2^{31}-1\) を超えませんが、安全のために long long 型を使用して計算を行っています。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solve_for_C(int N, const vector<long long>& H, int C) {
    vector<pair<long long, long long>> points;
    for (int i = 1; i <= N; ++i) {
        if (H[i - 1] % 2 == (i - 1 + C) % 2) {
            long long x = H[i - 1] + i;
            long long y = i - H[i - 1];
            points.push_back({x, y});
        }
    }
    
    // Sort primarily by x, and secondarily by y
    sort(points.begin(), points.end());
    
    // Find the Longest Non-Decreasing Subsequence (LNDS) on y
    vector<long long> dp;
    for (const auto& p : points) {
        long long val = p.second;
        auto it = upper_bound(dp.begin(), dp.end(), val);
        if (it == dp.end()) {
            dp.push_back(val);
        } else {
            *it = val;
        }
    }
    return dp.size();
}

int main() {
    // Optimize standard I/O operations for performance
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    if (!(cin >> N)) return 0;
    
    vector<long long> H(N);
    for (int i = 0; i < N; ++i) {
        cin >> H[i];
    }
    
    int ans = max(solve_for_C(N, H, 0), solve_for_C(N, H, 1));
    cout << ans << "\n";
    
    return 0;
}

---

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