選択する数字に制限のあるLISを求めます。以下のLISは厳密な増加のみを考えます。
LISの代表的な求め方として
- 1: $A[i]$ = 長さiのLISの中で末尾の最小値 をもって二分探索
- 2: $B[i]$ = 末尾の値がiであるLISの長さ をもって区間Maxクエリ、1点更新
の2つがあります。ここでは"2"のアプローチをとります。
題材: 隣り合う項の差がk以内のLIS
例えば以下のようなLISを求められます。
- 各要素の差が$k$以内であるようなLIS
例1: nums = $[4,2,1,4,3,4,5,8,15]$, k = 3のとき、5。 制限のないLISでは$[1,3,4,5,8,15]$が作れますが、8と15はk=3よりも大きく離れているのでこの問題で有効なLISではないです。
例2: num = $[2,1,3,4]$ k= $1$のとき、$[2,3,4]$で2
二分探索のLIS解法
多くのLIS解法で用いられるA[i] = 長さiのLISの中で末尾の最小値を記録した二分探索で求める方法を二分探索のLISの求め方とします。詳細は以下のような記事を参照してください。
さて、今回のように制限のある場合にもAを更新するときにk以内かを確認すればうまくいくのでは？と考えるかもしれませんがこれはうまくいきません。
上記の例2入力の$[2,1,3,4]$を例にとって示します。まず、$2$を処理し、$A = [3]$となります。$1$を処理するとき、同じ1文字までのLISしかできないならば、3より1の方が好ましいので$A = [1]$に更新されます。次に$3$を処理しますが(k以内かを見るとして)1には続けられないので捨てます。$4$も同様です。こうして、$[2,3,4]$となってほしいですが$[1]$と出力されます。
このように二分探索のLISの求め方では過去の数字を覚えていないため、$x$という値があった際に差が$k$以内という条件を満たせる値が過去にあったかが記録できません。
RMQを使ったLIS(セグ木など)
二分探索でLISを求める手法では過去にどんな数字があったのかを覚えていないため、今回の問題が解けません。先ほどの例2では$2$を処理した際にそれを覚えておけばそのあとに続けられました。
これを行うためにB[i] = 末尾の値がiであるLISの長さとしましょう。もし、kの制限がないとするなら、入力$a_1, a_2 \cdots a_n$があったとき、$B[a_i]$ = $max(B[0], B[1], \cdots B[a_i-1]) + 1$として求められます。これを工夫せずは求めると$O(a_i)$の計算量ですが、セグメント木などで1点更新のRange Maxを管理しておけば$O(log a_i)$で求められます。
例2を例にとると、長さ5(0-4)のBの配列を考えると、$[0,0,0,0,0]$ -> $[0,0,1,0,0]$ -> $[0,1,1,0,0]$ -> $[0,1,1,2,0]$ -> $[0,1,1,2,3]$となり、その最大値3がLIS長です。
座標圧縮の活用
ただし、セグ木は入力の値の上限が$M$とすると空間計算量$O(M)$となり、$a_i < 1e18$などの大きい場合に対応できません。この場合は座標圧縮を行えば、入力の個数$N$に対して$O(N)$となり競技プログラミングの問題などでは対応が可能です。
実装(座圧なし)
#include <atcoder/segtree>
#include <vector>
using namespace std;
using namespace atcoder;
int op(int a, int b) { return max(a, b); }
int e() { return -1; }
#define M 1000000 // 大きな数を扱うなら適当に座標圧縮する
int solve(vector<int> &input, int k){
int ans = -1;
segtree<int, op, e> seg(M);
for(auto &r: input){
int l = max(0, r - k);
int lislen = max(1, seg.prod(l, r) + 1);
seg.set(r, lislen);
ans = max(ans , lislen);
}
return ans;
}
int main() {
vector<int> a;
a = {4,2,1,4,3,4,5,8,15};
cout << solve(a, 3) << "\n"; // 5
a = {2,1,3,4};
cout << solve(a, 1) << "\n"; // 3
a = {7,4,5,1,8,12,4,7};
cout << solve(a, 5) << "\n"; // 4
a = {1,5};
cout << solve(a, 1) << "\n"; // 1
}