BOJ 17261 - 석유가 넘쳐흘러

BOJ 17261 - 석유가 넘쳐흘러

Observation

이진 트리의 특성상 모든 조상을 $O(\log N)$에 순회 할 수 있다.

부모에게서 석유가 흘러올 때, 항상 채우려는 노드 쪽으로 석유를 흘려주는 것이 최적이다.

$wlog.$ 내가 왼쪽 자식인데, 부모에게서 흘러오는 석유를 오른쪽 자식에게 먼저 채워주고 오른쪽 자식의 석유들까지 내쪽으로 끌고와서 더 빠르게 될 수 있을까?

1초마다 부모에게서 오는 석유 $p$ 와 오른쪽 자식을 채우기까지 남은 유량 $r$과 오른쪽 자식이 가진 leaf node를 $l_r$ 이라고 하자.

$r$을 모두 채우는데는 $\dfrac {r}{l_r+p}$ 초가 걸린다. 모두 채우고는 왼쪽 노드에 초마다 $l_r+p$ 의 석유가 흘러들어온다.

$r$을 모두 채우기 전까진 왼쪽 자식으로 $p$를 그냥 흘려주는게 더 이득이므로 $r$을 채운 후에 특정 시점에 더 오른쪽으로 흘려준게 이득이 되는 시점이 있나 보자.

$(l_r+p) \cdot (t - \dfrac r{l_r+p})$ 이 $t$ 초가 지났을 때 왼쪽 자식으로 흘러들어가는 양이고,

왼쪽 자식으로만 흐른다고 가정하면

$tp + l_r \cdot (t-\dfrac r{l_r})=t(p+l_r)-r$

결국 다음과 같이 되어서

$(l_r+p) \cdot (t - \dfrac r{l_r+p})=t(p+l_r)-r$

왼쪽 자식으로 흘러들어가는 양은 같으므로 항상 채우려는 쪽으로 부모의 석유를 모두 대주는게 최적이다. $\square$

Solution

Parametric Search로 각 노드마다 흐른 시간 $t$를 잡고 자기 자식 노드에서 $t$ 만큼 지나면 얻어지는 석유와 모든 조상을 순회하며 자신쪽 말고 다른쪽이 $t$ 에 스스로 모두 채워질 수 있는지를 보고 채워진다면 남은 양만큼 자신쪽에 더해준다.

위에서 증명했듯이 그리디하게 다른쪽이 스스로 채워지고 모두 자기에게만 흘려야 최적이기 때문이다.

즉, 시간복잡도 $O(Nlog ^2N)$ 에 해결 가능하다.