FENCE(垣根のトリム)

(ソース)https://www.algospot.com/judge/problem/read/FENCE

完全ナビゲーションの場合:

N個の所与の格子が入力されると、0番格子からN番格子まで全ての格子が基準格子となり、基準自体よりも高い格子が出現する前に周囲の格子を探索し、探索を行った回数に自身の高さを乗じて記憶する.全ての柵の高さが同じであればN個の柵は毎回N回探索するので時間的複雑度はO(N^2)である.問題で与えられる最大柵数は2万個であるため,O(n^2)時間複雑度は2万X 2万=4億程度の計算が必要である.1秒で4億回の繰返し計算を行うとタイムアウトする可能性があるため、より高速なアルゴリズムの設計が必要です.

より速いアルゴリズムが必要です

与えられたグリッドの総数にかかわらず、すべてのグリッドセットは、上の図のようにA領域とB領域を半分に分けることができる.そして、私たちが得たい答えは3つの状況に存在しなければなりません.答えがA領域に存在する場合、答えがB領域に存在する場合、答えはAおよびB領域に存在する.したがって,3つの場合ごとにそれぞれ最大値を求め,次に最大値を抽出することで,正解を正確に解くことができる.
1つのフェンス領域を半分に分けて表すAとB領域も同様の論理でさらに半分に分けることができる.すなわち、A領域は、前の問題の一部として再帰的にこの動作を継続することができる別のA"およびB"領域に分割することもできる.この場合,基板ケースはこれ以上半分に分けることができず,この分野には1つの柵しか存在しない.
このとき,我々が要求するAのみを切除すると,答えとBのみを切除する答えは最終的に再帰的な部分問題の戻り値となる.すなわち,1回の再帰関数内でこれらの2つを計算するのに要する時間は,再帰関数や局所問題を解く時間にのみ依存し,再帰呼び出し以外の関数の残りの部分の実行時間をO(N)として解決するだけであればよい.このアルゴリズムの時間的複雑さは再帰関数の全深さxN反復として決定できる.再帰関数の総深さは,N個のフェンスを分割できなくなるまで半分の回数=logn(底:2)に分割できるので,最終的にはこの問題をO(N*logn)にまとめることができる.要するに、O(N)以下の時間的複雑度で、A,Bを全て切除する方法を求めればよい.

AとBを切除する方法

A領域とB領域の間で垣根を剪定するには、A領域の最も右側の垣根とB領域の最も左側の垣根を計算に含める必要があります.含まなければならない2つの固定グリッドを起点として、左ポインタと右ポインタを移動し、グリッドの面積を増やします.このとき注意すべき点は,領域拡張に対して,左右のポインタを選択する際に条件が存在することである.左か右かを先に選ぶ条件です.
上の図の1番の状態から2番の状態に拡張すると、左側のポインタが高さ8を指すグリッドと、右側のポインタが高さ4を指すグリッドで、より高い左側のグリッドが選択されていることがわかります.領域を拡張する場合は、常に高さの大きいフェンスを優先します.これは,領域内の最低高さ(LOW)グリッドを基準として領域に存在するグリッド数(Count)を乗じ,2つのグリッドの中でまず高さの小さいグリッドを選択すると,選択されていないグリッドをLowとして完全に省略するためである.
すなわち、上図の2番目の図では、まず高さ8の格子ではなく高さ4の格子を選択して領域拡張を行うと、Lowが8の場合に得られる答えは完全に省略される.Lowは領域拡張を行うと現在のLowよりも低い高さのフェンスに変わり続けるため、2つのフェンスを選択する場合は高さの高いフェンスを優先的に選択する必要がありますが、可能なすべてのLowをチェックすることができます.
上記のように全ての存在するフェンスをループし、最も高いTempmax値を選択すれば、NサイクルでAとBの剪断が可能となる.
要するに,各深さの再帰関数は合計N反復を実行し,この問題の再帰関数の総深さはlog N個であるため,アルゴリズムの総時間複雑度はO(N*logN)である.

コード#コード#

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int fence(vector<int> &board, int minNum, int maxNum) {
	int left, middle, right;
	if (maxNum - minNum == 1) return board[minNum];
	if (maxNum - minNum == 2) {
		left = board[minNum];
		right = board[maxNum - 1];
		if (board[minNum] > board[maxNum - 1]) middle = board[maxNum - 1] * 2;
		else middle = board[minNum] * 2;
		int ret = max(left, right);
		return ret = max(ret, middle);
	}
	
	int half = (minNum + maxNum) / 2;
	left = fence(board, minNum, half);
	right = fence(board, half, maxNum);
	//middle 구하기
	int low;
	int count = 2;
	if (board[half - 1] <= board[half]) low = board[half - 1];
	else low = board[half];
	middle = low * count;

	int left_p = half - 2;
	int right_p = half + 1;
	while (left_p >= minNum || right_p < maxNum) {
		//예외사항 처리
		if (left_p >= minNum && !(right_p < maxNum)) {
			if (board[left_p] >= low) {
				count++;
				middle = max(middle, (low * count));
				left_p--;
			}
			else {
				low = board[left_p];
				count++;
				middle = max(middle, (low * count));
				left_p--;
			}
		}
		else if (!(left_p >= minNum) && right_p < maxNum) {
			if (board[right_p] >= low) {
				count++;
				middle = max(middle, (low * count));
				right_p++;
			}
			else {
				low = board[right_p];
				count++;
				middle = max(middle, (low * count));
				right_p++;;
			}
		}
		//왼쪽과 오른쪽 어느쪽 선택할지 결정
		else {
			if (board[left_p] >= board[right_p]) {
				if (board[left_p] >= low) {
					count++;
					middle = max(middle, (low * count));
					left_p--;
				}
				else {
					low = board[left_p];
					count++;
					middle = max(middle, (low * count));
					left_p--;
				}
			}
			else {
				if (board[right_p] >= low) {
					count++;
					middle = max(middle, (low * count));
					right_p++;
				}
				else {
					low = board[right_p];
					count++;
					middle = max(middle, (low * count));
					right_p++;
				}
			}
		}
	}
	int ret = max(left, right);
	return ret = max(ret, middle);
}

int main() {
	int testcase;
	scanf("%d", &testcase);
	getchar();

	for (int i = 0; i < testcase; i++) {
		int n;
		scanf("%d", &n);
		vector<int> board(n);
		int temp_int;
		scanf("%d", &temp_int);
		board[0] = temp_int;
		for (int i = 1; i < n; i++) {
			scanf("%d", &temp_int);
			board[i] = temp_int;
		}
		int ret = fence(board, 0, n);
		printf("%d\n", ret);
	}

	return 0;
}

覚えたいこと

私が書いたコードはif条件を使ったので、同じコードを余計に繰り返し、長くなる面があり、本の中のコードを見て、きれいにif条件ですべての状況を完璧にコントロールしたことに驚きました.特に、if(A&(B|C)で条件文を書くことを覚えたい.
また,配列のインデックスを扱う場合,インデックス計算に多くの時間を費やすことが多く,半開区間を利用して抽象的に考えるだけで,誤りを減らし,余分な計算でよく考えることを減らす.
ベクトルを渡すときは,ポインタを使わずにベクトルそのものに渡し,関数内でベクトルを生成し続け,タイムアウトが発生し,これを見つけるのに時間がかかった.後でビッグデータを渡すときは一度注意してください.