【ABC408】B問題 - Compression 考察から実装(c++)まで

AtCoderBeginnerContest408の解説＆感想です。
コンテストリンク

問題一覧

• 【ABC408】A問題 - Timeout　考察から実装(c++)まで
• 【ABC408】B問題 - Compression　考察から実装(c++)まで <- イマココ
• 【ABC408】C問題 - Not All Covered　考察から実装(c++)まで
• 【ABC408】D問題 - Flip to Gather　考察から実装(c++)まで
• 【ABC408】E問題 - Minimum OR Path　考察から実装(c++)まで
• 【ABC408】F問題 - Athletic　考察から実装(c++)まで

B問題 - Compression

問題リンク

問題概要

長さ$N$の数列$A=(A_1,A_2,...,A_N)$が入力される。重複を除いて小さい順に出力せよ。

制約

• $ 1 \le N \le 100 $
• $ 1 \le A_i \le 100 $

考察

「重複削除」「小さい順」はどっちも標準ライブラリのsetの得意技なので、$A$の要素を全部setに突っ込んで表示すれば良さそう。
c++ならvectorに入れていってsortしてunique+eraseでも良さそう。どっちも実装しておこう。
計算量はどちらも$O(NlogN)$

実装 (set ver)

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

int main(void){
    //入力
    ll N;
    cin>>N;
    
    //入力を全部setにぶち込む
    set<ll> s;
    for(int i=0;i<N;i++){
        ll a;
        cin>>a;
        s.insert(a);
    }
    
    //setの要素を表示していく
    cout<<s.size()<<endl;
    for(ll t: s) cout<<t<<" ";
    return 0;
}

実装（unique+erase ver）

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

int main(void){
    //入力
    ll N;
    cin>>N;
    
    //入力を全部setにぶち込む
    vll a(N);
    for(int i=0;i<N;i++) cin>>a[i];
    
    //unique+eraseで重複を全部削除する
    sort(a.begin(),a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    
    //aの要素を表示していく
    cout<<a.size()<<endl;
    for(ll t: a) cout<<t<<" ";
    return 0;
}