【典型90問】060 - Chimera（★5）

atcoder.jp

LIS問題という有名問題を少し変えた問題です。

LIS問題について

最長増加部分列(LIS)問題は、昇順(または降順)となるような部分列は最長でいくつ作れるか？という問題です。
O(N²)のDPが最初に思いつきましたが、これでは間に合いません。

有名問題とのことで解法を調べてみたところ、O(NlogN)でDP+2分探索をする解法が主流のようです。
この解法を理解するのに役立つリソースをまとめます。

qiita.com

o-treetree.hatenablog.com

↓このリンクのGIF画像がとてもわかりやすいです。
https://alfedenzo.livejournal.com/170301.html

解法

LIS問題の解法を少し工夫して解きます。
今回の問題は昇順→降順のような部分列を取り出す必要があります。(昇順だけ、降順だけ、でもよい)
そこで、昇順から降順へと変わる境目(これを頂点と呼ぶことにする)をどこにするか全探索することを考えます。
ここで、昇順になる部分列をL、降順になる部分列をRとします。
数列を左からみたときの降順は右から見たときの昇順と同じになるため、左から見たときLの長さを、右から見たときRの長さをそれぞれ計算することができます。
この方法で、頂点を$A_i$にしたときのLとRの長さを計算しておきます。
そして、頂点を全探索してmax(Lの長さ+Rの長さ-1)が答えになります。

実装

void solve(long long N, std::vector<long long> A) {
    vector<int> dpL(N+1, INF), dpR(N+1, INF);
    // l[i]: iを頂点としたときのLの長さ, r[i]: iを頂点としたときのRの長さ
    vector<int> l(N+1, 1), r(N+1, 1); 
    // 部分列の長さが0の時、最小値を0としておく
    dpL[0] = 0; dpR[0] = 0;
    dpL[1] = A[0]; dpR[1] = A[N-1];
    // 現在の最大の部分列の長さ
    int endL = 1, endR = 1;

    for (int i = 1; i < N; i++) {
        if (dpL[endL] < A[i]) {
            endL++;
            dpL[endL] = A[i];
            l[i] = endL;
        } else {
            // 二分探索
            // A[i]より小さい要素数を計算している
            // lower_boundはA[i]以上で最小のイテレータを返す
            auto iter = lower_bound(all(dpL), A[i]) - dpL.begin();
            dpL[iter] = A[i];
            // どこの要素を入れ替えたか、がそこを頂点としたときの部分列の最大の長さになる
            l[i] = iter;
        }

        if (dpR[endR] < A[N-1-i]) {
            endR++;
            dpR[endR] = A[N-1-i];
            r[N-1-i] = endR;
        } else {
            auto iter = lower_bound(all(dpR), A[N-1-i]) - dpR.begin();
            dpR[iter] = A[N-1-i];
            r[N-1-i] = iter;
        }
    }

    // 集計
    int ans = 0;
    REP (i, N) {
        chmax(ans, l[i]+r[i]-1);
    }
    c(ans)

}