BOJ 24976 - Balancing a Tree
그냥 트리에서 어쩌다 저쩌다보면 맞을 수 있는 문제같다.
내 풀이말고 에디토리얼을 그냥 정리해보겠다.
$l_i=r_i$
이 경우엔 모든 노드에 대해 조상의 가장 작은 값과 가장 큰 값을 계속 관리해 $O(n)$으로 풀 수 있다.
$B=0$
정답의 lower bound를 고려한다.
어떤 자손 조상인 $i, j$ 에 대해 다음과 같은 식이 성립한다.
일단 뒤에 $\left\lceil \right\rceil$ 부분은 어떤 $i$ 중 가장 작은 $l_i$ 와 어떤 $i$중 가장 큰 $r_i$ 의 차이의 절반보다는 항상 커야하므로 옳다.
항상 $i \to 1 \to j$ 를 고려하면 그렇다. 따라서 이 경우는 $i,j$가 조상-자손 관계가 아니여도 된다.
전자는 조상 $l_i, r_i$ 과 자손 $l_j, r_j$ 가 구간이 겹치지 않는다면 그 차만큼보다 정답은 커야하므로 옳다.
이 lower bound가 정답임을 항상 구성할 수 있고 아래서 설명된다.
$B = 1$
$R=\text{Min}_i r_i$ 라 하고 $L=\text{Max}_i l_i$ 라 하고 $M=\left\lfloor \dfrac{L+R}{2} \right\rfloor$라 한다.
모든 $i$에 대해 $W_i=\text{Max}(l_i, \text{Min}(M, r_i))$ 를 두는 정답이 항상 성립한다.
만약 $R \ge L$ 이라면 정답은 항상 $0$ 이다.
그렇지 않다면 모든 $i$에 대해 $\vert W_i-M \vert \le \left\lceil \dfrac{L-R}{2} \right\rceil$ 임을 관찰한다.
어떤 조상-자손 관계인 $i,j$ 에 대해 $\text{Max}(W_i, W_j) \le M$ 이라면
$\vert W_i-W_j \vert \le \left\lceil \dfrac{L-R}{2} \right\rceil \le \text{answer}$ 에 의해 옳다.
유사하게 $\text{Min}(W_i, W_j) \ge M$ 일 때도 성립한다.
$W_i > M,~ W_j < M$ 이라면 $W_i=l_i$ 이고 $W_j=r_j$ 이므로 $\vert W_i-W_j \vert = l_i-r_j \le \text{answer}$ 라서 성립한다.
솔직히 뭔말인지 모르겠다;
Comments