[AtCoder] ACL Beginner Contest D – Flat Subsequence

2020年9月27日2020年12月12日

問題

方針

最長増加部分列を解くような感じで解けるみたいですが、あまり理解できませんでした。

まず初めに、\( A_i \leftarrow A_i + K \) と再定義します。ここで、\( d(i) \) を末尾が \( i \) で終わる最長部分列の長さとします。\( d \) は \( 0 \) で初期化し、\( i – 1 \) まで \( d \) が構築できたとして、\( A_i \) について考えます。\( d(A_i) \) の更新は、

\[d(A_i) \leftarrow \max \left( d(A_i – K), d(A_i – K + 1), \cdots d(A_i + K)\right) + 1\]

となります。\( A_i – K \leq A_i \leq A_i + K \) となるので常に更新して大丈夫です。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct SegmentTree {
private:
    int n;
    vector<int> node;
public:
    SegmentTree(int N) {
        n = 1;
        while(n < N) n *= 2;
        node.resize(2 * n - 1, 0);
    }

    void update(int k, int x) {
        k += (n - 1);
        node[k] = x;
        while (k > 0) {
            k = (k - 1) / 2;
            node[k] = max(node[2 * k + 1], node[2 * k + 2]);
        }
    }

    int query(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r < 0) r = n;
        if (r <= a || b <= l) return 0;
        if (a <= l && r <= b) return node[k];
        int vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
        int vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return max(vl, vr);
    }
};

const int MAX = 600001;
int main() {
    int N, K;
    cin >> N >> K;
    int A[N];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        A[i] += K;
    }
    SegmentTree st(MAX);
    for (int i = 0; i < N; i++) {
        int v = st.query(A[i] - K, A[i] + K + 1);
        st.update(A[i], v + 1);
    }
    cout << st.query(0, MAX) << "\n";
    return 0;
}

参考