AOJ ITP2 6_B（Includes）を解く

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

ITP2では、「プログラミングのための基礎ライブラリを獲得します」とあります。トピック#6では、「二分探索」というテーマで学びます。

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

問題（6_B: Includes）

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

AOJ ITP2 6_B問題: Includes

一方の範囲の要素がもう一方の範囲に含まれているか判定する includes について学びます。

std::includes について

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

std::includes は、ソート済みイテレータ範囲において、一方の範囲の要素がもう一方の範囲に含まれているか判定します。

  template <class InputIterator1, class InputIterator2>
  bool includes(InputIterator1 first1,
                InputIterator1 last1,
                InputIterator2 first2,
                InputIterator2 last2); 

[first1, last1) と [first2, last2) は、どちらもソートされている必要があります。[first2, last2) の全ての要素が [first1, last1) に含まれている場合は true を、そうでない場合は false を返します。

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

C++ プログラム例（ITP2 6_B）

数列 B の要素が数列 A に含まれているか判定します。includes をそのまま使う問題になっています。

以下は、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];
	}

	if (includes(a.begin(), a.end(), b.begin(), b.end())) {
		cout << 1 << endl;
	} else {
		cout << 0 << endl;
	}

	return 0;
}

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

最後に

この機能は、この問題を解くまで知りませんでした。使わない機能は忘れてしまいそうですが、ぴったりと使える場合があればと思います。

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