Sequence Decomposing
問題はこちら atcoder.jp
問題文は次のように言い換えることができる。すなわち、「数列 が与えられた時に、その数列を狭義単調増加部分列に分ける。その分け方の最小値を求めなさい」という問題と同値になる。
考え方
sample1について、配列をイテレートする時の様子は以下のようになる。
具体的には、現在有効な部分列の右端（＝最大の値）を保持する集合 を持っておく。各要素
を見た時に、
となるものが
の中に存在するならば、
と更新する（以下の図で見ると、赤丸のものが
に含まれるものになる）。
なお、更新できるものが複数あるときは、貪欲になるべく大きい値を更新するとよい。なぜなら、小さい値を残しておいたほうが、後々に更新可能な値の範囲が広がるためである。
解答
実装方法には、multisetを使った解法、dequeを使った解法、vectorを使った解法があるのでそれぞれの実装とその注意点を見ていく。
1. multisetを使う
今回は同じ値が複数個 に含まれる可能性があるので、 multisetを使う。multisetに入っているものの中から、
lower_boundを使って 以上の場所を取得。その一個前が
以下で最大の値になるので、それを更新する。
注意点としては以下の通り。
multiset::eraseを使うとき、引数にイテレーターを指定すると一つだけ削除してくれる。逆に値を指定すると、その値が入った全てを削除する。今回は一つだけ削除したいのでイテレーターを指定して削除する。
multiset::erase - cpprefjp C++日本語リファレンスlower_bound(mulsiset.begin(), multiset.end(), x)の計算量は、
multiset::lower_boundの計算量は。
競プロ覚書：二分探索，std::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]; 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を使う
「 が集合に入っているもの全てより小さい値の時、配列の先頭に追加する」という操作をしたい。また、それとは別にランダムアクセスをして更新作業もできるようにしたい。dequeはこれを満たしてくれる。
dequeとはdouble-ended-queueの略で、末尾と先頭への要素追加・削除が で行える。さらにindexを指定してのランダムアクセスも
で行える。
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; }
