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의 개수는 \(\mathcal{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^{\prime})\)는 \(1\) 감소하고, 원래 위치에 있거나 오른쪽에 있다면 거리가 증가하기 때문에 \(1\) 증가한다는 것을 알 수 있다. 따라서 현재 증가하는 element의 개수를 저장해두고, 원래 위치에 도달하기까지 남은 시간을 key로 가지는 우선순위 큐를 이용해 개수를 업데이트하면 된다.

각 element는 감소 -> 증가를 단 한 번 밖에 하지 않으므로, 총합 \(\mathcal{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\)가 어떤 도착 정점까지 가는 최단 경로 중 하나에 포함됨을 의미하므로 그 화단을 방문하는 최단 경로가 존재한다. 다른 화단은 없으므로, 이것만 처리해주면 된다.

정점마다 최대 한 번씩만 탐색되므로 시간복잡도는 \(\mathcal{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\)

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

전체 문제

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

총평

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

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

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