Codeforces Round #579 (Div. 3) E. Boxers

問題文

個の数字が与えられる。各数字に対して+1,-1を行う事ができる。uniqueな数字の数を最大化せよ。

考えていたこと

・AtCoderでやった問題だ！と思ったけど違った
・は、またはの数を増やすことができる。の数が3以上ならばどちらも増やせる。2だとどちらに増やせばいいかわからない。
・max(右詰め、左詰め)を試したがWA.

解法

・のときは動かさないと思っていたのがだめだった。全部動かす。
・をに変化させたいとき、ができるだけ0になっていれば良いので(推移できてuniqueな数字が増える)、できるだけ0を作る。
つまり、できるだけ右に詰めて、左に詰めて試す。
・Editorialの解法と全く違うけど、これ合ってるのかな…?

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define all(in) in.begin(), in.end()
signed main(){
    int n; cin >> n;
    vector<int>p(n);
    for(auto & e : p) cin >>e;
    vector<int>v(150002,0LL);
    for(auto e : p) v[e]++;
    for(int i = 1; i < v.size(); ++i){
        if(v[i] == 0)continue;
        if(i != 1 and v[i - 1] == 0)
            v[i - 1]++, v[i]--;
    }
    for(int i = v.size() - 2; i >= 1; --i){
        if(v[i] == 0) continue;
        if(v[i + 1] == 0)
            v[i + 1]++,v[i]--;
    }
    cout << accumulate(all(v),0LL,[](int a, int b){return a += ( b > 0);})
    << endl;
}