概要

一列に並んだチェックポイントの標高を変更し、隣り合う標高の差がちょうど1かつ非負整数になるようにします。このとき、現在の標高のまま変更せずに残せるチェックポイントの個数の最大値を求める問題です。

考察

まず、条件「隣り合うチェックポイントの標高の差の絶対値がちょうど1」から分かることがあります。整備後の標高を \(H'_i\) とすると、\(H'_{i+1} = H'_i \pm 1\) となります。つまり、1つ隣に進むごとに標高は \(+1\) または \(-1\) されます。 ここで、\(H'_i + i\) の偶奇（パリティ）に注目すると、 \(H'_{i+1} + (i+1) = (H'_i \pm 1) + i + 1 = (H'_i + i) + (1 \pm 1)\) となります。\(1 \pm 1\) は \(0\) または \(2\) なので、\(H'_{i+1} + (i+1)\) と \(H'_i + i\) の偶奇は必ず一致します。 したがって、条件を満たす列において、\(H'_i + i\) の偶奇はすべての \(i\) で一致している必要があります。残すチェックポイントの標高 \(H_i\) も同様に、\(H_i + i\) の偶奇が全体で統一されていなければなりません。これにより、チェックポイントを \(y_i = i + H_i\) の偶奇で2つのグループに分けて独立に考えることができます。

次に、残すチェックポイントの条件を考えます。2つのチェックポイント \(i, j\) (\(i < j\)) をそのまま残すとします。間のチェックポイントの標高を1つ進むごとに \(\pm 1\) しか動けないため、\(i\) から \(j\) までの標高の差 \(|H_j - H_i|\) は、進むステップ数 \(j - i\) を超えることはできません。すなわち、 \(|H_j - H_i| \le j - i\) という条件が必要です。これを展開すると2つの不等式が得られます。 1. \(H_j - H_i \le j - i \Rightarrow i - H_i \le j - H_j\) 2. \(H_i - H_j \le j - i \Rightarrow i + H_i \le j + H_j\)

ここで、\(x_i = i - H_i\)、\(y_i = i + H_i\) とおくと、この条件は \(x_i \le x_j\) かつ \(y_i \le y_j\) と表せます。 これは、2次元平面上の点 \((x_i, y_i)\) に対して、\(x\) 座標と \(y\) 座標がともに広義単調増加になるような最長の部分列を見つける問題に帰着できます。

アルゴリズム

1. 各チェックポイント \(i\) (1-indexed) について、\(x_i = i - H_i\)、\(y_i = i + H_i\) を計算します。
2. \(y_i\) の偶奇（パリティ）に基づいて、2つのグループに分けます。
3. 各グループにおいて、\(x_i\) の昇順にソートします。\(x_i\) が同じ場合は \(y_i\) の昇順にソートします。
4. ソート後の各グループについて、\(y_i\) に関する最長増加部分列 (LIS) の長さを求めます。
5. 2つのグループで求めた LIS の長さの最大値が答えとなります。

計算量

• 時間計算量: ソートとLISの計算が \(O(N \log N)\) で行えるため、全体で \(O(N \log N)\) です。
• 空間計算量: 各チェックポイントの情報を保持するため、\(O(N)\) です。

実装のポイント

• \(x_i\) が同じ値を持つ複数の点について、それらは同時に残すことができます（間の標高を1ずつ増やす、あるいは減らすように設定すればよいためです）。

• LISを求める際、同じ \(x_i\) を持つ点を誤って複数選んだり、逆に選べなくなったりすることを防ぐため、ソートの第二キーを \(y_i\) の昇順にする必要があります。こうすることで、同じ \(x_i\) の点群が \(y_i\) について広義単調増加の順に並び、正しくLISの要素としてカウントされます。

• 提供コードはC++で記述されていますが、upper_boundを用いて狭義のLISを求めています。\(y_i = y_j\) なら必ず \(x_i = x_j\) となるため、\(y_i\) が等しい異なる点は存在せず、広義単調増加の条件を満たす列は自動的に狭義単調増加の条件も満たすことになります。

  ソースコード

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

using namespace std;

int solve_lis(const vector<pair<long long, long long>>& pts) {
    vector<long long> dp;
    for (const auto& p : pts) {
        long long y = p.second;
        auto it = upper_bound(dp.begin(), dp.end(), y);
        if (it == dp.end()) {
            dp.push_back(y);
        } else {
            *it = y;
        }
    }
    return dp.size();
}

int main() {
    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];
    }
    
    vector<pair<long long, long long>> odd_pts, even_pts;
    for (int i = 0; i < N; ++i) {
        long long x = (i + 1) - H[i];
        long long y = (i + 1) + H[i];
        if (y % 2 == 0) {
            even_pts.push_back({x, y});
        } else {
            odd_pts.push_back({x, y});
        }
    }
    
    auto cmp = [](const pair<long long, long long>& a, const pair<long long, long long>& b) {
        if (a.first != b.first) return a.first < b.first;
        return a.second < b.second;
    };
    
    sort(even_pts.begin(), even_pts.end(), cmp);
    sort(odd_pts.begin(), odd_pts.end(), cmp);
    
    int ans_even = solve_lis(even_pts);
    int ans_odd = solve_lis(odd_pts);
    
    cout << max(ans_even, ans_odd) << "\n";
    
    return 0;
}

この解説は or-glm5.2-high によって生成されました。