実は双対性が深く絡んでるけど、割と素直な Greedy でも解ける

問題へのリンク

問題概要

$N$ 要素からなる整数列 $A_{1}, \dots, A_{N}$ が与えられる。これらの要素をいくつかの色に塗り分けたい。ただし、同じ色で塗られた要素は狭義単調増加になるようにしなければならない。

このようなことが可能となる色の種類数の最小値を求めよ。

制約

$1 \le N \le 10^{5}$
$0 \le A_{i} \le 10^{9}$

考えたこと

これ実はめっちゃ有名な問題なのだ。「LIS の双対問題」とも言うべき問題となっている。色々な背景があるけど、何も知らないものとして考察してみようと思う。

たとえば $A = (3, 5, 1, 2, 8, 7, 4, 6)$ としたとき、これらの要素を左から見ていって、いくつかの山に分けたい。各山の要素は単調増加となるようにしたい。そして山の個数を最小にしたい。

まず、3 を一つ目の山に入れる

そして、5 は 3 の上に重ねられるので重ねてしまう (5 を別の山に分けるメリットはない...そのような解があったとしても、その解を悪化させることなく、5 を初めから 3 の上に重ねる場合へと変形できる)。

3 → 5

次の 1 については、5 の上に重ねられないので、新たに山を分ける。

3 → 5
1

その次の 2 は、1 の上に重ねられるので重ねる

3 → 5
1 → 2

その次の 8 は、「5 の上」と「2 の上」のどちらにも重ねることができる。しかし 2 の上に重ねるのは勿体ない。できるだけ大きい方に重ねた方がよい。

3 → 5 → 8
1 → 2

その次の 7 は、8 の上には重ねられないので 2 の上に重ねる。

3 → 5 → 8
1 → 2 → 7

その次の 4 は新たに山にする

3 → 5 → 8
1 → 2 → 7
4

最後に 6 は、4 の上に重ねられる。

3 → 5 → 8
1 → 2 → 7
4 → 6

以上から、3 色だとわかる。

一般化

以上の手続きを一般化すると、次のように言える。

要素 $A_{i}$ を考えるとき、

すでにある各山のてっぺんの値のうち、 $A_{i}$ 未満となっている範囲で最大の要素のところに $A_{i}$ を重ねる
そのような山が存在しない場合は新たに $A_{i}$ のみからなる山を作る

このとき、実は各山のてっぺんの値は常に単調減少になっている。したがって、「どの山の上に乗せたら良いか」は二分探索 (lower_bound) で求めることができる。

ただし、単調減少だと扱いづらいので、あらかじめ $A$ を反転してしまって、「各山を狭義単調減少となるようにする」という設定にしてしまえば扱いやすい。そうすれば、lower_bound() が使いやすくなる。

実は LIS

最後にたどり着いたアルゴリズム ( $A$ を反転したバージョン) をもう一度振り替えてみよう。

要素 $A_{i}$ を考えるとき、

すでにある各山のてっぺんの値のうち、 $A_{i}$ より大きくなっている範囲で最小の要素のところに $A_{i}$ を重ねる
そのような山が存在しない場合は新たに $A_{i}$ のみからなる山を作る

これって、実は LIS (Longest Increasing Subsequence) を求めるための DP とまったく同じものだ！！！！！

ただし LIS といっても、同じ値が連続することは許すものとなることに注意... 山の中で同じ値は許さないが LIS としては同じ値を許すものになる。

さて、実は今回の問題は LIS の双対問題とも言うべき問題になっている。より一般に Dilworth の定理を用いた話が editorial にも載っている。

https://img.atcoder.jp/abc134/editorial.pdf

コード

計算量は $O(N \log N)$ である。

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

// dp[i] := 長さが i の増加部分列として最後尾の要素のとりうる最小値
// is_strong = false のとき、同じ値が連続することを許す
template<class T> int LIS(vector<T> a,  bool is_strong = true) {
    const T INF = 1<<30; // to be set appropriately
    int n = (int)a.size();
    vector<T> dp(n, INF);
    for (int i = 0; i < n; ++i) {
        if (is_strong) *lower_bound(dp.begin(), dp.end(), a[i]) = a[i];
        else *upper_bound(dp.begin(), dp.end(), a[i]) = a[i];
    }
    return lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
}

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    reverse(A.begin(), A.end());
    cout << LIS(A, false) << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 134 E - Sequence Decomposing (水色, 500 点)

問題概要

制約

考えたこと

一般化

実は LIS

コード