FORTRESS(要塞)

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

最も壁を越える必要がある2つの点

一つの城には他の城が含まれることができ、城の間に重なり合ったり接触したりできない条件は、木で入力された城として表現するように大胆に誘導されているようだ.
問題は、複数の城の中で最も壁を越える必要がある2つの場所を見つけることです.
まず与えられた城を木で表現し、木を巡視し、木の対象ごとに高さを保存し、その高さを利用して答えを求めることはできないのではないかと考えました.
各ツリーノードの高さを求めて単独で保存し、最下部の高さが0のリーフノードから親ノードを遡ってアクセスし、既存の高さに1を追加して保存し、すべてのノードを1回だけ巡回すればよい.この過程はO(N)の時間的複雑さで達成できる.

外壁を基準に、この城が最も壁を越える必要がある2つの場所がどれだけの壁を越えることができるかを数えると、外壁の直系子孫の間で高さを増やすのが直観的に最適なようだ.
外壁の直系子孫の高さも、その城の最奥の城から城を越え始めた時の値と見なすことができるので、各直系子孫の間にペアを組んで並び、互いの高さを合わせると答えが見つかるはずです.
(正確には、2つの直系子孫の高さの和に加えて2が最大の城壁を正確に越える答えですが、具体的な部分を考えるとすべての論理を設計するのは効率的ではないので、詳細な計算式は省略し、高さを利用して答えを探す方法に焦点を当てました)
 
そこで,根の高さ(外壁の高さ)を初期retとし,膝下のすべての子を対にして高さの和を求めるとき,最大のMax値を戻り値とするようにコードを実現した.ret = max(ret, 루트의 직계자손들 중 두 쌍의 높이 합)このとき最初のretは根の高さに入り,すべての直系子孫の2対の状況がすべて確認されるまでret更新を繰り返す.
ルートの直系子孫を2対ペアリングするためには,すべてのサブ候補が最大n個と自己ペアリングのサブ候補n−1個を結合する必要があるため,総(n*(n−1)/2)回計算する必要がある.したがって,このプロセスは最大O(N^2)の時間的複雑さを消費する.
 
しかし、この方法には脆弱性があります.
外壁の直系の子供たちの中で最大の城壁を越える答えがある場合だ.

したがって,外壁直系子孫間の2対の高さの和を確認するだけでなく,直系子孫内部に最大値に達する2対の姓が存在するかどうかを確認するため,直系子孫内部ごとに最大の壁を越えて買い求める過程に戻る.これは外壁の膝の下のすべての直系子孫を別の外壁ルートと見なし、この城内で壁をひっくり返して購入する過程を繰り返していればよい.
既存の最大壁を越える論理は全O(N^2)の時間的複雑度を必要とし,最大Nサブシステムは最大壁を越える過程を繰り返す必要があるため,最終的な時間的複雑度はO(N^3)である.
このとき入力したNの最大値は100なので、O(N^3)は完全に解決できる線です.

ツリーの実装

入力で与えられた最初の城壁は根です.したがって,最初の入力をルートとし,最初にツリーを生成する.次に入力するノードN−1個は、これまでに作成したツリーを1個ずつループし、ターゲット入力ノードがツリーのどの位置に入るべきかを判断し、適切な位置に挿入すればよい.
このとき、入力ノードの適切な位置を検索するプロセスは、これまでに作成したツリーのルートの直系サブノードから開始し、残りのすべてのノードにアクセスするときに行われます.ツリーを巡回するときに、入力ノードとアクセスノードの包含関係を決定します.
すべてのルートの直系サブノードと入力ノードの包含関係が見つからない場合、その入力ノードはルートの新しい直系サブノードになります.
逆に,包含関係が確認されると,二つのケースに分けられる.
入力ノードにターゲットルートの直系サブノードが含まれている場合、逆にルートの直系サブノードに入力ノードが含まれます.
前者は,既存のルートの直系サブノードが入力ノードのサブノードとして入り,入力ノードがルートの新しい直系サブノードに変換され,挿入が終了する.
後者はルートの直系サブノードの内部をナビゲートする必要があるため、現在のターゲットルートの直系サブノードが新しいルートになり、入力ノードの挿入が再び終了するまで、上記の手順を再帰的に繰り返しなければならない.
最終的に、入力ノードは、最大N個のノードを巡回して挿入位置を決定することができるので、ノードを挿入する際に、適切な位置を探すプロセスは、最大O(N)の時間的複雑さを必要とする.挿入する場所が見つかれば,挿入ノード自体はノードへの親ノードと子ノードへのポインタを再変更するだけで,O(1)定数時間で問題を解決できる.
したがって,ツリーを作成するプロセスには,n−1入力ノードが最大n回の探索(n−1)*n=O(n^2)を行う時間的複雑さが必要である.

コード#コード#

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

using namespace std;

struct tree {
	int height;
	int x, y, r;
	tree* parent;
	vector<tree*> children;

	int get_height(tree* root) {
		int h = 0;
		for (int i = 0; i < root->children.size(); i++) {
			h = max(h, 1 + get_height(root->children[i]));
		}
		root->height = h;
		return h;
	}
};

int sqr(int x) {
	return x * x;
}

//포함관계가 없을 때 0, node1 > node2 일때 1, node1 < node2 일때 2
int judge_relation(tree* node1, tree* node2) {
	int dist = sqr(node1->x - node2->x) + sqr(node1->y - node2->y);

	if (node1->r > node2->r && dist < sqr(node1->r - node2->r)) return 1;
	else if (node1->r < node2->r && dist < sqr(node1->r - node2->r)) return 2;
	else return 0;
}

void makingTree(tree* root, tree* node) {
	for (int i = 0; i < root->children.size(); i++) {
		int judge = judge_relation(node, root->children[i]);
		if (judge) {
			if (judge == 1) {
				node->children.push_back(root->children[i]);
				node->parent = root;
				root->children[i]->parent = node;
				root->children[i] = node;
				return;

			}
			else if (judge == 2) {
				makingTree(root->children[i], node);
				return;
			}
		}
	}

	int judge = judge_relation(root, node);
	if (judge) {
		root->children.push_back(node);
		node->parent = root;
	}
}

int fortress(tree* root, int ret) {
	// O(N^2)
	for (int a = 0; a < root->children.size(); a++) {
		for (int b = a + 1; b < root->children.size(); b++) {
			ret = max(ret, root->children[a]->height + root->children[b]->height + 2);
		}
	}
	// O(N^3)
	for (int i = 0; i < root->children.size(); i++) {
		ret = max(ret, fortress(root->children[i], ret));
	}

	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int testcase;
	cin >> testcase;
	while (testcase--) {
		int n;
		cin >> n;

		vector<int> temps;
		temps.reserve(3);
		for (int i = 0; i < 3; i++) {
			int temp;
			cin >> temp;
			temps.push_back(temp);
		}
		// 주어진 입력으로 트리 만들기 O(N^2)
		tree root{ 0, temps[0], temps[1], temps[2] };
		for (int i = 0; i < n - 1; i++) {
			temps.clear();
			for (int i = 0; i < 3; i++) {
				int temp;
				cin >> temp;
				temps.push_back(temp);
			}
			tree* node = new tree{ 0, temps[0], temps[1], temps[2] };
			makingTree(&root, node);
		}
		//각 노드의 height 구하기 O(N)
		root.get_height(&root);

		int ret = fortress(&root, root.height);
		cout << ret << "\n";

		cout << "hi";
	}
	return 0;
}

覚えたいこと

ツリーのルートのみをスタックに格納し、残りのルートの子はnew演算子によってhipメモリに動的に割り当てられます.
しかし,動的に割り当てられたサブノードは領域関数の1つのポインタのみで制御されるため,ターゲットノードがツリーに1回格納された後にターゲットノードを離れる場合,そのノードを参照する方法は存在しない.
ルートノードからのみ、サブノードに従って参照にアクセスできます.
したがって、これらの動的に割り当てられたツリーオブジェクトを後で再削除するのは面倒です.
もちろん、1つ1つ循環して、1つずつメモリから解放すればよいのですが、本当に最適化のために再実施することを提案すると、面倒になります.
この問題のテストケース数と入力ノードは少なく、メモリを解放しなくても正解が得られますが、後でこの点に問題が発生するに違いありません.それを覚えておきたい.
また、木の最大の経路を探す本の答えも知るべきだ.木の最大経路を探して以降もよく使うので注意して見てください.
そして、本の中では高さと最大の2組を探すために、私のように2重にドアを開けず、すべての城の高さを簡単に揃えた後、最後の2つの要素を取り出します.
従って、すべてのn個のノードについて、O(NxlgN)のソートに使用される時間の複雑さは、O(N^2 xlgN)である.
私のアルゴリズムでは,2対の高さの和が最も大きいのはO(NxlgN)ではなくO(N^2)であることを探しているので,時間全体の複雑さはO(N^3)である.ソートというアイデアを覚えたいです.
最後の雑談として、初めて木を実現するのに時間がかかり、データ構造を直接実現し、問題を解決するのも良い経験だと思います.