AOJ ITP2 4_D（Unique）を解く

Aizu Online Judge（AOJ）が提供している「プログラミング応用」（ITP2）の4_D問題をC++で解いてみました。

ITP2では、「プログラミングのための基礎ライブラリを獲得します」とあります。トピック#4では、列に対する変更を学びます。

#3から#6は、alogrithm をインクルードして利用する機能を紹介します。全てのアルゴリズムは、データ構造の実装から切り離されています。アルゴリズムの要件（主にイテレータ）を満たせば動作します。

問題（4_D: Unique）

問題はリンク先をご覧ください。

AOJ ITP2 4_D問題: Unique

重複要素を取り除く unique について学びます。

std::unique について

以下は、cpprefjp 様の記事を参考にさせていただきました。

std::unique を使って隣り合った重複要素を取り除くことができます。

  template <class ForwardIterator>
  ForwardIterator unique(ForwardIterator first, ForwardIterator last);

unique は、隣り合った重複要素を除いた要素を、範囲の先頭に集めます。この関数によって要素数は変わりません。この関数は、集められた重複なし範囲の末尾の次を指すイテレータを返すため、erase 関数などで削除する必要があります。

具体的には、以下のように使うことを想定しています。

	vector<int> a(n);
	// ... 
	sort(a.begin(), a.end());
	a.erase(unique(a.begin(), a.end()), a.end());

C++ プログラム例（ITP2 4_D）

昇順にソートされた配列 A が与えられます。unique と erase で重複した要素を削除します（17行目）。最後に A を出力します。

以下は、C++のプログラムです。

#include <iostream>
#include <algorithm>

#include <vector>

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}

	a.erase(unique(a.begin(), a.end()), a.end());

	for (int i = 0; i < a.size(); ++i) {
		cout << a[i] << " \n"[i == a.size() - 1];
	}

	return 0;
}

上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。

最後に

C++のライブラリ全体の方針なのか、unique だけの仕様なのか不明ですが、unique 単独では、効果が中途半端です。事実上 erase と組みで使うことが前提の仕様となっています。

引き続き、ITP2 の問題を紹介していきます。