C - 行列のできるドーナツ屋

[Q] https://atcoder.jp/contests/donuts-2015/tasks/donuts_2015_3
単調増加列の最長一致（LIS）をこねます。

入力例を考える

6
5 4 3 6 2 1

5の人からみたら 0人
4の人から見たら {5} で1人
3の人から見たら {5,4} で2人
6の人から見たら {5,4,3} で3人
2の人から見たら {6} で1人
1の人から見たら {6,2} で2人

目線の人を除いた「単調減少列」の大きさが答えになっていそう。だけど、目線の人ごとに探索するとO(N^2)になってしまう。

使えそうなアルゴリズムに、
LIS 単調増加列の最長一致
https://atcoder.jp/contests/typical90/tasks/typical90_bh
が思い当たります。

テンプレをいくらか改良して、
1, 増加列を減少列にしたいので、A[i]をマイナスにする
2, 最長一致ではないので、更新点(cnt)を常に更新する
ことをします。

   DP[ ] = -A   ans  DP
              // 0
   DP[0] = -5 // 1   {-5}
   DP[1] = -4 // 2   {-5, -4}
   DP[2] = -3 // 3   {-5, -4, -3}
   DP[0] = -6 // 1   {-6}
   DP[1] = -2 // 2   {-6, -2}
   DP[2] = -1        {-6, -2, -1}

LISの典型を解けばおのずと問題も解けるので、有能解説に飛ぶのがいいかもしれない。

https://atcoder.jp/contests/donuts-2015/submissions/25521483

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

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

// LIS 単調増加列の最長一致
/*
https://atcoder.jp/contests/typical90/tasks/typical90_bh
*/
ll DP[100010];
ll A[100010];
int main(){
 cin.tie(0);
 ios::sync_with_stdio(0);
 cout << fixed << setprecision(10);
 ll N;
 cin >> N;
 rep(i, N){
   cin >> A[i];
   A[i] *= -1;
 }
 ll cnt = 0;
 rep(i, N){
   cout << cnt << endl;
   ll pos = lower_bound(DP, DP+cnt, A[i]) - DP;
   DP[pos] = A[i];
   cnt = pos+1;
 }
}