백준 8987 수족관 3 (KOI 2013 고등부 4)

수족관 3

8987번: 수족관 3

굉장히 재미있는 문제 같다.

한참 전부터 풀고 싶었는데, 아무리 검색해도 풀이가 나오지 않아서 해멨다.

겨우겨우 물어가며 결국 풀어내서 참 기쁘다.
나처럼 풀이가 궁금할 누군가를 위해 풀이를 작성함

---

목차
1. 문제 요약
2. 발상
3. 풀이
4. 코드

---

1. 문제 요약

그림 2. 수족관의 처음 상태. 물의 양은 26L이고 구멍은 2개.

위가 뻥 뚫린 단순직각다각형 모양의 수족관이 있다.

처음에 물이 가득 차있다.

 

X축 방향의 바닥들 중 K개를 골라서 구멍을 뚫는다.

이 때 배출되는 물의 양을 최대화 하여라.

 

꼭짓점의 개수 4 ≤ N ≤ 300,000

구멍의 개수 1 ≤ K ≤ N/2

 

2. 발상

이 문제가 풀이가 좀 여러 가지인 듯 하다.

가장 쉽게 떠오르는 풀이를 기준으로 적는다.

 

단계별로 어떤 생각을 해야 하는지 적었다.

1)

구멍을 한개 뚫는다고 생각해보자.

그러면 위의 그림에서, 1번에 뚫는 것보다 2번에 뚫는 것이 반드시 좋다.

왜냐하면 2번에 뚫어서 배출되는 물의 집합은 1번에서의 집합을 포함하기 때문이다.

 

즉, 깊숙한 곳에 뚫을 수록 어차피 위의 것들은 다 빠지기 때문에 반드시 유리하다.

 

2)

그런데 깊숙한 곳에만 뚫는다고 능사가 아니다.

왜냐하면, 2번에 구멍을 뚫는다면 1번의 오른쪽 아래 부분의 물은 빠지지 않기 때문이다.

 

이를 조금 더 생각해보면, 1번을 중심으로 왼쪽 or 오른쪽 둘 중 하나의 부분만 뺄 수 있음을 파악할 수 있다.

물론 1번에서 뚫었을 때의 집합은 반드시 포함된다.

 

1번 이 중심이 된 이유는, 그곳이 제일 높기 때문이다.

즉 가장 높은 곳을 중심으로, 구멍을 한개 뚫는다면 왼쪽 혹은 오른쪽을 선택하여야 한다.

이것을 재귀적으로 반복할 수 있다. (DnC 느낌?)

 

3)

높이가 높은 곳을 기준으로 갈라져야 하기 때문에, Cartesian Tree를 생각할 수 있다.

간단하게 부모로 올라갈수록 커지는 Binary tree 라고 할 수 있다

따라서 루트는 가장 큰 놈(가장 높은 놈)이 될 것이다.

 

그림으로 나타나면 아래와 같다.

카르테시안 트리 구성

그러면 구멍 하나를 뚫을 때 배출되는 물의 양은, 그 노드부터 루트까지 쭉 올라가면서 있는 물의 양의 합이다.

그렇다면 구멍을 K개 뚫으려면 어떻게 뚫는 것이 가장 좋을까?

 

4)

놀랍게도, 그때 그때 가장 많은 물을 뺄 수 있는 구멍을 뚫는 것이 greedy하게 좋다.

 

K=1은 자명

K=2일 때도 잘 생각해보면 성립한다.

- 만일 최적의 해에, 맨 처음에 가장 많은 물을 뺄 수 있는 구멍이 포함되어 있지 않다면 : 임의의 구멍을 그 구멍으로 바꾸면 이득이다.

* 수정(2023-02-05): 생각해보니 이건 아닌것 같네요. "임의의" 구멍이 이득은 아니고,

  최적 해에 포함된 구멍들 중 "맨 처음에 가장 많은 물을 뺄 수 있는 구멍" 과의 LCA가 가장 낮은 구멍을 바꿔야 이득입니다.

  두 구멍 중 어느 것을 택하더라도 LCA보다 같거나 높은 node들은 항상 선택되기 때문에, 그 아래쪽 node들의 합이 더 큰 것이 유리할텐데, 이는 가정에 의해 "맨 처음에 가장 많은 물을 뺄 수 있는 구멍"이 더 크기 때문입니다.

 

잘 생각해보면 K가 임의의 수 일때도 위의 논리가 성립한다. (맨 처음 구멍에 대해서는)

 

두 번째 구멍부터는, 처음에 구멍을 뚫은 노드부터 루트까지를 전부 0으로 바꿔주면 동일하게 생각할 수 있다.

 

3. 풀이

1) 입력을 야무지게 받음

2) 그거로 Cartesian tree를 잘 구성

 

3) 오일러 투어를 돌아 트리를 쫙 펴준다.

하면서 루트 ~ 자신 을 합한 값: sum도 따로 저장해주자.

 

4) sum 배열로 max 세그를 만들자.

5) sum 배열 중 가장 큰 값을 골라, 답에 더해주자.

그리고 부모로 쭉 올라가면서 물의 양을 0으로 바꿔주자.

이를 K번 반복하자.

 

어떤 노드의 물의 양을 0으로 바꾸면, sum 배열에서 영향받는 부분은 그 노드의 서브트리이다.

따라서 오일러 투어를 통해 얻은 구간에다가 변화량을 뿌려주면 된다.

즉 레이지도 필요하다.

 

시간복잡도: $\mathcal{O}(N\log N)$

Cartesian Tree 구성: O(N)

오일러 투어 + sum 배열: O(N)

가장 큰 값 고르기: O(K lgN)

부모들을 0으로 바꾸기: O(N lgN) ← 어차피 한 노드를 0으로 바꾸는 행위는 각 노드당 최대 1번 일어나면 충분하다.

 

4. 코드

https://www.acmicpc.net/source/49042740

int main() {
	memset(ed,-1,sizeof(ed));

	n = n/2-1;
	par[0] = 0;
	for(int i=0, r,xx,yy,x,y;i<n;i++) {
		cin>>x>>y;
		cin>>xx>>yy;

		arr[i]={y,{x,xx}};
		if(!i) continue;

		for(r=i-1; arr[r].height > y; r=par[r]) ;

		if(y is new minimum) {
			ed[i].left_child=r, par[r]=par[i]=i;
		}
		else {
			if(ed[r].right_child exists) par[ed[i].left_child = ed[r].right_child] = i;
			par[i] = r;
			ed[r].right_child = i;
		}
	}

	for(int i=n;i--;) if(i==par[i]) make_cartesian_tree();

	for(int i=n;i--;) tmp[vis[i]]=sum[i];
	memcpy(sum, tmp, sizeof(sum));
	segment_tree.init(n, sum);

	for(int i=n;i--;) tmp[vis[i]]=i;
	memset(vis,0,sizeof(vis));

	ll ans=0;
	for(;k--;) {
		ans += segment_tree.get_max();
		int t = segment_tree.idx_of_max();
		for(t=tmp[t]; !vis[t]; t=par[t]) {
			vis[t]=1;
			segment_tree.update(range[t], -water[t]);
		}
	}
	cout<<ans;
}

void make_cartesian_tree(int now) {
	water[p] = amount of "now" water
	sum[p] = amount of total water

	range[p].first = vis[p] = cnt++;
	make_cartesian_tree(left_child);
	make_cartesian_tree(right_child);
	range[p].second = cnt-1;
}