けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 360 G - Suitable Edit for LIS (3D, 青色, 625 点)

NoviSteps3D 左右からそれぞれ走査する 累積和テク:左右両端からの累積和や累積結果を前処理 DP状態:フェーズ(耳DP) N個のものうち1個を変更・削除したものを解く LIS DP 数列 そのまま覚えたいシンプル設定の中堅以上の典型問題 操作 最適化問題 最大スコア 操作:上書き 操作:値の更新 ある値を固定して考える Greedy Greedy:どちらも可なら厳しい方 テク:「最大値がK以上」⇔「K以上が存在」 最適化テク:操作の流れを単純化する 最適化テク:探索候補を絞る 最適化テク：変形しても悪化しない 個人的要復習

すごく面白い問題！　いろんな嘘解法がありそうで怖い。

問題概要

長さ N の数列 A_{0}, A_{1}, \dots, A_{N-1} が与えられる。今、数列の 1 つの要素の値を自在に書き換えることができる。

操作後の数列の LIS の長さを求めよ。

制約

  • 1 \le N \le 2 \times 10^{5}
  • 1 \le A_{i} \le 10^{9}

考えたこと

この手の問題では、まずは操作を何もしない場合の最適解を考えることが有効な印象がある。ここでも、何も操作しないで LIS を求めたとしよう。

このとき、ある LIS として A_{l_{0}}, A_{l_{1}}, \dots, A_{l_{K-1}} が存在して、

  • l_{k+1} - l_{k} \ge 2
  • A_{l_{k+1}} - A_{l_{k}} \ge 2

を満たすような k が存在すれば、操作によって LIS を 1 増加させることができる。具体的には、 A_{l_{k} + 1} の値を A_{l_{k}} + 1 に書き換えればよい。(なお、ここで、適宜番兵を用意することで、 l_{0} \ge 1 の場合に A_{0} の値を 0 などにすればよいという場合も含めて考えることにする)。

逆に、このような組 (LIS, k) が存在しない場合には、どのように操作しても LIS は増加しない。

以上の考察から、次のことが言える。

操作を次のいずれかのものに限ってもよい。

  • A_{0} の値を 0 にする
  • A_{i} の値を A_{i-1} + 1 にする ( i \gt 0 のとき)

以降、操作する添字 i を固定して、その操作された要素 A_{i} を含むような LIS を考えよう。

操作する添字 i を固定する

まず、数列の先頭から LIS DP を回していくことで、次の値 l_{0}, l_{1}, \dots, l_{N-1} を前処理で求めよう。

l_{i} ← A_{i} の値を上述の通りに操作ときの、末尾を A[i] (操作後) とする LIS の長さ

そして、再び数列の末尾から LIS DP を回していくことで、 A_{i} (操作後) を含むような LIS の長さが求められる。

具体的には、各 i = N-1, N-2, \dots, 0 についての次の値の最大値を求めればよい。

( A_{i} (操作後) を先頭とする LIS の長さ - 1) + l_{i}

以上の解法の計算量は O(N \log N) となる。

コード

#include <bits/stdc++.h>
using namespace std;
const int INF = 1<<30;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    
    // left[i] := A[i] を A[i-1]+1 にしたときの、末尾を A[i] とする LIS の長さ
    vector<int> dp(N+1, INF), left(N);
    for (int i = 0; i < N; ++i) {
        int v = (i > 0 ? A[i-1] + 1 : 0);
        int len = lower_bound(dp.begin(), dp.end(), v) - dp.begin();
        left[i] = len + 1;
        len = lower_bound(dp.begin(), dp.end(), A[i]) - dp.begin();
        dp[len] = A[i];
    }
    
    int res = lower_bound(dp.begin(), dp.end(), INF) - dp.begin();  // 通常の LIS
    
    // 右からもう一度やる
    dp.assign(N+1, INF);
    for (int i = N-1; i >= 0; --i) {
        int v = (i > 0 ? A[i-1] + 1 : 0);
        int len = lower_bound(dp.begin(), dp.end(), -v) - dp.begin();
        res = max(res, len + left[i]);
        len = lower_bound(dp.begin(), dp.end(), -A[i]) - dp.begin();
        dp[len] = -A[i];
    }
    cout << res << endl;
}