【競プロ精進ログ】ABS編<8>

zuka

APG4bを終えたので次はABSです。

本記事は,管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために,積極的にアウトプットしていく作戦です。これから競技プログラミングを始めようと考えている人や,なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。

目次

本記事の概要

Atcoderが公表しているc++の入門記事の内容を1からさらっていくものです。今回はABC085B Kagami Mochiです。

実装

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

// 以下は配列を表示するための関数です
// 今回はしっかりと重複が削除されているかどうかを可視化するために利用しました
void printVec(vector<int> &V){
  cout << "[";
  int cnt = 0;
  for (int v: V){
    if (cnt < V.size()-1) cout << v << " ";
    else cout << v;
    cnt ++;
  }
  cout << "]" << endl;
}

int main() {
  int N;
  cin >> N;
  vector<int> D(N);
  rep(i, N){
    cin >> D[i];
  }
 // まずはソートします
 // uniqueは隣合う重複を削除する関数ですので
 // ソートしないと同じ数字が出現する可能性があります
  sort(D.begin(), D.end());
 // uniqueの返り値をそのままeraseで利用します
  D.erase(unique(D.begin(), D.end()), D.end());
  cout << D.size() << endl;
}

ポイント

今回おさえるべき内容

 配列内の重複を削除する方法を確認する

配列内の重複を削除する問題です。c++ではSTLにuniqueという関数が装備されています。uniqueは隣り合う重複を削除する関数ですので,昇順ソートした配列に対してuniqueを適用することで,重複を完全に削除した配列を得ることができます。

しかし,それ単体では重複を削除する前の配列と同じ長さの配列を作成します。そのために,作成される配列は末尾にゴミが残っています。uniqueの返り値は末尾のゴミが始まるインデックスですので,そいつをeraseの引数として利用すれば,うまいこと重複を削除した配列が得られます。答えは,重複を削除した後の配列の長さを出力すればOKです。

よかったらシェアしてね!

コメント

コメントする

目次
閉じる