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

hamayanhamayan's blog

Flat Subsequence [ACL Beginner Contest D]

競技プログラミング

https://atcoder.jp/contests/abl/tasks/abl_d

前提知識

解説

https://atcoder.jp/contests/abl/submissions/17050957

たぶん似たような解法をやったことが無いと、思いつくのは難しいかもしれない。
以下のような問題設定は見たことがないだろうか。

  • BはAの部分列である
  • どのBの隣り合う要素についてもB[i]<B[i+1]が成り立つ

これはLISと言う典型問題である。
今回の問題はこれのセグメントツリー解法を知っていると思いつきやすい。

先頭から見ていく

先頭から順に評価をしていくのだが、A[i]について配列Bに加えるかを考えるとしよう。
この時、加えることのできる配列Bは末尾が[A[i]-K,A[i]+K]に含まれるものである。
よって、以下のようなセグメントツリーを用意して、この検索を高速化しよう。

segtree[x] := 末尾の要素がxである配列Bの最大サイズ
segtree[x,y] := [x,y)の最大値

先頭から順に評価して行く中で、このsegtreeを適宜更新することで、以下のようにとらえることができる。

segtree[x] := 『A[i]以前までの要素を使って』末尾の要素がxである配列Bの最大サイズ
segtree[x,y] := [x,y)の最大値

これで得られた最大値+1をsegtree[A[i]]に更新していく。
最後にsegtree全体の最大値を取ると答え。

これは何か？

色々な考え方があると思うが、TLではin-place DP、インラインDPであるという発言を多く見た。
確かに。

dp[i][x] := 配列Aのi番目までを使って末尾がxの配列Bを作ったときの配列Bの最大サイズ

このように定義すると更新式はこうなる

dp[i][x] -> dp[i + 1][x]
max(dp[i][A[i] - K],...,dp[i][A[i] + K]] -> dp[i + 1][A[i]]

1回の更新ではA[i]の部分しか更新されない。
よってインラインDPができる。
更新時のmaxはセグメントツリーで実現できるので、セグメントツリーをそのままDPっぽく扱って計算していく感じだ。

int N, K, A[301010];
SegTree<int, 1 << 19> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];

    rep(i, 0, N) {
        int ma = st.get(max(0, A[i] - K), min(301010, A[i] + K + 1));
        st.update(A[i], ma + 1);
    }

    int ans = st.get(0, 301010);
    cout << ans << endl;
}