USACO Gold 후기 [2025/2026 Third Contest]

:blobhyperthink:

 

USACO Gold부터는 한국 시간 기준 새벽 2시에 시작해서 6시에 끝나야 Platinum Division으로 진출할 수 있다.

 

첫 번째 대회는 누워있다가 잠드는 바람에 완전 놓쳐버렸고, 두 번째 대회는 그냥 망했었다 (350점).

하지만 USACO는 이유는 모르겠지만 세 번째 대회가 항상 제일 쉬운 경향이 있어서 일단 올해 마지막 기회 겸 해보기로 했다.

 

> 모든 문제가 Test Case여서 조금 당황했다. Codeforces에 내려다가 버려진 문제인지 궁금하다.

버려진 거 맞는 거 같은데...

문제별 풀이

Problem 1 : Good Cyclic Shifts

어떠한 순열 $p$에 대해서 $f(p) = \sum_{i=1}^{N}{\frac{|p_{i} - i|}{2}}$라고 정의한다.

입력으로 길이 $N$의 순열이 주어진다. 오른쪽으로 Cyclic Shift를 할 때 순열마다 Inversion의 개수가 $f(p')$보다 같거나 작은지 판별하는 문제다.

 

> $\sum_{i=1}^{N}{|p_{i} - i|}$는 항상 짝수라는 것이 보장된다 (Permutation Displacement).

 

각 Cyclic Shift마다 Inversion의 개수는 $O(1)$로 업데이트 할 수 있다. ($v \rightarrow v + 2X - N - 1$; $X$는 맨 오른쪽에서 맨 왼쪽으로 이동한 수) 따라서 이 문제는 각 Shift마다 $f(p)$를 빠르게 계산하는 문제가 될 것이다.

 

편의성을 위해 함수 $g$를 정의하고 $g(p) = 2f(p) = \sum_{i=1}^{N}{|p_{i} - i|}$라고 두자.

 

순열의 각 항은 왼쪽에서 오른쪽으로 이동한다. 이때, 원래 위치의 왼쪽에 있다면 거리가 감소해서 $g(p')$는 $1$ 감소하고, 원래 위치에 있거나 오른쪽에 있다면 거리가 증가하기 때문에 $1$ 증가한다는 것을 알 수 있다. 따라서 현재 증가하는 element의 개수를 저장해두고, 원래 위치에 도달하기까지 남은 시간을 key로 가지는 우선순위 큐를 이용해 개수를 업데이트하면 된다.

 

각 element는 감소 -> 증가를 단 한 번 밖에 하지 않으므로, 총합 $O(2N)$ 정도만 우선순위 큐에 저장된다는 것을 알 수 있다.

Problem 2 : Picking Flowers

정점의 개수가 $N$, 양방향 간선의 개수가 $M$인 그래프가 주어진다. $K$개의 정점에는 화단이 있고, $L$개의 정점이 도착 지점이다. (화단이 있는 정점도 도착 지점이 될 수 있다.)

각 정점 $v$에 대해 해당 정점에 화단을 하나 추가했다고 가정할 때, $1$번 정점부터 어떤 도착 지점까지의 최단 경로 중 하나가 모든 화단을 방문할 수 있는지 판별하는 문제다. ($2 \leq v \leq N$) 각 정점에 대한 판별은 서로 독립적이다.

 

> 서브테스크 1: $K=0$, $L=1$

> 서브테스크 2: $K=0$

> 서브테스크 3: 추가 제약 조건 없음.

 

문제를 잘못 읽어서 모든 화단이 아니라 하나라도 방문할 수 있는 걸로 판별하는 줄 알았던 상태로 풀이를 짰는데, 그게 우연찮게 $K=0$ 풀이였다. (USACO 하기 직전에 쳤던 AtCoder에서도 비슷한 상황이 있었던 것 같은데..)

공통 관찰

일단 모든 Subtask에서 공통적으로 해야하는 관찰에 대해서 설명하겠다.

 

정점 $1$에서 시작해서 각 도착 지점까지의 최단 경로만 고려하기 때문에 모든 정점에 대해 정점 $1$로부터의 최단 거리를 BFS로 구한다. 이후 임의의 도착 지점 $t$에 대해서 $\mathrm{dist}(1, v) + \mathrm{dist}(v, t) = \mathrm{dist}(1, t)$를 만족하는 정점만이 $1 \rightarrow t$ 최단 경로 위에 존재할 수 있다.

따라서 이 조건을 만족하는 정점들만 남기고 나머지는 제거하면, "어떤 도착 지점으로 가는 최단 경로에 포함될 수 있는 정점"들만 남게 된다. 최단 경로에서는 이동할 때마다 거리값이 정확히 $1$씩 증가하므로 남은 간선들은 항상 거리가 증가하는 방향으로 진행하기 때문에 이 그래프는 DAG가 된다.

Subtask 2 : $K = 0$

각 도착 정점에서 시작해 거리 값이 $1$씩 감소하는 간선만 따라 역방향 BFS를 수행하면 어떤 도착 정점으로 가는 최단 경로에 포함되는 모든 정점을 구할 수 있다. 정점 $v$가 이 과정에서 제거되지 않았다면, 이는 $v$가 어떤 도착 정점까지 가는 최단 경로 중 하나에 포함됨을 의미하므로 그 화단을 방문하는 최단 경로가 존재한다. 다른 화단은 없으므로, 이것만 처리해주면 된다.

 

정점마다 최대 한 번씩만 탐색되므로 시간복잡도는 $O(N)$이다.

전체 문제

$K=0$에서 살짝만 바꾸면 만점을 받을 수 있다.

 

DAG에서 DP를 수행한다.

• $F[v]$ : 정점 $1$에서 $v$까지 가는 최단 경로 중 방문할 수 있는 화단의 최대 개수
• $B[v]$ : 어떤 도착 지점에서 $v$까지 (역방향으로) 갈 때 방문할 수 있는 화단의 최대 개수

정점 $v$를 지나는 하나의 최단 경로가 모든 화단을 포함하려면 $F[v] + B[v] - \mathrm{is\_flower}[v] = K$를 만족하면 된다. ($v$에 화단이 있을 경우 중복 계산되므로 빼줘야 한다)

따라서 위 조건을 만족하는 정점에 화단을 추가했을 때 모든 화단을 방문하는 최단 경로가 존재한다.

Problem 3 : Random Tree Generation

다음과 같이 트리를 생성한다.

1. 정점 $1$을 만든다.
2. 각 정점 $i(2 \leq i \leq N)$는 $1$ 이상 $i-1$ 이하의 정점 중 하나를 균등하게 선택하여 부모로 둔다.
3. 위 과정을 $N-1$개의 정점이 추가될 때까지 반복한다.
4. 이후 정점 번호에 임의의 순열을 적용한다.

정점의 개수가 $N$인 트리가 주어질 때, 위 방법으로 생선된 트리가 주어진 트리와 정확히 동일한 간선 집합을 가질 확률을 구하는 문제이다.

 

> 서브테스크 1: $N \leq 8$

> 서브테스크 2: $N \leq 2\,000$

> 서브테스크 3: $N \leq 200\,000$

 

임의의 정점이 생성되려면 그 부모가 항상 먼저 생성되어야 하기에, 어떤 정점이 $1$번 정점(루트)이었는지에 따라 가능한 순서의 개수가 달라진다. 루트를 $r$로 두고 DFS를 통해서 각 정점의 서브트리의 크기를 구해보자. 부모가 자식보다 먼저 나오는 순서여야 하기 때문에, 이 트리를 만들 수 있는 순서의 수는 $\frac{\left(N - 1\right)!}{\prod_{u \neq r}{\mathrm{sz}_{r}[u]}}$이다.

 

한편, 생성 과정에서 정점 $i$는 부모를 $\frac{1}{i-1}$의 확률로 선택하기 때문에, 하나의 특정한 생성 순서가 나올 확률은 $\prod_{i=2}^{N}{\frac{1}{i-1}} = \frac{1}{\left(N-1\right)!}$이다.

 

따라서 루트가 $r$일 때 트리가 정확히 동일한 간선 집합을 가질 확률은 $\frac{\left(N - 1\right)!}{\prod_{u \neq r}{\mathrm{sz}_{r}[u]}} \times \frac{1}{\left(N-1\right)!} = \frac{1}{\prod_{u \neq r}{\mathrm{sz}_{r}[u]}}$이다.

 

마지막으로, 라벨을 임의로 섞는 경우까지 포함시키면, 최종 답은 모든 정점이 루트인 경우를 전부 세서 $N!$로 나눠주는 것이 된다.

Subtask 2 : $N \leq 2\,000$

$O(N^{2})$으로 각 루트마다 DFS를 사용하면 해결할 수 있다.

전체 문제

현재 트리의 루트를 $r$이라고 뒀을 때, 트리의 루트를 임의의 $r$ 자식 $v$로 바꾸면, 서브트리 크기가 바뀌는 정점은 $r$과 $v$뿐이다. 트리의 루트를 잡고 $O(N)$으로 DFS를 한 번 돌려 $\mathrm{sz}$를 알아낸 뒤 DFS를 한 번 더 돌려서 각 정점마다 $O(1)$로 바뀐 서브트리의 크기를 계산해주면서 답을 구하면 된다.

총평

문제가 재밌었다. 난이도도 풀만했던 것 같고, 적어도 두 번째 대회에서 4시간을 날린 것 보다는 좋은 성과를 거뒀으니...

Platinum부터는 넘사벽이라 아마 안 할 것 같다.

 

추신) Platinum을 유지하려면 Gold를 매년 해야 한다고 한다. 유지할 만큼의 실력을 길러야겠다...