CERC 2013 Escape, JOISC 2017 Sparklers

CERC 2013의 Escape(https://www.acmicpc.net/problem/9539)와 JOISC 2017의 Sparklers(https://oj.uz/problem/view/JOI17_sparklers)를 풀어보자.

 

Escape는 다음과 같은 문제를 풀어야 한다.

트리의 1번 정점에서 시작하여 간선을 따라 움직인다. 처음 체력은 0이다. 각 정점 $i$을 처음으로 방문하면 $H_i$만큼 체력을 얻는다. $H_i<0$이면 $-H_i$만큼 체력을 잃는다. 체력이 음이 되지 않도록 유지하며 정점 $t$까지 갈 수 있는가?

1번 정점을 루트로 한 뒤 DFS를 돌며 트리의 형태를 간소화할 것이다. 그 아이디어를 얻기 위해 리프 노드부터 생각해보자. 리프 노드 $v$에 대해 $H_v<0$이면 $v$를 방문하지 않을 것이다. 따라서 $v$를 제거해도 된다. $H_v>0$이면 그대로 둔다. 이제 리프 노드 $v(H_v>0)$의 부모 노드 $u$를 생각하자. $u$의 자식은 $v$만 있다고 생각하자. $H_u<0$인 경우를 살펴보자. $H_u+H_v<0$이면 $u, v$를 제거한다. $H_u+H_v>0$이라면, $u$에 도달하면 $H_u+H_v$의 체력을 얻을 수 있는 셈이다. 대신 그러려면 $-H_u$만큼의 체력이 이미 있었어야 한다. 즉, "$c$ 이상의 체력이 있으면 $h$의 체력을 얻을 수 있다" 꼴이 되는 것이다.

 

이제 우리는 트리를 $v_1, v_2, ..., v_k$가 차례로 이어져있는 체인 형태로 바꿀 것이다.($v_i$는 $v_{i+1}$의 부모이고, $v_k$는 리프 노드이다.) 각 정점에는 $(c_{v_i}, h_{v_i})$의 정보가 들어있고, 이는 "$c_{v_i}$ 이상의 체력이 있어야만 $v_i$를 방문할 수 있으며 방문한 후에는 $h_{v_i}$의 체력이 생긴다."라는 뜻이다. ($c_i \geq 0, h_i>0$)

1. 리프 노드: $H_i<0$이면 제거, $H_i>0$이면 $c_i=0, h_i=H_i$

2. 여러 자식 체인 합치기 : 이 체인들에서 가능한 많은 체력을 얻어가고 싶다. 따라서 현재 hp $\leq c_i$이면 무조건 그 정점에 들어가서 $h_i$의 체력을 얻을 것이다. 모든 $h_i$가 양수이기 때문에 갈수록 $c_i$가 큰 정점도 방문할 수 있을 것이다. 따라서 $c_i$가 작은 정점부터 방문하다가, 더 이상 들어갈 수 있는 정점이 없으면 멈출 것이다. 따라서 여러 체인 중 $c_i$가 가장 작은 것이 위로 오도록(루트에 가깝도록) 하면서 차례로 합쳐주면 된다.

3. 부모 노드 $u$ 추가하기 : $H_u >0$이라면 $(0, H_u)$를 추가한다. 만약에 체인의 첫 번째 정점 $v_1$에 대해 $c_{v_1} < H_u$라면, $u$를 방문하며 얻은 체력을 이용하면 $v_1$에도 무조건 들어갈 수 있다. 따라서 $u$와 $v_1$을 합쳐준다. $H_u<0$이라면, $(-H_u, H_u)$를 만든 뒤 $u$에 $v_1$을 합쳐준다. 그러면 $c = max(c_u, c_{v_1}-h_u), h=h_u+h_{v_1}$이 된다. $h_u>0$이 될 때까지 이 과정을 반복한다. 만약 체인의 모든 정점을 합쳤는데도 $h_u<0$이라면, 이 서브트리에서는 양의 체력을 얻을 수 없다는 것이므로 지워준다. 

 

문제에서 원하는 답을 구하기 위해서는 정점 $t$가 제거되지 않도록 해야한다. 따라서 $H_t$에 충분히 큰 수를 더해주면 된다. 여기까지 하면 답을 구할 수 있다. 그러나 여러 체인을 합치는 과정(2)이 $O(N)$이어서 총 시간복잡도가 $O(N^2)$이 된다. 따라서 체인에 한 가지 성질을 추가하자. $c_{v_i} < c_{v_{i+1}}$의 조건을 추가해주면 multiset 등을 활용해 $O(Nlog^2N)$에 답을 구할 수 있다. 이 조건을 추가하는 것이 가능하다는 것을 보이기 위해 $c_{v_i} > c_{v_{i+1}}$인 경우가 필요하지 않음을 보이자. $c_{v_i} > c_{v_{i+1}}$이라면, $v_i$를 방문한 후의 체력은 $c_{v_i}+h_{v_i}$ 이상일 것이다. $c_{v_i}+h_{v_i}\geq c_{v_{i+1}}$이므로 $v_{i+1}$도 방문할 수 있다. 따라서 이러한 경우에는 두 정점을 합쳐주면 된다. 이렇게 하면 정점들의 순서를 생각하지 않고, $c$를 키로 가지는 set을 이용하면 된다. small to large 방법을 사용하면 $O(Nlog^2N)$에 문제를 해결할 수 있다.

---

이제 Sparklers를 풀어보자.

$N$명의 사람이 폭죽을 하나씩 들고 일직선상에 서있다. $i$ 번째 사람은 $X_i$에 서있다($X_i \in \mathbf{Z}$). 처음에는 $K$번째 사람의 폭죽에만 불이 붙어있다. 한 폭죽에 불이 붙으면 그 불은 $T$초 동안 유지되며, 불이 꺼진 후에는 다시 불을 붙일 수 없다. 사람들이 움직여서 모든 폭죽에 불을 붙이려고 한다. 불을 붙이기 위해서는 불이 붙어있는 폭죽을 든 사람과 불이 붙어있지 않은 폭죽을 든 사람이 같은 장소에 있어야 한다. 사람들이 움직이는 속력에 제한을 걸어서 $v$ 이하의 속력으로만 움직일 수 있게 하려고 한다($v \in \mathbf{Z}, v \geq 0$). 모든 폭죽에 불을 붙이는 것이 가능한 $v$의 최솟값은?

불을 붙여주는 과정을 그래프로 나타내보면 $K$번 정점을 루트로 하는 트리가 됨을 알 수 있다. 이제 아래 Lemma들을 보이자.

Lemma 1. 불을 주는 행위가 불이 붙어있는 폭죽이 꺼지는 순간에만 이루어지게 할 수 있다.

pf) $i$번 폭죽의 불이 꺼지기 전에 $j$번에게 불을 붙여준다고 생각하자. 그렇다면 $j$가 $i$의 불이 꺼질 때까지 $i$를 따라다니게 할 수 있다. $j$가 $i$를 따라다니는 동안 $j$의 서브트리에 속하는 사람들($j$를 거쳐온 불로 폭죽에 불을 붙인 사람들)도 $j$와 똑같은 움직임을 하면 그 상대 위치는 바뀌지 않는다. 따라서 $i$의 불이 꺼지기 전에 $j$에게 붙인 것과 같은 효과를 낼 수 있다.

Lemma 2. 여러개의 폭죽에 동시에 불이 붙어있는 일이 없도록 할 수 있다.

pf) Lemma 1.이 성립하므로, 한 사람이 2명 이상의 사람에게 동시에 불을 나눠주는 일이 없다는 것을 보이면 된다. 만약 $i$번 사람이 $j$번 사람과 $k$번 사람에게 동시에 불을 준다면, 이것은 $i$가 $j$에게 불을 준 직후 $j$가 $k$에게 불을 준 것이라 볼 수 있다. 이는 Lemma 1.의 논리를 사용하면 $j$의 불이 꺼질 때 $k$에게 불을 준 상황으로 바꿀 수 있다. 이 과정을 반복적으로 적용하면 동시에 2명 이상의 사람에게 불을 주는 경우를 없앨 수 있다.

 

이제 불의 경로를 생각하자. 불은 $K$번 사람의 위치에서 시작한 후 $v$ 이하의 속력으로 이동한다. 아직 불을 받지 못한 사람들은 불을 향해 $v$의 속력으로 달려온다. 불과 새로운 사람이 만날 때마다, 불의 수명이 $T$씩 늘어난다. 이러한 상황에서 불의 수명이 다하기 전에 모든 사람을 만나는 것이 가능한지 판별하면 된다. 불이 $v$의 속력으로 끊임없이 움직인다 생각해도 무방하다. (ex. 움직이지 않는 것은 좌우로 방향을 끊임없이 바꾸며 진동하는 것과 같다.) 불과 사람들의 상대속도를 생각하자. 불이 왼쪽으로 $v$의 속력으로 움직이는 경우, 불의 왼쪽에 위치한 사람들은 $2v$의 속력으로 가까워지고, 불의 오른쪽에 위치한 사람들의 상대 위치는 바뀌지 않는다. 불이 오른쪽으로 움직이는 경우는 반대이다. 따라서 왼쪽 또는 오른쪽에 있는 사람들이 $2v$의 속력으로 가까워지고, 반대편은 상대위치가 일정하다. 

 

이제 Sparklers 문제가 Escape처럼 바뀌었다. 선형 트리가 있고, $K$번 정점에서 시작한다. $i<K$번 정점을 방문하면 $2vT - (X_{i+1}-X_i)$의 체력을 얻고, $i>K$번 정점을 방문하면 $2vT-(X_i - X_{i - 1})$의 체력을 얻는다. Escape와의 차이점은 모든 정점을 방문해야한다는 것이다. 따라서 $h<0$인 정점을 없애지 말고 기록해놓자. $h>0$인 부분들 모두 지난 후에는 $h<0$인 부분을 적절한 순서로 이동해서 모든 정점을 방문해야 한다. 그 역과정을 생각하면 $h>0$이 된다. 모든 정점을 지난 후의 체력을 계산한 후, 그 체력으로부터 거꾸로 진행한다. 이렇게 하면 특정 $v$에 대해 모든 폭죽에 불을 붙이는 것이 가능한지 판별할 수 있다. 여기에 이진탐색을 사용하면 $O(NlogX)$에 문제를 해결할 수 있다. (Escape와 달리 트리가 아니라 체인 2개이기 때문에 set을 사용하지 않고 그냥 $O(N)$에 합쳐주면 된다.)

 

사실 Sparklers 문제는 더 쉽게 풀 수 있다. 두 번째 풀이는 접근은 다르지만, 결국 알고리즘은 거의 유사하다. (그러나 구현은 이게 더 직관적이고 간단하다.) $s$번 사람부터  $e$번 사람이 불을 받았다고 하자. ($s\leq K \leq e$) 이 때 $X_e - X_s \leq 2vT(e-s)$가 만족되어야 한다. 이를 변형하면 $2vTs-X_s \leq 2vTe-X_e$이다. $A_i=2vTi-X_i$이라 하자. $A_s$가 최소가 되게 하는 $s(s\leq K)$를 $s_{mn}$, $A_e$가 최대가 되게 하는 $e(e\geq K)$를 $e_{mx}$라 하자. $s=K, e=K$에서 시작해서 $s=s_{mn}, e=e_{mx}$까지 옮기는 것이 가능한지 판별하는 것은 굉장히 간단하게 구현할 수 있다. $s$를 $A_s\leq A_e$가 유지되는 한에서 최대한 왼쪽으로 움직이자. 움직인 구간 중에서 $A_s$의 최솟값에서 $s$를 멈추자. 그 후 $e$도 마찬가지로 $A_s\leq A_e$가 유지되는 한에서 최대한 오른쪽으로 움직인다. $A_e$의 최댓값에서 $e$를 멈춘다. 이를 반복하여 $s=s_{mn}, e=e_{mx}$ 상태에 도달하면 성공한 것이다. $s<s_{mn}, e>e_{mx}$에 대해 확인을 하기 위해서는 뒤집어서 진행하면 된다. $s$를 $0$부터 $s_{mn}$까지 움직이고,  $e$를 $N$부터 $e_{mx}$까지 움직이며 확인을 하면 된다.