AOJ ITP2 4_B（Rotate）を解く

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

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

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

問題（4_B: Rotate）

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

AOJ ITP2 4_B問題: Rotate

要素の並びを回転させる rotate について学びます。

std::rotate について

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

std::rotate は、指定された範囲の要素の並びを回転します。

  template <class ForwardIterator>
  void
  rotate(ForwardIterator first,
         ForwardIterator middle,
         ForwardIterator last);  // C++03

  ForwardIterator
  rotate(ForwardIterator first,
         ForwardIterator middle,
         ForwardIterator last);  // C++11

middle の要素を先頭に、middle – 1 の要素を末尾になるようにイテレータ範囲の要素並びを回転させます。左回転をしていると考えることができます。

具体的には、0 以上 last – first 未満の整数 i について、first + i の要素を
first + (i + (last – middle)) % (last – first) の位置へ移動します。最大で last – first 回の swap を行います。

C++03 では、戻り値がありませんでした。C++11 から回転前の要素を指すイテレータ
first + (last – middle) を返すように仕様変更されました。

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

配列 A が与えられて、q 個の操作が与えられます。1回の操作で指定された範囲の rotate を行います（21行目）。最後に A を出力します。

以下は、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 b, m, e;
		cin >> b >> m >> e;
		rotate(a.begin() + b, a.begin() + m, a.begin() + e);
	}

	for (int i = 0; i < n; ++i) {
		cout << a[i] << " \n"[i == n - 1];
	}

	return 0;
}

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

最後に

rotate は、この問題を解くまで知りませんでした。rotate は、イテレータで指定された範囲内の swap を行うだけで実現できるようです。

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