SCPC 2025 Round 1¶

A. 거스름돈¶

\(500\)원을 내는 사람이 왔을 때는 \(500\)원을 받는 선택지밖에 없으며, 항상 가능하다.
\(1000\)원을 내는 사람이 왔을 때는 \(1000\)원을 받고 \(500\)원을 거슬러 주는 선택지밖에 없으며, \(500\)원 동전이 남아 있다면 가능하다.
\(5000\)원을 내는 사람이 왔을 때가 문제인데, 우선 \(5000\)원 지폐는 거스름돈에 사용하는 경우가 없기 때문에 무시해도 되고, 현재 갖고 있는 \(500\)원짜리 동전들과 \(1000\)원짜리 지폐를 이용하여 \(4500\)원을 거슬러 주는 상황이다. \(500\)원짜리 동전은 2번째 케이스에서 거슬러 주어야 하지만 \(1000\)원짜리 지폐는 받기만 하니, 최대한 \(1000\)원짜리 지폐를 많이 이용하는 것이 이득이다. 따라서 \(4500\)원을 우선 가능한 많은 \(1000\)원 지폐를 이용하고, 남은 만큼 \(500\)원짜리 동전을 이용하여 거슬러 주면 된다.

위 전략에 맞게 사람들이 올 때마다 현재 내가 들고 있는 \(500\)원, \(1000\)원의 개수를 관리하며 그리디하게 배정하다가 실패하는 순간을 구하면 된다.

B. 폭탄¶

각 폭탄 사이에 \(0\)으로 이동할지, \(L\)로 이동할지를 정하면 되는 문제이다. 모든 선택들이 서로 독립적이므로 단순하게 인접한 두 폭탄 사이에서 \(0\)으로 이동하는 거리의 합이 작은지, \(L\)로 이동하는 거리의 합이 작은지 따져서 그리디하게 더해주면 된다.

C. 십진수¶

생각의 편의를 위하여 leading zero를 모두 붙여서 생각한다. (사용할 수 있는 숫자가 \(0, 1, 2\)이기 때문에 문제가 없다.) 또한, 편의를 위하여 \(1 \sim N\)까지의 수 대신 \(0 \sim N-1\)까지의 수들 중 조건을 만족하는 수들의 개수를 센다.

가장 앞자리부터 하나씩 보며, \(0 \sim N-1\) 수들 중 지금까지 본 자리의 숫자들이 \(N\)과 다른 수들의 개수를 답에 더해 나간다. 현재 자리의 칸을 포함하여, 앞으로 남은 자리들의 개수를 \(k\)개라 하자.

현재 자리가 \(0\) : 추가로 더하지 않고 다음 자리로 넘어간다.
현재 자리가 \(1\) : 현재 자리가 \(0\)인 수들을 모두 답에 더해주어야 한다. 답에 \(3^{k-1}\)을 더하고 다음 자리로 넘어간다.
현재 자리가 \(2\) : 현재 자리가 \(0, 1\)인 수들을 모두 답에 더해주어야 한다. 답에 \(2 \cdot 3^{k-1}\)을 더하고 다음 자리로 넘어간다.
현재 자리가 \(3\)이상 : 더 이상 추가적으로 고려할 필요가 없다. 현재 자리부터 시작하여 남은 모든 자리에 \(0, 1, 2\)를 자유롭게 배정하면 된다. 답에 \(3^k\)를 더하고 종료한다.

D. 상점¶

우선 파란 집 \(b\)과 매칭되는 빨간 상점 \(r\)의 순서쌍을 고정시켰다고 생각하자. 같은 개수의 빨간 집들을 빨간 상점들과 일대일 매칭 시켜서 거리의 합을 최소화해야 하니, 이는 두 집합을 정렬하고 순서대로 매칭하면 된다. (파란 집들과 파란 상점들도 마찬가지로 계산한다.) 이와 같이 \((r, b)\)의 순서쌍을 고정시키는데 \(O(N^2)\), 비용을 계산하는데 \(O(N)\)으로 \(O(N^3)\)에 문제를 해결할 수 있다.

\((r, b)\) 대신 \(r\)만 고정해도 빨간 집들과 빨간 상점들 간의 매칭 비용은 계산할 수 있다. 이는 빨간 집, 상점 두 집합을 정렬하고 prefix, suffix sum을 이용하여 빠르게 구할 수 있으며 결론적으로 모든 \(r\)에 대해 \(r\)을 선택했을 때 남은 빨간 집, 상점들을 매칭하는 비용 \(X[r]\)을 \(O(N)\)에 구할 수 있다. 같은 방법으로 \(b\)를 선택했을 때 남은 파란 집, 상점들을 매칭하는 비용 \(Y[b]\)를 \(O(N)\)에 구할 수 있다.

이제 우리가 해결하고 싶은 문제는 모든 \((r, b)\) 순서쌍에 대하여 \(X[r]+Y[b]+|A[r]-B[b]|\) (\(A[r], B[b]\)는 좌표)를 최소화 하는 것이다. 절댓값 기호가 거슬리긴 하지만, \(A[r]>B[b]\)인 경우만 고려한다고 가정하면 \((X[r]+A[r])+(Y[b]-B[b])\)를 최소화하는 문제이니 변수 분리가 가능하고, \(r\)을 하나씩 증가시키며, \(b\)에 대한 투 포인터로 \(O(N)\)에 문제를 해결할 수 있다. 반대의 경우도 정확히 같은 방법으로 한번 더 투 포인터를 활용하면 정렬 한번 후 전 과정을 \(O(N)\)에 해결할 수 있다.

E. MST¶

모든 스패닝 트리들에 대하여, 1. 사용한 간선의 가중치의 최댓값 - 최솟값을 최대화 해야 하고, 2. 같은 경우 사용한 간선의 가중치 합을 최소화 해야 한다.

우선, "사용한 간선의 가중치의 최댓값 - 최솟값"을 최대화 해야 하는데, 다음과 같이 변형할 수 있다. "스패닝 트리에 대하여 임의의 두 간선 \(e_1, e_2\)를 선택하고, \(e_1 - e_2\)"를 최대화 하는 문제로 바꾸어 생각해도 최적해에서는 자연스럽게 \(e_1\)을 최댓값, \(e_2\)를 최솟값으로 선택할 것이기 때문에 원래 문제와 동일하다. 이 문제는 먼저 임의의 두 간선 \(e_1, e_2\)를 선택하고, 그 다음 \(e_1, e_2\)를 포함하는 MST를 잡는 문제로 생각할 수 있으니, \(O(M^3)\)에 해결할 수 있다.

하지만 우리는 \(e_2\)를 최솟값 간선으로 선택하고 싶고, MST를 선택하면 자연스럽게 최소 가중치 간선은 무조건 포함한다. 이를 이용하여 처음부터 굳이 \(e_1, e_2\)를 선택하지 말고, \(e_1\)만 선택한 후 MST를 구하면 자연스럽게 \(e_2\)는 현재 MST에서 최소 가중치 간선으로 정하면 된다. 따라서, 임의의 간선 \(e_1\)에 대하여 \(e_1\)을 포함하는 MST를 구하고, 최소 가중치 간선과 가중치 합을 구하면 문제를 \(O(M^2)\)에 해결할 수 있다.

하지만 "임의의 간선 \(e_1\)을 포함하는 MST 구하기"는 유명한 문제이며, 기본적으로 MST를 구한 후, 원하는 간선 \(e_1\)이 연결하는 두 정점 사이의 경로에서 가장 가중치가 큰 간선을 끊고 \(e_1\)을 삽입하면 된다. 우리가 필요한 건 원래 MST에서 어떤 간선을 끊어야 하는지와, 그 간선을 끊고 \(e_1\)을 삽입하였을 때의 최소 가중치 간선과 가중치 합이니, 원래 MST에서 minimum과 second minimum 정도만 관리하고, 원래 MST에서 path maximum query를 빠르게 해결할 수 있으면 된다. 이는 sparse table을 이용하면 쉽게 해결할 수 있으니, 전체 문제를 \(O(M \log M)\)에 해결할 수 있다.