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; }