AtCoder Beginner Contest 134 E - 今日から始める競プロ日記
はじめに
AtCoder Beginner Contest (ABC) 134 E を解いてみた。
E - Sequence Decomposing
数列 A1, A2, ...... , AN が与えられる。
このとき、それぞれの整数を以下の条件を満たすように色を塗っていく。
同じ色で塗られている整数 Ai と Aj (i < j) において、Ai < Aj が成り立つ
参考
解説動画いつも分かりやすくてありがたい。
今回の解き方
まず、例として以下の数列を考える。
2 1 4 5 3
まず先頭から値を一つずつ順番に見ていって、条件に合うように空の配列に入れていくとする。
流れは以下のようになる。（B[0], B[1]は空の配列）
初期状態 B[0] : 空 B[1] : 空 ...... ...... B[M] : 空 一つ目の値：2 B[0] : 2 ← 入れる 二つ目の値：1 B[0] : 2 B[1] : 1 ← 入れる（2 < 1 だからA[0]には入れられない） 三つ目の値：4 B[0] : 2 4 ← 入れる B[1] : 1 四つ目の値：5 B[0] : 2 4 5 ← 入れる B[1] : 1 五つ目の値：3 B[0] : 2 4 5 B[1] : 1 3 ← 入れる
このとき、配列の数（B[0], B[1]の二つ）が色の数ということになる。
よって答えは2。
しかし、この解き方では計算量がO(N^2)くらいになると思うので間に合わない（たぶん）。
そこで空の配列は一つだけにして考えてみる。
行う処理は以下の二つ。
- 次に入れる値が配列に格納されているどの値よりも小さければ先頭にいれる
- それ以外の場合は、次に入れる値より小さくて一番大きな値を書き換える
解き方はこんな感じ。
初期状態 B : 空 一つ目の値：2 B : 2 二つ目の値：1 B : 1 2 ← 前から入れる 三つ目の値：4 B : 1 4 ← 2を書き換える（4より小さくて一番大きな値である2を書き換え） 四つ目の値：5 B : 1 5 ← 4を書き換える（5より小さくて一番大きな値である4を書き換え） 三つ目の値：3 B : 3 5 ← 1を書き換える（3より小さくて一番大きな値である1を書き換え）
Bの長さが答えとなるので（つまり色の数）、答えは 2。
このとき、Bは常に昇順になっている。
よって、二分探索的なものを使うことができるので計算量はO(NlogN)となる。
ここでいう二分探索的なものがlower_bound()である。
lower_bound()を使えば、ある値以上で一番小さい値のインデックスを求めることができる。
これにより、先の例で示したような「Xより小さくて一番大きな値であるYを書き換え」という処理を行うことができる。
また、配列の先頭に値を入れるという処理はdeque（デックと読むらしい）を使うことで可能となる。
dequeは両端のどちらからでも値を出し入れすることができるvectorの拡張版らしい。
push_front()で配列の先頭に値を入れることができる。
コード
コードはAtCoder公式の解説動画を参考にさせていただきました。
ありがとうございます。
#include <iostream>
#include <deque>
#include <vector>
using namespace std;
int main()
{
int N;
cin >> N;
vector<int> a(N);
for(int i = 0; i < N; i++)
{
cin >> a[i];
}
//両端キュー、前からも値を入れることが可能
//昇順に並べていく
deque<int> d;
for(int i = 0; i < N; i++)
{
//a[i]以上の値の中で一番小さい値のインデックスを返す
int p = lower_bound(d.begin(), d.end(), a[i]) - d.begin();
//a[i]以上の値が存在しないときはキューの一番最初に入れる
//（つまり別の色を塗る）
if(p == 0)
{
d.push_front(a[i]);
}
//a[i]以上の値より一つ左隣り（インデックスが一つ小さい）値を書き換える
//つまりa[i]より小さい値の中でで一番大きな値を書き換える
//（同じ色で塗るということ）
else
{
d[p-1] = a[i];
}
}
//dの長さが色の数になっている
//（別の色を塗るたびに先頭に挿入しているから）
int ans = d.size();
cout << ans << endl;
return 0;
}
おわりに
今日は自分にとってちょっと難しめの問題を解いてみた。
本番で解けたら嬉しい。
