AOJ ALDS1 1_D（Maximum Profit）を解く

Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の1_D問題をC++で解いてみました。

ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#1「入門」は、このコースの導入となっています。

問題（1_D: Maximum Profit）

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

AOJ ALDS1 1_D問題: Maximum Profit

計算量について学びます。

計算量について

この問題は、$R_j – R_i \;(j > i)$ の最大値を求める問題です。以下は、読み込んだ配列 r[i] に対して、すべての r[j] – r[i] を求めて、その最大値を求めます。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> r(n);
	for (int i = 0; i < n; ++i) {
		cin >> r[i];
	}

	int result = -1000000000;
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			result = max(result, r[j] - r[i]);
		}
	}

	cout << result << endl;

	return 0;
}

このプログラムを提出すると、TLE（Time Limit Exceeded）判定となります。n の最大値は、200,000 となっています。このプログラムのループ回数は、n * (n – 1) / 2 となり最大で約 2×10¹⁰ 回となります。

このプログラムの時間制限は1秒です。一般的なサーバで1秒間にできる計算は、10⁸ から10⁹ 回程度です。このため、上記プログラムは、TLE 判定となりました。

C++ プログラム例（ALDS1 1_D）

$R_j – R_i \;(j > i)$ の最大値を求めるために、すべての場合を計算することが難しいことが分かりました。

以下の工夫をします。

• それより前の時点でのr[i]の最小値 t_min を記憶しておく。
• r[i] – t_min の最大値を記憶する。

この工夫で結果的に r[j] – r[i] の最大値を求めることができます。この場合、ループ回数が n-1 回となり、時間に間に合います。以下が、C++プログラムとなります。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> r(n);
	for (int i = 0; i < n; ++i) {
		cin >> r[i];
	}

	int result = -1000000000;
	int t_min = r[0];
	for (int i = 1; i < n; ++i) {
		result = max(result, r[i] - t_min);
		t_min = min(t_min, r[i]);
	}

	cout << result << endl;

	return 0;
}

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

最後に

導入の最後として、計算量を意識する問題を紹介しました。少しの工夫で計算量を減らすことができました。

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