ABC134 E問題：Sequence Decomposing

問題. Sequence Decomposing

長さ $N$ の非負整数列 $a = (a_1, a_2, \ldots, a_N)$ が与えれられる．各要素を色で塗ることを考える．ただし，同じ色で塗られたどの 2 要素 $a_i$ と $a_j \, (i < j)$ に対しても $a_i < a_j$ が成り立つように塗る．このような塗り方の中で使用した色の種類の最小値を答えよ．

制約： $1 \le N \le 10^5$ ，　 $0 \le a_i \le 10^9$

解法．Dilworthの定理

整数列 $a$ に対応する狭義半順序集合 $P_a = (X, \prec)$ を次のように構成する．

　・ $X = \{1, 2, \ldots, N\}$
　・任意の $i, j \in X$ に対して， $i \prec j \Leftrightarrow i < j$ かつ $a_i < a_j$

$P_a$ は狭義半順序集合であるための条件，

　　1. 非反射性：任意の $i \in X$ に対して $i \nprec i$ ，
　　2. 推移性：任意の $i, j, k \in X$ に対して $i \prec j$ かつ $j \prec k$ ならば $i \prec k$ ，
　　3. 非対称性：任意の $i, j \in X$ に対して $i \prec j$ ならば $j \nprec i$

をすべて満たすことが確認できる．

求める答えは $P_a$ を被覆する鎖の数の最小値である．Dilworth の定理からこの値は $P_a$ の反鎖のサイズの最大値に等しい．したがって， $P_a$ の最大サイズの反鎖を求めることを考える．
$P_a$ の反鎖は元の数列で解釈すると広義単調減少部分列に等しい．これは $a$ の各要素の符号を反転させた整数列に対する最長増加部分列問題に等しい．最長増加部分列は $O(N \log N)$ 時間で求まるので，使用した色の種類数の最小値も $O(N \log N)$ 時間で求まる．

計算時間： $O(N \log N)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

template<typename T>
int longestIncreasingSubsequence(const std::vector<T> &a) {
    if (a.empty()) return {};

    const T INF = std::numeric_limits<T>::max();
    const int size = a.size();

    std::vector<T> dp(size, INF);
    std::vector<int> idx(size);
    for (int i = 0; i < size; ++i) {
        // 単調増加： a_i <= a_j
        idx[i] = std::distance(dp.begin(), upper_bound(dp.begin(), dp.end(), a[i]));
        dp[idx[i]] = a[i];
    }

    return *max_element(idx.begin(), idx.end()) + 1;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<int> a(n);
    for (auto &a_i : a) cin >> a_i, a_i *= -1;

    cout << longestIncreasingSubsequence<int>(a) << endl;

    return 0;
}

＊注意：解説でDilworthの定理はDAG上で成り立つと書いていますが，正しくはDAGを推移閉包したものの上で成り立つが正しいと思います．反例は有向道などです．

Dilworthの定理を忘れて時間がかかったので反省．
Dilworth の定理はDAGの推移閉包したものに対しても成り立つはずで，それが狭義半順序集合なので大丈夫なはず．一般的な DAG には DAGの最小道被覆問題 - 忘れても大丈夫を使用するが，今回は Dilworth の定理が成り立つので最長増加部分列問題に帰着できて嬉しい．