[백준] 2023 KAIST RUN Spring Open Contest 후기
https://www.acmicpc.net/contest/view/1021
2023 KAIST RUN Spring Open Contest
www.acmicpc.net
[총평]
오랜만에 영어 문제로 대회를 치르다 보니(마지막 코드포스 이후로 4개월만 ?) 문제 읽는데도 오래 걸리고, 이해하는데도 시간이 좀 걸렸다. 그런 것 치고는 나름대로 좋은 결과가 나온 것 같..다.
문제 공개 초기에는 B번에 플4(!) 기여가 찍히면서 '내가 대회 중에 플레 문제를 풀었다고..?'하는 생각이 들었는데, 지금 보니 역시 고평가였던 듯 하다.. 다만 C < B인 것만큼은 맞지 않나 하는 생각이 든다. C번도 증명까지 생각하려면 확실히 어려운 문제인 것 같지만, 손으로 끄적끄적하다 보면 직관적으로 보이는 풀이가 있다 보니..
뒤 문제들은(D부터) 제대로 보지 못했지만, 앞부분 문제들은 상당히 코포스럽지 않나 하는 생각이 든다. 어려운 알고리즘이나 자료구조보다는 발상과 직관, 그걸 풀어내는 수학적 전개가 더 필요했다고 본다. 그래서 개인별 체감 난이도차가 클 것 같다. (실제로도 그런 반응이 많다.)
[문제 풀이]
A번. Simple Game
https://www.acmicpc.net/problem/28053
28053번: Simple Game
Let $s$ be an arithmetic sequence consisting of $2n$ integers, where the first term is denoted as $a$ and the common difference as $b$. In other words, $s = [a, a+b, a+2b, \ldots, a+(2n-1)b]$. You should perform a sequence of $n$ operations, where each ope
www.acmicpc.net
첫 문제부터 호락호락하지 않은 정수론 수학 문제. 문제를 요약하자면, 초항과 공차가 주어진 길이가 짝수인 등차수열에서 서로소 짝을 계속해서 뽑아낼 수 있느냐이다.
[서브태스크1](50점)
$b=1$일 때 답은 항상 Yes이다. 어떤 연속한 두 수는 늘 서로소이기 때문에, 계속해서 연속한 두 수를 뽑아내기만 하면 된다.
[서브태스크2](50점)
서브태스크1에서 한 발 더 나아가보자. 서브태스크1에서 알 수 있듯 등차수열에서 연속된 위치에 있는 두 수가 서로소가 될 수 있는지를 판별해주면 된다. 왜냐하면 $a$와 $a+b$를 비교했던 방법 그대로 $a+2b=A$, $a+3b=A+d$와 같이 치환하여 똑같이 적용해볼 수 있기 때문이다. 이때 gcd($a$, $a+b$) = 1이기 위해서는 gcd($a$, $b$) = 1이어야 함을 쉽게 알 수 있다.
B번. Clique Partition
https://www.acmicpc.net/problem/28054
28054번: Clique Partition
We have a complete graph of size $N$. Find a way to represent the set of edges in this graph as the union of several $N$-vertex trees. Specifically, $K$ denoting the number of trees and $K$ trees $T_1, ..., T_K$ satisfying the following conditions should b
www.acmicpc.net
최소의 트리 개수로 완전 그래프 덮기. 말은 간단해보이지만..
우선 트리 개수의 최솟값부터 구해보자. 완전 그래프를 볼록 다각형으로 바라보자. 어떤 볼록 다각형의 대각선의 개수와 변의 개수의 합은, 볼록 다각형의 변의 개수가 $n$일 때 $\frac{n(n-1)}{2}$개이다. 한편, 정점이 $n$개인 트리의 간선 개수는 $n-1$개이다. 따라서 필요한 트리 개수의 최솟값은
- $n$이 홀수일 때, $n/2+1$개
- $n$이 짝수일 때, $n/2$개
이 개수대로 트리를 구성해보자. 여러 풀이가 있을 것 같은데 내 접근은 이렇다. 트리 개수를 최소로 맞추기 위해서는 각 트리에서 겹치는 간선이 최대한 없게 해야 한다. (특히 $n$이 짝수일 때는 겹치는 간선이 아예 없어야 한다.)
- 어떤 한 정점을 기준으로 간선 여러 개를 이어본다. 이때 이 '여러 개'는 $n-1$개가 될 수 없음이 자명하다.
- 남은 간선은 1.에서 연결되지 않은 정점을 기준으로 1.의 방법과 동일하게 이어준다.
- 1~2를 반복한다.
'여러 개'는 시행착오를 통해 $n/2$개임을 알 수 있고, 2.에서의 기준 정점은 1.에서 마지막으로 끝난 정점으로 하는 것이 개인적으로 (구현 측면에서도) 가장 깔끔한 것 같다. 예시로, $n = 6$이라고 하자.
tree 1. 1-2, 1-3, 1-4
tree 2. 2-3, 2-4, 2-5
tree 3. 3-4, 3-5, 3-6
<각 트리를 규칙 1.에 맞춰 구성한 상태>
tree 1. 1-2, 1-3, 1-4, 4-5, 4-6
tree 2. 2-3, 2-4, 2-5, 5-1, 5-6
tree 3. 3-4, 3-5, 3-6, 6-1, 6-2
<각 트리를 규칙 2.에 맞춰 완전히 구성한 상태>
이러한 방법이 $n$이 홀수일 때도 성립한다는 것을 보일 수 있다.
C번. Monochrome Tree
https://www.acmicpc.net/problem/28055
28055번: Monochrome Tree
Vertex $x$ is an ancestor of vertex $y$ $(x \neq y)$ if there is a sequence of vertices $\{x=a_1, a_2, \ldots a_k=y\}$ where $a_i$ is a parent of $a_{i+1}$ ($1 \leq i \leq k-1$).
www.acmicpc.net
C번을 처음 봤을 때, 어려운 문제가 아닌가 싶어서 잠시 후퇴했다가 B번에 매진했었다. 지금 생각해보면 C번을 좀 더 고민해보면 어땠을까 하는 아쉬움이 조금 있다. B번에 1시간~2시간 정도를 쏟다 포기하고 돌아왔을 때 상당히 쉽게 풀렸었기 때문에..
트리의 리프 노드 수가 $k$개라고 하자. 그렇다면 $c_0$부터 $c_k$까지의 값은 0이 될 수 있음을 쉽게 알 수 있다. 리프 노드만 색칠해 나갈 경우, 색칠된 부모-자식 관계 쌍이 나타나지 않기 때문이다. 그렇다면, $c_{k+1}$부터는 어떻게 구해야 할까? 다음부터는 반드시 부모-자식 관계 쌍이 나타나게 되므로 자식 노드가 최소 개인 노드부터 색칠해 나가야 한다. 그리고 이를 반복한다.
한 번의 dfs를 통해 노드 당 자신의 아래에 있는 노드 개수를 파악한 후 정렬, 이를 토대로 $c_i$값을 계산한다. 어떤 노드의 아래에 있는 노드(자식 노드) 개수를 $x$개라 할 때, $c_i = c_{i-1} + x$이다.
[업솔빙]
(추후 추가 예정)