BOJ 24976 - Balancing a Tree

image.png

그냥 트리에서 어쩌다 저쩌다보면 맞을 수 있는 문제같다.

내 풀이말고 에디토리얼을 그냥 정리해보겠다.

li=ril_i=r_i

이 경우엔 모든 노드에 대해 조상의 가장 작은 값과 가장 큰 값을 계속 관리해 O(n)O(n)으로 풀 수 있다.

B=0B=0

정답의 lower bound를 고려한다.

어떤 자손 조상인 i,ji, j 에 대해 다음과 같은 식이 성립한다.

answerMax(Maxi,j,related(0,liri),MaxiliMiniri2) \text{answer} \ge \text{Max}\left( \text{Max}_{i,j,\text{related}} (0, l_i-r_i), \left\lceil \dfrac{\text{Max}_i l_i-\text{Min}_ir_i}{2} \right\rceil \right)

일단 뒤에 \left\lceil \right\rceil 부분은 어떤 ii 중 가장 작은 lil_i 와 어떤 ii중 가장 큰 rir_i 의 차이의 절반보다는 항상 커야하므로 옳다.

항상 i1ji \to 1 \to j 를 고려하면 그렇다. 따라서 이 경우는 i,ji,j가 조상-자손 관계가 아니여도 된다.

전자는 조상 li,ril_i, r_i 과 자손 lj,rjl_j, r_j 가 구간이 겹치지 않는다면 그 차만큼보다 정답은 커야하므로 옳다.

이 lower bound가 정답임을 항상 구성할 수 있고 아래서 설명된다.

B=1B = 1

R=MiniriR=\text{Min}_i r_i 라 하고 L=MaxiliL=\text{Max}_i l_i 라 하고 M=L+R2M=\left\lfloor \dfrac{L+R}{2} \right\rfloor라 한다.

모든 ii에 대해 Wi=Max(li,Min(M,ri))W_i=\text{Max}(l_i, \text{Min}(M, r_i)) 를 두는 정답이 항상 성립한다.

만약 RLR \ge L 이라면 정답은 항상 00 이다.

그렇지 않다면 모든 ii에 대해 WiMLR2\vert W_i-M \vert \le \left\lceil \dfrac{L-R}{2} \right\rceil 임을 관찰한다.

어떤 조상-자손 관계인 i,ji,j 에 대해 Max(Wi,Wj)M\text{Max}(W_i, W_j) \le M 이라면

WiWjLR2answer\vert W_i-W_j \vert \le \left\lceil \dfrac{L-R}{2} \right\rceil \le \text{answer} 에 의해 옳다.

유사하게 Min(Wi,Wj)M\text{Min}(W_i, W_j) \ge M 일 때도 성립한다.

Wi>M, Wj<MW_i > M,~ W_j < M 이라면 Wi=liW_i=l_i 이고 Wj=rjW_j=r_j 이므로 WiWj=lirjanswer\vert W_i-W_j \vert = l_i-r_j \le \text{answer} 라서 성립한다.

솔직히 뭔말인지 모르겠다;

Tags:

Categories:

Updated:

Comments