はまやんはまやんはまやん

hamayanhamayan's blog

Strictly Increasing Array [CSAcademy #61]

https://csacademy.com/contest/round-61/task/strictly-increasing-array/

N個の配列Vがある。
この配列に対して「ある要素の数を変更する」操作ができる。
配列全体が狭義単調増加列となるような操作の最小回数は?

解法

配列Vを配列Aとして説明する(ただの言い換え)。
 
これはLCSの発展問題として考える事ができる。
もし、配列全体を広義単調増加列にしたいのであれば、答えは「N-lcs長」となる。
LCSを抜き出して、それ以外のやつをそのLCSに合わせて変更するのが最適だからである。
参考
 
GeeksForGeeksで紹介されているコードを見てみよう

int minRemove(int arr[], int n)
{
    int LCS[n], len = 0;
 
    // Mark all elements of LCS as 1
    for (int i = 0; i < n; i++)
        LCS[i] = 1;
 
    // Find LCS of array
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j])
                LCS[i] = max(LCS[i], LCS[j] + 1);
        }
        len = max(len, LCS[i]);
    }
 
    // Return min changes for array
    // to strictly increasing
    return n - len;
}

ここで「arr[i]>arr[j]」という条件がある。
これを「arr[j] + j - i < arr[i]」と変えてみよう。
こうすると、「1 1 2」という列に対して「* 1 2」とは取れても「1 * 2」とは取れなくなる。
狭義単調増加列では間に最小限の数は敷き詰める必要があるので、距離を足して下駄をはかせる必要がある。
この条件を替えると「arr[i] - i<arr[j] - j」となる。
他の部分は特に変わらないため、今回の問題では、「A[i]-iとした配列についてのLCS」を考えればいいことになる。
よって、A[i] = A[i] - iとして、LCS長を計算。「N-LCS長」が答えである。
 
下の解法ではセグメントツリーを使ったLCSdpをしている。
st.update(i,v) := i番目をvに変更
st.get(L,R) := [L,R)の最大値
st[i] := i番目の要素

int N, A[101010];
int LCS[101010], len = 0;
SegTree<int, 1 << 17> st;
vector<int> za;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) A[i] -= i;
    rep(i, 0, N) za.push_back(A[i]);
    sort(za.begin(), za.end());
    za.erase(unique(za.begin(), za.end()), za.end());

    rep(i, 0, N) LCS[i] = 1;
    int a = lower_bound(za.begin(), za.end(), A[0]) - za.begin();
    st.update(a, LCS[0]);

    rep(i, 1, N) {
        int a = lower_bound(za.begin(), za.end(), A[i]) - za.begin();
        LCS[i] = st.get(0, a + 1) + 1;
        int b = st[a];
        st.update(a, max(b, LCS[i]));
        len = max(len, LCS[i]);
    }

    int ans = N - len;
    cout << ans << endl;
}