AOJ ITP2 6_D（Equal Range）を解く

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

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

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

問題（6_D: Equal Range）

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

AOJ ITP2 6_D問題: Equal Range

lower_bound と upper_bound を組にして返す equal_range について学びます。

std::equal_range について

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

std::equal_range は、ソート済みイテレータ範囲を与えて、lower_bound と upper_bound の結果を組で返します。

  template <class ForwardIterator, class T>
  pair<ForwardIterator, ForwardIterator>
    equal_range(ForwardIterator first,
                ForwardIterator last,
                const T& value);

この関数は、[first , last) の範囲で二分探索を行い、指定された値 value に対して、lower_bound の結果と upper_bound の結果を pair にして返します。

最大で、2 × log2 (last – first) + O(1) 回の比較を行います。計算量的には、lower_bound と upper_bound をそれぞれ呼び出す場合と変わらないようです。

6-C で学んだ lower_bound でも紹介しましたが、upper_bound から lower_bound を引くと、value と一致している要素の個数を求めることができます。

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

与えられた数列 A に対して、「クエリとして与えられた値 k の lower bound とupper bound の組を求めてください」と問題文でなっています。

イテレータを要素の個数に変換するために a.begin() を引いて出力しています。この差を計算すると value と一致する個数が分かります。

以下は、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 q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		int t;
		cin >> t;
		auto result = equal_range(a.begin(), a.end(), t);
		cout << result.first - a.begin() << " " << result.second - a.begin() << endl;
	}

	return 0;
}

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

最後に

この機能は、この問題を解くまで知りませんでした。

実際に lower_bound と upper_bound を両方呼び出すことがあります。その場合に、使ってみようと思います。忘れているかもしれませんが。

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