競技プログラミングの鉄則 A10 - Resort Hotel

記事概要

競技プログラミングの鉄則 演習問題集のA10のとりあえず動くコードと説明．

注意

アルゴリズム初心者が書いてます．時間内の動作は確認してますが、必ずしも最適解ではないです．

とりあえずコード

A10_main.cpp

//////////////////////
// A10-Resort Hotel //
//////////////////////

#include <iostream>
#include <vector>
#include <algorithm>

using std::vector;

int main(void)
{
	//============================== 入力 ==============================//
	
	// 部屋数の入力
	int N;
	std::cin >> N;

	// 部屋ごとの収容人数の入力
	vector<int> room_capacity(N + 1);   
	room_capacity[0] = 0;
	room_capacity[0] = 0;				// 使わない部分は0で初期化
	for (int i = 1; i <= N; ++i) {
		std::cin >> room_capacity[i];
	}

	// 期間の入力
	int D;								// 期間
	std::cin >> D;

	// 工事範囲の入力(L：範囲の先頭 R：範囲の後尾)
	vector<int> L(D + 1), R(D + 1);
	for (int i = 1; i <= D; ++i) {
		std::cin >> L[i] >> R[i];
	}

	//=============================== 計算 ==============================//
	vector<int> P(N + 1), Q(N + 1);
	
	// Pを計算
	// Pの説明
	// P[i]は、部屋の収容人数の配列で、先頭から位置iまでの内の最大値をP[i]に格納する．
	P[1] = room_capacity[1];
	for (int i = 1; i <= N; ++i) {
		P[i] = std::max(room_capacity[i], P[i - 1]);
	}

	// Qの計算
	// Qの説明．
	// Pと同様だが、こっちはQ[i]に収容人数の配列の最後尾から位置iまでの内の最大値を格納する．
	Q[N] = room_capacity[N];
	for (int i = N - 1; i >= 1; --i) {
		Q[i] = std::max(room_capacity[i], Q[i + 1]);
	}

	// 答えの計算
	// 計算方法の説明
	// 使用可能な部屋を○、工事中の部屋を●で表すと、ある日Dのとき、
	// ○○○●●○○○○
	// のような配列の内、○の範囲内の最大値を調べたい．というのがA10の問題の趣旨である．
	// ここでPとQはそれぞれ位置iに左から、右から見ていった時の最大値を格納している．
	// つまり、○と●の境界の○の位置のPとQを調べ、比較した内の大きい方がある日Dの使用できる部屋の収容人数の最大値になる．
	vector<int> ans(D + 1);
	for (int i = 1; i <= D; ++i) {
		ans[i] = std::max(P[L[i] - 1], Q[R[i] + 1]);
	}

	//============================== 出力 ==============================//
	for (int i = 1; i <= D; ++i) {
		std::cout << ans[i] << std::endl;
	}
}

コード説明

コメントにほとんど書いていますが、説明．
配列Pは、部屋の収容人数room_capacityを先頭から見ていったとき、位置iまでに現れる最大値をP[i]に格納します．(なのでPの計算でP[i-1]とroom_capacity[i]の内大きい方をP[i]に格納いている)
同じく配列Qには、room_capacityを最後尾から見ていったとき、位置iまでに現れる最大値をQ[i]に格納する．

この問題は、下の図で白丸を使用可能な部屋、黒丸を工事中の部屋としたとき、白丸である2つの範囲内の最大値を調べたいというものである．ちょっと言い方を変えると、「先頭からL-1番目まで」と「最後尾からR-1番目まで」の範囲の内の最大値が欲しいということである．

ここでさっきのPとQを使う．P[L-1]には「先頭からL-1番目まで」の内の最大値が格納されており、Q[R-1]には「最後尾からR-1番目まで」のうちの最大値が格納されている．
つまり、P[L-1]とQ[R-1]のうち大きい方が、ある日Dの使用可能な部屋の最大の収容人数となる．

終わりに

最初の方は結構力ずくでどうにかなってましたがA10になってくときついですね．
あと、この手法になんか名前があったら教えてください．