ABC351 E - Jump Distance Sum

Competitive Programming C++ AtCoder Algorithms

2024-04-28

공식 에디토리얼

문제 링크
https://atcoder.jp/contests/abc351/tasks/abc351_e

원문 링크
https://atcoder.jp/contests/abc351/editorial/9890

점을 원점을 중심으로 하여 \(45\)도 회전한 후, \(\sqrt{2}\)배로 확대하는 것을 생각해봅시다.
이 때, 원래 \((X, Y)\)에 있던 점은 \((X +Y, X - Y)\)로 이동하게 됩니다.

다음으로, \(\mathrm{dist}(A, B)\)의 정의가 어떻게 되는지 생각해봅시다.
토끼는 원래 정의대로라면 \((X, Y)\)로부터 \((X + 1, Y + 1), (X + 1, Y - 1), (X - 1), (Y + 1), (X - 1), (Y - 1)\)로 점프할 수 있었으므로,
이는 \((X + Y, X - Y)\)로부터 \((X + Y + 2, X - Y), (X + Y, X - Y + 2), (X + Y, X - Y - 2), (X + Y - 2, X - Y)\)로 점프하게 됩니다.
\(x = X + Y, y = X - Y\)로 바꿔 쓰면 \((x, y)\)로부터 \((x + 2, y), (x, y + 2), (x, y - 2), (x - 2, y)\)로 이동하는 것이 됩니다.
이 때의 \(A\)에서 \(B\)까지 이동하는 데 필요한 점프 횟수의 최솟값이(도달할 수 없는 경우엔 0) \(\mathrm{dist}(A, B)\)의 정의가 됩니다.

다음으로, 회전/확대 한 후의 상태에 대해 문제를 생각해봅시다.

즉., \(P_i = (x_i, y_i)\)라 두고, 위의 내용처럼 \(\mathrm{dist}(A, B)\)를 정의했을 때의 \(\sum_{i = 1}^{N - 1}\sum_{j = i + 1}^{N}\mathrm{dist}(P_i, P_j)\)의 값을 구하면 됩니다.

이는 원래 문제와 일치함이 자명합니다.

\(A = (x_1, y_1), B = (x_2, y_2)\)일 때, \(\mathrm{dist}(A, B)\)에 대해서 구체적으로 생각해봅시다. \(x_1 \not \equiv x_2\ (\mathrm{mod} 2)\) 또는 \(y_1 \not \equiv y_2\ (\mathrm{mod} 2)\) 일 때, 토끼는 \(A\)에서 \(B\)로 이동하지 못하므로, \(\mathrm{dist}(A, B) = 0\)이 됩니다. 그렇지 않을 때, 이는 맨해튼 거리의 딱 절반이 되기 때문에, \(\frac{1}{2}(\vert x_1 - x_2 \vert + \vert y_1 - y_2 \vert)\)가 됩니다.

임의의 \(i\)에 대해서 \(x_i = y_i + 2Y_i \equiv y_i\ (\mathrm{mod} 2)\)임에 주의하면, \(N\)개의 점은 \(x_i, y_i\)가 합해서 짝수인 그룹과 홀수인 그룹으로 나눌 수 있으며, 서로 다른 그룹에 속하는 \(2\)개의 점 \(A, B\)에 대해서는 \(\mathrm{dist}(A, B) = 0\)이 되어, 같은 그룹에 속하는 \(2\)개의 점 끼리는 \(\mathrm{dist}(A, B) = \frac{1}{2}(\vert x_1 - x_2 \vert + \vert y_1 - y_2 \vert)\)가 됩니다.

\(x_i, y_i\)가 모두 짝수인 점들의 집합을 \(E = \{E_1, E_2, … , E_{\vert E \vert}\}\)로 나타내면, \(\sum_{i = 1}^{\vert E \vert - 1}\sum_{j = i + 1}^{\vert E \vert}\mathrm{dist}(P_{E_i}, P_{E_j}) = \frac{1}{2}\sum_{i = 1}^{\vert E \vert - 1}\sum_{j = i + 1}^{\vert E \vert}\vert x_{E_i} - x_{E_j} \vert + \frac{1}{2}\sum_{i = 1}^{\vert E \vert - 1}\sum_{j = i + 1}^{\vert E \vert}\vert y_{E_i} - y_{E_j} \vert\)이 됩니다.

\(\sum_{i = 1}^{\vert E \vert - 1}\sum_{j = i + 1}^{\vert E \vert}\vert x_{E_i} - x_{E_j} \vert\)는 \((x_{E_i}, x_{E_2}, … , x_{E_{\vert E \vert}})\)를 오름차순으로 정렬한 수열을 \((x_{E_i}’, x_{E_2}’, … , x_{E_{\vert E \vert}}’)\)라 할 때,

\(\sum_{i = 1}^{\vert E \vert - 1}\sum_{j = i + 1}^{\vert E \vert}\vert x_{E_i} - x_{E_j} \vert = \sum_{i = 1}^{\vert E \vert - 1}\sum_{j = i + 1}^{\vert E \vert}\vert x_i’ - x_j’ \vert = \sum_{i = 1}^{\vert E \vert - 1}\sum_{j = i + 1}^{\vert E \vert}(x_i’ - x_j’) = \sum_{i = 1}^{\vert E \vert}(\vert E \vert + 1 - 2i)x_i’\)으로 구할 수 있습니다.

마찬가지로 \(y\)좌표에 대해서도 계산해주는 것으로, \(\sum_{i = 1}^{\vert E \vert - 1}\sum_{j = i + 1}^{\vert E \vert}\mathrm{dist}(P_{E_i}, P_{E_j})\)를 구할 수 있으며 \(x_i, y_+i\)의 합이 홀수인 점들의 집합에 대해서도 마찬가지로 계산해서 더해주는 것으로 최종 정답을 구할 수 있습니다.

시간복잡도는 \(2\)개 그룹의 \(x, y\)좌표를 각각 정렬하는 데 필요한 \(O(N \log N)\)에 더해 \(O(N)\) 만큼 더 계산하므로, 전체 \(O(N \log N)\)에 답을 구할 수 있습니다.

좌표평면 회전 아이디어

충분히 생각할 수 있는 문제였던거 같고, D까지 비교적 빨리 풀어내서 여유도 있었다.

근데 좌표평면 돌리는 아이디어를 캐치 못하고…
세그랑 스위핑으로 비비려 열심히 짜다 막혀버렸다.

웰노운을 더 공부해야 이런것도 금방 보고 하겠지.