AOJ ITP2 2_D（Splice）を解く

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

ITP2では、「プログラミングのための基礎ライブラリを獲得します」とあります。トピック#2では、基本データ構造を学びます。

問題（2_D: Splice）

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

AOJ ITP2 2_D問題: Splice

list::splice について学びます。

list::splice について

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

list::splice は、list オブジェクトの要素を移動します。

void splice(iterator position, list& x);

position が指す要素の前に、list x のすべての要素を移動します。

C++03 までは、移動する要素数 x に対して線形時間がかかりました。また移動元 list x のイテレータと参照が無効となります。

C++11からは、定数時間で処理できるようになりました。この場合、移動元 list x のイテレータと参照は無効になりません。

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

問題で与えられるクエリに従い、以下の操作を行います。なお、Vector コンテナの要素を list<int> として、複数の list を用意します。

• クエリ0　insert により、L[t] の末尾に、与えられた x を挿入する。
• クエリ1　L[t] のすべての要素を空白区切りで出力する。空の場合も含めて改行する。
• クエリ2　splice により、L[t] の末尾に、L[s] をコピーする。L[s] は clear で空にする。

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

#include <iostream>
#include <list>

#include <vector>

using namespace std;

int main()
{
	int n, q;
	cin >> n >> q;

	vector<list<int>> L(n);

	for (int i = 0; i < q; ++i) {
		int command;
		cin >> command;
		if (command == 0) {
			int t, x;
			cin >> t >> x;
			L[t].insert(L[t].end(), x);
		} else if (command == 1) {
			int t;
			cin >> t;
			if (!L[t].empty()) {
				for (auto it = L[t].begin(); it != L[t].end(); ++it) {
					if (it != L[t].begin()) {
						cout << " ";
					}
					cout << *it;
				}
			}
			cout << endl;
		} else if (command == 2) {
			int s, t;
			cin >> s >> t;
			L[t].splice(L[t].end(), L[s]);
			L[s].clear();
		}
	}

	return 0;
}

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

最後に

この機能（splice）は、この問題を解くまで知りませんでした。問題を通して、新しい機能が学べて良かったです。

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