AOJ ITP2 1_A（Vector）を解く

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

ITP2では、「プログラミングのための基礎ライブラリを獲得します」とあります。トピック#1では、動的配列とリストを学びます。

問題（1_A: Vector）

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

AOJ ITP2 1_A問題: Vector

Vector コンテナについて学びます。

Vector コンテナについて

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

概略

C/C++ の言語定義に含まれる配列に近い機能を提供します。

• 各要素は連続して配置される。
• 配列と同じく、添え字によって要素にアクセスできる。
• 可変長で、自動的に領域の拡張が行われる。

主なメソッド

よく使われるメソッドを紹介します。

言語定義に含まれる配列と同じで、途中の要素に挿入したり、削除する操作は速くはありません。これは、影響がある要素以降の要素すべてについて波及的に操作をする必要があるためです。

一方、末尾要素への追加、削除は影響を受ける要素がないため、速く動作します。

C++ プログラム例（ITP2 1_A）

問題で与えられるクエリに従い、以下の操作を行います。

• クエリ0　push_back により、与えられた x を末尾に挿入する。
• クエリ1　与えられた p に対して、A[p] を出力する。
• クエリ2　pop_back により末尾の要素を削除する。

Vetcor コンテナで提供されているメソッドを、クエリに従い呼び出します。以下が、C++プログラムとなります。

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<int> A;

	int q;
	cin >> q;

	for (int i = 0; i < q; ++i) {
		int command;
		cin >> command;
		if (command == 0) {
			int x;
			cin >> x;
			A.push_back(x);
		} else if (command == 1) {
			int p;
			cin >> p;
			cout << A[p] << endl;
		} else if (command == 2) {
			A.pop_back();
		}
	}

	return 0;
}

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

最後に

「プログラミング入門」（ITP1）をすべて解くことができました（まとめ記事）。続きとして、「プログラミング応用」（ITP2）を解くことにしました。

このコースの題材は、C++のライブラリを意識しているように思われます。そのため、C++で解くことにしました。

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