AtCoder Beginner Contest E - Sequence Decomposing 解いた感想

問題はこちら。

素直にやれば解ける問題。

atcoder.jp

解法

setでデータを管理する。データの中身は同じ色で塗られている塔の中で高さが最大のもの。

新しく塔（高さ）に色を塗る（setに追加する）ことを考える。色を増やさない方が良いので、自分より高さの小さい塔を探し出し、その塔の色と同じ色をに塗れば良い。

例えばset: {1, 3, 6, 2, 10}で新しく8の塔に色を着けるとすると、候補になるのは{1, 2, 3, 6}である(10は8より大きいので同じ色を使うことができない）。この4つの候補のうちどれと同じ色を使ってもルール上良いのだが、最適なのは6と同じ色を塗ることである。

例えば1と同じ色を塗ってしまうと、setは{8, 3, 6, 2, 10}と更新される。このあと高さ2 の塔に色つけをしようとすると、新しい色を使わなければならない。（setの最大値が2だから）。

これは最適ではない。塔を6と同じ色を塗ると、{1, 3, 8, 2, 10}と更新され、高さ2の塔に色を付けようと思ったときに高さ1の塔と同じ色を使うことができる。結果色を使う総数は増えない。

そうなると色の候補の中で最も最大値が大きい塔と同じ色を塗るのが良いことがわかる。候補の最大値の求め方はset.lower_boundで以上の要素の中で最小の要素のイテレータを取得、その直前の要素が求めるものである。(prev()で取得可能)

候補が0個だったときには(lower_boundで取得したイテレータが先頭のイテレータだった場合）、すでに使った色と同じ色を使う事はできないのでsetの要素として新しくを追加する。

lower_boundはサイズに対して対数時間で計算できるので、十分早い。少なくとも今回の問題に関しては問題ない。

提出コード

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i=0;i<n;i++) cin >> a[i];
  multiset<int> s;
  for(int i=0;i<n;i++) {
    if(i == 0) s.emplace(a[i]);
    else {
      auto it = s.lower_bound(a[i]);
      if(it == s.begin()) s.emplace(a[i]);
      else {
        s.erase(prev(it));
        s.emplace(a[i]);
      }
    }
  }
  cout << s.size() << endl;
}

 Editorialに面白いことが書いてあった気がする。時間があれば追記予定。