_

1. Stage 1

1.1. Stone

답이 되는 벡터의 방향을 고정하고 생각하면 그 벡터의 방향 90도 이내의 벡터들을 전부 사용하고, 나머지는 사용하지 않는 경우 고정한 방향으로 가장 먼 벡터를 구할 수 있다는 것을 알 수 있다.

따라서 각 벡터에 대해 시계 방향으로 180도 이내의 벡터를 모두 더한 경우를 매번 답으로 갱신해주면 되는데, 180도 이내 벡터의 경우 Two Pointer로 관리하면 O(N)에 구할 수 있다.

1.2. Subway Design

1번 정점과 N번 정점을 잇는 직선을 생각해 보면 그 직선 상에 존재하지 않고 1번 정점이나 N번 정점에 직선 밖 트리처럼 붙어있는 정점들의 경우 \(l_i\)와 \(d_i\)의 차가 1번 정점부터 N번 정점의 거리로 정해진다. 또 그 외의 정점들은 \(l_i\)와 \(d_i\)의 차가 1번 부터 N번 정점 사이 거리보다 클 수 없다.

따라서 이때 모든 \(2\leq i \leq N-1\)에 대해 \(l_i\)와 \(d_i\)의 차 중 최댓값을 \(mx\)라 하면 \(mx\)는 1번 정점에서 N번 정점까지의 거리라고 할 수 있다.

\(l_i\)와 \(d_i\)의 차가 \(mx\)인 \(i\)의 경우 \(max(l_i, d_i) - mx = k_i\)라 하면 1번 정점¹ 또는 N번 정점에² 길이 \(k_i\)인 간선으로 정점 \(i\)를 붙여주면 된다.

\(l_i\)와 \(d_i\)의 차가 \(mx\)가 아닌 \(i\)들의의 경우 먼저 \(l_i + d_i = mx\)인 정점들의 경우 1번 정점과 N번 정점을 잇는 경로 상의 점임을 알 수 있다. 나머지 정점에서 \({{l_i + d_i - mx} \over 2 } = k_i\)라 하면 1번 정점에서 거리 \(d_i - k_i\)에 있는 정점 N과의 경로 상 정점에다가 거리 \(k_i\)로 이어주면 조건을 만족하는 그래프를 만들어낼 수 있다.

경로 길이가 자연수가 아니거나, 연결할 정점이 없는 등 앞의 과정들에서 문제가 하나라도 발생하면 _NIE_를 출력하면 된다.

1.3. Flood

문제

같은 높이의 구역들을 그룹으로 묶어서 관리한다는 아이디어를 생각해볼 수 있다. 이때 그룹이 변경되는 횟수는 최대 \(N-1\)번이기 때문에 그룹을 합치는 것을 \(O(1)\)에 처리하면 \(O(MN)\)에 문제를 해결할 수 있다.

그룹을 합치는 것에서 끝나는게 아니라 경우의 수를 세야 하기 때문에 Union & Find를 해주면서 그룹마다 DP처럼 정보를 저장하고 있으면 된다. 각 그룹마다 그 그룹의 구역의 가능한 최소 높이 \(H_i\)와 그 그룹의 누적 경우의 수 \(C_i\)를 저장하고 있자. 처음에는 모든 구역의 \(H_i = 1, C_i = 0\)일 것이다.

댐의 높이가 낮은 순서로 그룹을 합쳐주는 과정을 반복한다. 그룹 A와 그룹 B를 높이 \(h\)인 댐을 통해 합쳐주어 그룹 C를 만든다고 생각해보자. 그룹 C의 최소 높이는 \(h+1\)이기 때문에 \(H_C = h+1\)이 된다. 또, 그룹 C에는 그룹 A와 그룹 B가 각각 높이 \(h\) 이하인 경우를 \(C_C\)에 저장해야 하기 때문에 \(C_C = (C_A + h+1 - H_A) \times (C_B + h+1 - H_B)\)라고 계산해줄 수 있다. 이때 같은 높이 \(h\)에 대해 여러 그룹(그룹 A, 그룹 B, 그룹 C, ...)이 하나의 그룹(그룹 Z)으로 합쳐지는 처리를 하는 경우 \(C_Z = (C_A + h+1 - H_A) \times (C_B + h+1 - H_B) \times (C_C + h+1 - H_C) \times ...\)처럼 동시에 \(C_i\)값을 계산해줘야 한다.

마지막에 그룹 하나(그룹 A)가 남으면 답은 \(C_A + H+1 - H_A\)로 계산하여 구할 수 있다.

비슷한 방식으로 하되 \(H_i\)에 그 그룹의 가능한 최소 높이 대신 현재 그룹의 높이를 저장하고 \(C_i\)에 그 그룹에서 높이 \(H_i\) 이하로 가능한 경우의 수를 저장해 놓으면 합칠 때 쉽게 합칠 수 있으며 여러 그룹을 합치는 것도 2개의 그룹을 합치는 것 여러 번으로 처리해줄 수 있으므로 간단하다...

높이 \(h\)의 댐으로 그룹 A와 그룹 B를 그룹 C로 합치면 먼저 \(C_A = C_A + h - H_A\), \(C_B = C_B + h - H_B\)라 한 다음 \(C_C = C_A * C_B, H_C = h\)라고 해주면 된다.