ひらめの日常

プログラミングと読書と

ABC134-E Sequence Decomposing (500)

Sequence Decomposing

問題はこちら atcoder.jp

問題文は次のように言い換えることができる。すなわち、「数列  A が与えられた時に、その数列を狭義単調増加部分列に分ける。その分け方の最小値を求めなさい」という問題と同値になる。

考え方

sample1について、配列をイテレートする時の様子は以下のようになる。

具体的には、現在有効な部分列の右端(=最大の値)を保持する集合  S を持っておく。各要素  A_i を見た時に、 A _ i > s_j となるものが  S の中に存在するならば、 s _ j = A_i と更新する(以下の図で見ると、赤丸のものが  S に含まれるものになる)。

f:id:thescript1210:20190721071519j:plain
sample1

なお、更新できるものが複数あるときは、貪欲になるべく大きい値を更新するとよい。なぜなら、小さい値を残しておいたほうが、後々に更新可能な値の範囲が広がるためである。

解答

実装方法には、multisetを使った解法、dequeを使った解法、vectorを使った解法があるのでそれぞれの実装とその注意点を見ていく。

1. multisetを使う

今回は同じ値が複数個  A に含まれる可能性があるので、 multisetを使う。multisetに入っているものの中から、lower_boundを使って  A_i 以上の場所を取得。その一個前が  A_i 以下で最大の値になるので、それを更新する。

注意点としては以下の通り。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

int main() {
    ll n;
    cin >> n;
    
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    
    multiset<ll> s;

    for (ll i = 0; i < n; ++i) {
        ll now = a[i];
        auto itr = s.lower_bound(now);
        if (itr != s.begin()) s.erase(--itr);
        s.insert(now);
    }
    cout << s.size() << endl;
    return 0;
}

Submission #6482597 - AtCoder Beginner Contest 134

2. dequeを使う

 A_i が集合に入っているもの全てより小さい値の時、配列の先頭に追加する」という操作をしたい。また、それとは別にランダムアクセスをして更新作業もできるようにしたい。dequeはこれを満たしてくれる。

dequeとはdouble-ended-queueの略で、末尾と先頭への要素追加・削除が  O(1) で行える。さらにindexを指定してのランダムアクセスも  O(1) で行える。 C++ 両端キュー std::deque 入門

やっていることはmultisetの時と基本的に同じだが、注意点としては以下の通り。

  • dequeはランダムアクセスはできるが、連続したメモリ領域を確保するとは限らない。なので、イテレーターをデクリメントして値を参照するのではなく、一回indexに直してから値を更新する必要がある。

  • 常にsort済みであるようにdequeに入れていくので、lower_boundが使える。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

int main() {
    ll n;
    cin >> n;
    vector<ll> a(n);

    rep(i, n) cin >> a[i];

    deque<ll> dq;
    rep(i, n) {
        ll idx = lower_bound(dq.begin(), dq.end(), a[i]) - dq.begin();
        if (idx == 0) dq.push_front(a[i]);
        else dq[idx - 1] = a[i];
    }
    cout << dq.size() << endl;
    return 0;
}

Submission #6482641 - AtCoder Beginner Contest 134

3. vectorを使う

2の時に、先頭に追加することを考えたため、vectorでは不適となった。しかし、値を降順に保持しておいて、末尾に追加することを行えばvectorでも実現が可能。

そもそも先ほどまで昇順にこだわっていたのは、lower_boundなどを使って高速に更新する値を求めたいからであったので、高順の時にも lower_boundが使えれば良い...(実は使える!!!)。

これもやっていることは他の手法と同じ。注意点としては以下の通り。

  • 降順にsortされたvectorに対しては、lower_bound(v.rbegin(), v.rend(), x) とすることで既存ライブラリを使って二分探索ができる。これで得られる reverse_iteretorはrbegin()からrend()の方へインクリメントしていく形になる。

  • アドレスの比較は、全て reverse_iteretor同士で行うこと。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

/* ------------- ANSWER ------------- */
/* ---------------------------------- */

int main() {

    ll n;
    cin >> n;
    vector<ll> a(n);

    rep(i, n) cin >> a[i];
    vector<ll> d;

    rep(i, n) {
        auto itr = lower_bound(d.rbegin(), d.rend(), a[i]);
        if (itr == d.rbegin()) {
            d.emplace_back(a[i]);
        } else {
            itr--;
            *itr = a[i];
        }
    }
    cout << d.size() << endl;
    return 0;
}

Submission #6482661 - AtCoder Beginner Contest 134