ABC134 E - Sequence Decomposing
April 17, 2020
問題
考えたこと
制約的にはO(N),O(NlogN)じゃないとだめ
となるとpririty_queueか二分探索あたりかな？
元の数列の順番も条件に含まれるので、ソートしたりするのは難しい。
シミュレートしてみよう
入力例1は{2, 1, 4 ,5, 3}という数列
先頭から1つづつ見ていく、みる数字が今使っている色のどれでも塗れない場合は新しい色で塗るという方針にしてみる
2をとりあえず色aで塗ってみる1は2以下なので同じ色で塗れないからbで塗る4は1,2どちらよりも大きいので、a,bどちらでも塗れる、ここで今後のことを考えみる
もしここでaにしてしまうと, 次に2が来た時にa, bどちらも使えないので新しい色を使わないといけないが、bで塗っておくと
次に2が来た時にaで塗れるのでbで塗っておくのが良さそうだ(これより, 今塗れる候補のうち、最後に塗った色が一番大きいのを選べば良さそう)5は1,4どちらよりも大きいので、a,bどちらでも塗れる。1つ前のと同様大きい方のbで塗っておく
最後の3は1より大きいが5よりは小さいのでaで塗れる
最終的に使った色は2色だった
考え方をみるに二分探索でいけそう
vectorを用意して、vectorのサイズ=使う色の数として
vectorの各添字の値が、その色を最後に使った数列の値にすれば良さそう。
新しく塗ろうとする数(例えば5という数字とする)が、
- vectorの中の最小値以下の場合はvectorの先頭に突っ込んであげる
- vectorの中の最小値より大きい場合は、vectorの中から5より大きい数で一番小さいのを更新すればいい
この要素の追加、更新方法であればvectorの中が昇順sortで保たれる
であれば、後者は二分探索でできる
問題は前者でvectorでやろうとすると昇順ソートでは,新しい要素の追加が遅い
(後ろに追加(push_back)であればO(1)だけど、前に追加はおそい)
vectorを降順にしてあげれば, いけそう? 新しい要素の追加は後ろにするとして
これなら
- 新らしい要素の追加は
O(1) - 今使っている色で塗れる時は、塗れる色の中から一番大きいやつを選ぶ二分探索なので
O(lonN)
最終的にO(NlogN)で解ける
実装では、逆順になってるのでlower_boundとか使えないので自前で二分探索を実装する必要がある
これがミスりやすいので注意(3WA)
提出したコード
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
typedef pair<int, int> P;
ll modnum = 1e9+7;
int main() {
int n; cin >> n;
vector<int> ans;
rep(i, n) {
int a; cin >> a;
if(ans.size() == 0 || ans[ans.size()-1] >= a) {
ans.push_back(a);
} else {
int l = 0, r = ans.size()-1;
while(r-l > 1) {
int mid = l + (r - l) / 2;
if(a > ans[mid]) r = mid;
else l = mid;
}
if(l == 0 && a > ans[0]) ans[l] = a;
else ans[r] = a;
}
}
cout << ans.size() << endl;
return 0;
}
解説をみて
dequeを使えば, lower_boundとかも使える
dequeって前と後ろ両方から突っ込めたり取れたりするqueueだと思ってたけどvectorみたいに添字アクセスとかもできる
ので、dequeを使えばもともと想定してた昇順ソートで、新しく値を突っ込む時は前に入れるってので実装できる
これだと二分探索にlower_beginとか使えるので実装が楽
deque使ったコードはこちら
int main() {
int n; cin >> n;
deque<int> ans;
rep(i, n) {
int a; cin >> a;
int itr = lower_bound(ans.begin(), ans.end(), a) - ans.begin();
if(itr == 0) ans.push_front(a);
else ans[itr-1] = a;
}
cout << ans.size() << endl;
return 0;
}
あと解説見たら、全てにマイナスかけるっていう方法とかもあるらしい
これならvectorでいけるらしい