서울대학교 프로그래밍 대회 (SNUPC) 2021 후기 / 풀이(A-G) & Whining
9월 11일 (토)에 진행된 서울대학교 프로그래밍 경시대회 (SNUPC) 2021 Division 2에 참가해 6등 했습니다.
SNUPC
SNUPC는 한국에서 열리는 프로그래밍 대회 중 개인 대회로는 아마 가장 높은 난이도를 자랑하는 대회가 아닌가 싶습니다. Division 1과 2로 나누어 수행되는데, 기억에는 Division 1의 참가자 상당수가 ACM-ICPC World Final 참가자들 급의 실력을 가진 (실제 WF 무대를 경험한 사람들도 10명은 있을 겁니다) 것으로 기억합니다. 제가 참가한 Division 2는 (공식적으로는) 퍼플 이하의 참가자들을 위한 대회이기 때문에 난이도가 훨씬 덜하지만, 다른 대학 대회들과 비교하면 오히려 정상적인 수준입니다.
저는 2019년에 Div2 9등 (3등상), 2020년에 7등 (3등상), 올해 6등 (3등상) 의 성적을 얻었습니다. 제 실력은 분명 조금씩 발전하고 있지만, 대회가 점점 더 고여가기 때문에 제가 내년에도 Div2 우승을 노리는 것보다는 아마 Div1에 나가지 않을까 싶습니다. SNUPC는 대학원생들도 꽤 많이 나오고, 저한테는 앞으로도 당분간은 좋은 취미일 (?) PS를 즐길수있게 해주는 좋은 대회이기 때문에 석사과정 정도까지는 토요일 하루 빼서 나와볼만 하다고 생각합니다.
Phase 1 : Easy problems (0분 - 60분)
A, B
A, B 두 문제는 워낙 쉬운 문제라서 딱히 commentate할 부분은 없습니다.
B 퍼솔을 먹어서 기분이 좀 좋았습니다. :)
C를 조금 손대 보았고, 실제로 맞는 관찰을 헀지만, 구현에서 실수가 조금 있어서 AC를 받지 못했습니다. 스코어보드를 보고 의외로 G가 쉬운 문제라고 판단하여 G로 갔습니다.
G : 자연수 색칠하기
서로소인 두 색을 서로 다른 색으로 색칠해야 한다는 조건이 있는데, 이 조건의 충분조건으로 다음과 같은 색칠을 생각합니다.
- 소수는 모두 서로소이므로, 소수끼리는 서로 다른 색으로 칠합니다.
- 소수가 아닌 수는, 무조건 가장 큰 소인수에 해당하는 색으로 칠합니다. 이렇게 칠하면, $\pi(n) + 1$ 개의 색을 쓰게 됩니다 (1은 따로 칠해야 하므로) 소수는 모두 서로 다른 색으로 칠해야 하므로 이보다 적게 색깔을 쓰는 방법은 없습니다. 또한, 두번째 조건에 의해 서로소인 수는 소인수를 공유하지 않으므로 다른 색으로 칠하게 되어, 이 칠하는 방법이 올바릅니다.
F : AND와 OR
두 수 $a, b$를 두 수 $c, d$로 바꾸되, 이때 $a, b$와 $c, d$는 각각 AND한 값과 OR한 값이 같아야 합니다. $N$개의 수가 주어지고, 이 수들에 대해 이 연산을 원하는 만큼 수행한 후, 곱을 최소화하는 문제입니다.
생각해 보면, 두 수에 모두 켜져 있는 비트는 c, d 에서도 켜져 있어야 하고, 한쪽에만 켜져 있는 비트는 한쪽에만 켜져 있어야 하고… 해서 각 비트 단위로 조건을 생각하면 $a + b = c + d$ 여야 한다는 것을 알 수 있습니다 (충분조건은 아닙니다)
따라서, $N$개의 수에 대해 그 합을 바꿀 방법은 없습니다. 합을 유지하면서 곱을 최소화하는 방법은 최대한 큰 수와 최대한 작은 수로 수의 크기 갭을 벌리는 것입니다. 이를 위해, 모든 수를 OR하여 하나를 만들고, 앞으로 그 수는 건드리지 않는 방법으로 모든 수에 켜진 bit의 union에 해당하는 수를 하나 만들어서 앞으로의 연산에서 제외하는 식으로 진행하면 됩니다.
이 구현은 $O(N^2)$ 이기 때문에, 더 줄여야 합니다. 특정 비트 $k$번을 생각하고, $k$번 비트가 $N$개의 수를 통틀어 몇 번 켜지는지 확인하여 구현하면 $O(30 N)$ 에 해결할 수 있습니다.
이문제까지 해결한 다음, 다시 스코어보드를 확인했는데 CDEFG가 풀린 숫자가 거기서 거기인 신기한 스코어보드를 보고 좀 당황했습니다.
Phase 2 : Spurt (60분 - 120분)
E : 뛰는 기물
가로와 세로로 나이트처럼 움직이되, $(m, n)$칸 움직일 수 있는 (또는 $(n, m), (-n, m)$ 등) $(m, n)$-나이트를 정의합니다. 무한한 정수 격자점 $\Z^2$를 무한히 많은 나이트 move로 커버하기 위해, 최소 몇 개의 시작점 (몇 마리의 나이트) 가 필요한지에 대한 문제입니다.
어렵지 않은 관찰로 시작합니다.
- $\gcd(m, n) = g > 1$ 이면, 전체 보드를 $g * g$ 칸 정사각형으로 분할했을 때, 같은 정사각형 안에서는 움직일 방법이 없습니다. 즉, 적어도 $g^2$ 개는 필요합니다.
따라서, $m, n$이 서로소인 경우만 해결하면 됩니다.
여기서 추가로, $(1, 1)$ 나이트 같은 경우, $x + y$ 좌표의 홀짝성을 바꿀 수 있는 방법이 없습니다. 이는 $(3, 3)$나이트나, $(3, 5)$ 등 다른 (홀수, 홀수) 나이트도 가지고 있는 문제입니다. 이유는 $x + y$, $x - y$ 가 모두 짝수이기 때문입니다. 이를 해결하기 위해 적어도 2마리가 필요할 것입니다.
그렇지 않고, $(2, 3)$ 나이트같은 경우 이 나이트가 모든 칸을 방문할 수 있음을 주장합니다. 이 증명을 엄밀하게 하는 것은 상당히 귀찮은 일이며, 풀이 슬라이드에 잘 나와 있습니다. ㅋㅋ! 저는 엄밀한 증명까지는 하지 않고, 그림을 몇개 그려 보고 대충 지그재그로 잘 움직이다가 밑으로 훅 내려오는 것을 반복하면 $(1, 0)$에 도달할 수 있다고 믿었습니다.
간단히 아이디어만 소개하자면, $(m, n)$ 나이트에서 일반성을 잃지 않고 $n > m$ 이라고 하겠습니다. 이때 $n > 2m$ 인 경우, $n < 2m$ 인 경우를 나누어, 나이트로 잘 움직여서 $(m, n)$ 나이트가 다른 어떤 $(a, b)$ 나이트의 행동을 모두 할 수 있음을 보이고, (이때 a, b를 n, m보다 작게 줄이면서) base case로 $(1, 2)$ 나이트가 $(1, 0)$에 도달 가능함을 이용합니다.
참고로, 체스를 좋아한다면 $(1, 2)$ 나이트로 엔드게임 시점에 바로 옆 칸에 가기 위해 3번의 움직임을 쓰는 상황을 calculate해본 경험이 많을 것입니다. 저는 그래서 조금 재밌었습니다. (비슷한 이치로 장기를 잘 두는 사람은 $(2, 3)$ 나이트도 추가로 머릿속에서 그려지는듯 합니다.)
별개로 저는 이 문제에서 사소한 실수로 4틀했습니다. :( 페널티 싸움에서 패배해서 등수가 낮아진 매우 중요한 원인이 되었습니다.
C : 실 전화기
정오각형으로 노드가 배치된 그래프를 평면에 임베딩하기 위해, 노드를 최소 몇개 움직여야 하는지 찾는 문제.
- 완전그래프 $K_5$는 평면 임베딩이 불가능함이 알려져 있으며, 예제로 주어져 있습니다.
- 여기서 edge를 하나 빼면 평면에 올릴 수 있고, 최대 2개만 움직이면 됩니다.
- 노드를 1개 움직여서 가능한지 아닌지만 판정하면 되고,
- 노드 한개를 충분히 멀리 움직이는 것이 없애는 것과 같은 효과이므로, 하나를 없애서 나머지가 충돌하지 않는지 확인하면 됩니다.
D : 누텔라 트리
트리에 검정색과 빨간색으로 칠해진 정점들이 있는데, 여기서 검정색에서 출발하여 빨간색들만 밟는 ‘누텔라 경로’ 가 몇 개 있는지 세는 문제입니다.
빨간색에 한번 도달하면, 연결된 빨간색들 중 어디에 멈출지만 정하면 되기 때문에, 그 component에서 가능한 경우의 수는 빨간색의 개수입니다. 이를 DSU로 미리 묶어서 처리하면 쉽게 해결 가능합니다.
Phase 3 : Too hard
7문제를 푼 순간, 제가 참가자들 중 가장 먼저 7솔브에 도달했기 떄문에 이거 Div2 우승하는거 아니냐 ㅋㅋ 라고 생각하며 잠깐 설렜습니다. 그런데 생각해보면 CDEFG의 난이도가 비슷해서 생긴 일이므로, 지금 (120분 시점) 6솔인 사람들은 시간이 주어진다면 충분히 7솔브가 가능하고, 저는 E번을 4틀하면서 페널티에서 엄청 밀렸으므로 8솔브를 해야 우승을 노릴 수 있었습니다 (그렇지 않더라도 사실 이 상황에서 저한테 달라질건 없지만요). H와 I 중 무엇을 풀지 고민하다가, H가 인터랙티브라서 I를 풀고자 시도했는데 I번에서도 뭔가 어려움이 많았습니다. $N \sqrt{N}$ 정도까지는 어떻게 잘 우기면 될거 같은데, $N = 2e6$이라서 루트도 허용하지 않는 처참한 시간제한을 보고 다시 H로 도망쳤지만 답이 없었습니다.
대회가 끝나고
매년 SNUPC는 정말 많은 생각이 들게 합니다. 매년 뛰어난 사람들이 몰려오고 있고, 나는 정체된 것이 아닌가 하는 회의감부터, 그럼에도 불구하고 하나씩 풀어나갈 때 나름의 즐거움과 생각하는 과정의 즐거움은 PS를 그만둘 수 없게 하기도 합니다.
내년에는 Div1에 나가보고 싶지만, 어떻게 될지는 모르겠습니다. 내년에 학교에 있을지도 불분명한 상황이라… 이번 H번을 보고, CP 대회에 대한 의욕을 갑자기 훅 잃은 것도 있습니다.