AOJ ITP2 9_D（Set Symmetric Difference）を解く

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

ITP2では、「プログラミングのための基礎ライブラリを獲得します」とあります。トピック#9では、集合演算を学びます。

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

問題（9_D: Set Symmetric Difference）

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

AOJ ITP2 9_D問題: Set Symmetric Difference

対称差集合を求める set_symmetric_difference について学びます。

std::set_symmetric_difference について

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

std::set_symmetric_difference は差集合を求めます。

  template <class InputIterator1, class InputIterator2, class OutputIterator>
  OutputIterator
    set_symmetric_difference(InputIterator1 first1,
                             InputIterator1 last1,
                             InputIterator2 first2,
                             InputIterator2 last2,
                             OutputIterator result);

2つのソート済み範囲 [first1, last1) と [first2, last2) の対称差集合を求めます。対称差集合とは、[first1, last1) と [first2, last2) の範囲に共通しない要素を result へコピーすることを意味します。結果もソートされています。

最大で 2 × ((last1 – first1) + (last2 – first2)) – 1 回の比較を行います。

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

2つのソート済の数列AとBが与えられます。「AとBの互いに素な集合を求めてください」とあります。対称差集合を求めて、要素を出力します。

対称差集合を set_symmetric_difference で求めます（24行目）。set_symmetric_difference の最後の引数は、 OutputIterator を指定する必要があります。このためヘルパ関数 inserter を使いました。

以下が、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];
	}
	int m;
	cin >> m;
	vector<int> b(m);
	for (int i = 0; i < m; ++i) {
		cin >> b[i];
	}

	vector<int> result;
	set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(), inserter(result, result.end()));

	sort(result.begin(), result.end());
	for (auto it = result.begin(); it != result.end(); ++it) {
		cout << *it << endl;
	}

	return 0;
}

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

最後に

トピック#9の4回すべてで新しいことを学べました。どこかで応用できればと思います。

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