AOJ ITP2 3_D（Lexicographical Comparison）を解く

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

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

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

問題（3_D: Lexicographical Comparison）

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

AOJ ITP2 3_D問題: Lexicographical Comparison

辞書式順序で比較する lexicographical_compare について学びます。

std::lexicographical_compare について

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

std::lexicographical_compare は、2つのイテレータ範囲を辞書式順序で比較します。

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

「辞書式順序」とはなんでしょうか。動きは以下のコードと等価になるようです。

• 真に前者が小さい場合に true を返す。同じ場合は、false を返す。
• イテレータ範囲の長さが合わない場合、短い方を小さいと判断する。

for ( ; first1 != last1 && first2 != last2 ; ++first1, ++first2) {
  if (*first1 < *first2) return true;
  if (*first2 < *first1) return false;
}
return first1 == last1 && first2 != last2;

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

与えられた2つの数列が与えられます。2つの数列を辞書式順序で比較して、後者の数列の方が大きい場合は 1 を、前者の数列の方が大きい場合は 0 を出力します。

基本的に lexicographical_compare を呼び出すだけです。以下は、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 (lexicographical_compare(a.begin(), a.end(), b.begin(), b.end())) {
		cout << 1 << endl;
	} else {
		cout << 0 << endl;
	}

	return 0;
}

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

最後に

この機能（lexicographical_compare）は、この問題を解くまで知りませんでした。このライブラリ関数を学ぶことで、辞書式順序について理解を深めることができました。

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