나코더 송년대회는 2016년 경기과학고 32기에서 처음 개최하여 지난 7년간 매년 연말에 개최되어왔다. 올해는 내가 있는 나코더 39기가 대회를 열어야만 했다.
대회 문제들은 나, 문정후(mjhmjh1104), 채이환(chaeyihwan), 이동현(kizen)이 출제했다. 내가 5문제, 이동현이 3문제, 채이환과 문정후가 각각 2문제를 출제했다.
대회 결과
본대회 스코어보드
오픈 콘테스트 스코어보드
의도한 것 보다는 솔브 수가 많이 적었으나, 상위권 분포가 생각보다 잘 나왔다. 1, 2, 3등 팀이 각각 39, 41, 40기 팀이다.
대회 문제 출제
문제 아이디어를 모으는 것은 2년전 나코더 40기 선발고사 때부터 시작했다. 그때 생각한 문제 중 일부는 40기 선발고사에 냈다. 내가 출제한 문제 중 어떤 문제는 3년 전에 문제의 컨셉을 생각하여 1년 전에 풀려서 낸 문제도 있다.
후술할 내용은 문제의 풀이의 간단한 요약과 문제를 만든 과정이다. 자세한 풀이가 담긴 공식 풀이 슬라이드는 곧 BOJ에 업로드 될 예정이다.
출제한 문제 : C, D, G, J, K
출제에 관여한 문제 : E, I, L
내가 출제하거나 관여한 문제만 썼다.
C. Split the SSHS 2
그래프의 특정 구조를 끊었을 때 그래프의 연결성이 어떻게 유지되는가에 대한 주제를 다룬 문제는 많이 있었는데, 이러한 문제들을 보고 이것저것 해보다가 풀려서 냈다. 처음 생각했을 때에는 안 풀릴 것 같아 보였었는데, dfs트리를 만드니 쉽게 풀렸다.
풀이
dfs 트리를 만들자. 세 점을 골랐을 때 제거되는 간선 중에서 트리엣지는 최대 두개까지 있을 수 있다. 트리엣지가 없다면 제거해도 연결성이 유지되므로, 세 점을 골랐을 때 트리엣지가 하나 제거되는 경우, 두 개 제거되는 경우로 나눌 수 있다.
다음과 같은 네 가지의 경우의 수가 있다. 첫 두 가지의 경우는 트리엣지가 하나 제거되는 경우, 다음 두 가지 경우는 트리엣지가 두개 제거되는 경우이다.
- ab가 트리 간선, bc와 ac가 백엣지, c가 a, b의 조상
- ab가 트리 간선, bc와 ac가 백엣지, c가 a, b의 자손
- ab와 bc가 트리 간선, a가 b의 부모, c가 b의 자식
- ab와 bc가 트리 간선, a, c의 부모가 b
네 경우 모두 적절한 전처리를 통해 해결할 수 있다. 전체 시간복잡도는 $O(MlogM)$으로, 선형에 되는지는 확인되지 않았다.
검수진에서 나온 풀이 중 정해가 아닌 것은 aeren 님의 $O(M\sqrt M)$ 풀이가 있다. 아마 그래프에서 크기 3 사이클 개수가 M sqrt M 정도라는 사실을 이용하는 것 같다.
이 문제의 풀이는 학교 수업시간에 생각했다.
D. 순열과 수열
모티브는 2021 사이컴 입부시험의 아래 문제이다.
https://www.acmicpc.net/problem/21607
21607번: Polynomial and Easy Queries
모든 3번 쿼리에 대해, 그 답을 한 줄에 하나씩 출력합니다.
www.acmicpc.net
$f(g(x))=g(f(x))$라는 관찰이 핵심적인데, 저 식을 문제 조건으로 사용해서 문제를 만들었다. $A$와 $B$가 둘다 순열, 둘다 수열, 둘 중 하나만 수열일 경우 4가지를 모두 해 봤는데, $A$만 순열인 쪽이 풀려서 그렇게 했다. 정해는 세제곱을 의도하고 짰는데, 계산해보면 $O(N^2)$이라서 맞는 느낌의 풀이이다.
풀이
일단 주어진 순열을 사이클로 분할한다. 한 $B_x$만 결정하면 $x$와 같은 사이클에 포함된 모든 수의 $B$값이 결정된다는 사실을 확인할 수 있다. 이때 $B_x=y$이고, $x$가 포함된 사이클의 크기가 $y$가 포함된 사이클의 크기의 배수가 아니라면 $B$값에서 모순이 생긴다.
한 사이클에 대해서 그 사이클 크기의 약수인 쪽으로 $B$값을 계산하는 것을 다 해주면 되는데, 나이브하게 해줘도 잘 계산해보면 시간 복잡도가 $O(N^2)$이 되어서 시간 안에 동작한다.
E. 마비노기 가방 정리하기
정후가 가져온 문제이다. 여러 차례의 버프로 본 대회에서 가장 어려운 문제가 되었지만, 원래 버전은 정말 쉬웠다. 버프되기 이전의 조건은 다음과 같다.
- 가방이 하나로 고정, 가방의 R, C 크기는 짝수
- 쿼리가 아무것도 없었다
- 물건의 가치가 다 같았고, 입력은 가방 크기, 2*2 물건의 수, 1*2 물건의 수, 2*1 물건의 수, 1*1 물건의 수 여섯 개였다.
원래 버전의 정해는 내가 발견했었는데, 식정리를 통해 가방에 담을 수 있는 조건을 알 수 있고, 그를 통해 답을 구할 수 있다.
이후 내가 농담삼아 쿼리를 추가해보자고 했는데 그게 진짜 풀려서 이렇게 출제되었다.
총 8번의 제출, 3번의 CE, 4번의 WA, 1번의 RE가 있었는데, 이들 제출은 전부 살짝만 고치면 정해가 됨에도 불구하고 아쉽게 틀린 제출들이다. 그 중 하나를 공개한다.
G. 금고 털이 2
가장 오래 전에 생각한 문제이고, 풀이를 도출해 내는 시간과 세팅하는 시간이 가장 긴 문제였다. 처음 생각한 것은 경기과학고에 입학하기도 전인 2021년 2월로, 그 해 선발고사에 출제된 철도라는 문제를 보고 생각하게 되었다.
22029번: 철도
$N=6$, $K=1$, 철로 E = $[(1, 2), (1, 3), (1, 4), (4, 5), (4, 6)]$인 경우를 생각해 보자. 그레이더는 다음 함수를 호출한다. encode_map(6, 1, X, [(1, 2), (1, 3), (1, 4), (4, 5), (4, 6)]) 왼쪽 그림은 B나라의 철도망을 나타
www.acmicpc.net
그러다 2년동안 못 풀었고, 2023 선발고사 직전에 풀이를 찾았다. 풀이는 세 개의 어려운 관찰을 단계적으로만 해야 풀린다.
전체 셋에서 이 문제만 폴리곤에서의 세팅과 백준 스택에서의 세팅이 다르다. 폴리곤 세팅의 경우, 일반적인 투스텝 문제처럼 인터렉터가 데이터를 생성해 프로그램과 통신하는데 백준 스택의 경우 첫 출력을 두 번째 입력으로 바꿔주는 컨버터를 따로 짰다. 폴리곤에서 투스텝을 세팅하는 경우도 딱히 없고, 자료를 찾기 너무 힘들어서 세팅하는데 오래 걸렸다.
정말 놀랍게도, 실제 대회에서 풀렸다.
풀이
관찰 1. 루트가 있고 루트의 차수가 최대 2인 크기 33인 트리 세 개를 만들고, 한 정점에 세 트리의 루트를 붙여 크기 100의 트리를 만들자. 이 경우, 트리에서 어떤 간선이 제거되어 트리의 일부가 떨어지더라도 트리의 센트로이드는 일정하다.
따라서 주어진 수를 루트가 있고 크기가 33인 트리로 인코딩해 센트로이드에 세 번 붙여 보낸다는 생각을 할 수 있다. 크기가 33이며 루트가 있고, 루트 차수가 2 이하인 서로 구별되는 트리는 약 $4*10^9$개 정도이다. 따라서 이렇게 하면 10억 이하의 수를 보낼 수 있다.
관찰이 하나 더 필요하다. 같은 트리를 센트로이드에 세 번 붙이는 이유는 센트로이드에 붙은 세 개의 트리 중 어느 것이 제거될지 몰라서이다.
관찰 2. 두 수 A, B가 있고, 3A, 3B+1, 3(A xor B)+2를 트리로 인코딩해 붙이면 셋 중 어느 트리가 제거되더라도 A와 B를 복원할 수 있다.
따라서 주어진 수를 $10^9A+B$꼴로 나타내어 보내면 된다.
여담으로 트리를 인코딩, 디코딩할 때 한 정점에 연결된 두 자식 서브트리 크기가 다르다는 조건을 넣으면 구현이 훨씬 쉬워지고, 주어진 숫자 제한을 아슬아슬하게 통과한다. 이쪽 방향이 의도된 풀이이다. 실제 대회에서 이 문제를 푼 팀도 이러한 방식으로 구현했다.
J. 줌
작년 연말에 만든 문제로, 그림판의 자르기 기능을 보고 생각했다. 처음 생각한 버전은 3번 쿼리가 없고 N은 5000에 2차원 문제였다. 현 버전에서 필요한 첫 관찰을 하고 이차원 세그를 쓰면 풀리는 문제였다.
여기서 다른 출제자의 제안으로 문제를 1차원으로 바꾸었고, 코포에서 본 "지금까지 시행한 모든 연산을 다시 실행하는 쿼리"를 추가해 문제를 바꿨다.
풀이의 경우, 단계적인 다섯 가지의 관찰을 모두 해야 풀 수 있다. 처리해야 할 예외도 있고, 시간 복잡도에 대한 증명이 정말 어렵다. 내가 객관적으로 보기에 셋에서 제일 좋은 문제라고 생각한다. 구현은 200줄 정도인데, 생각보다 쉽다. 나도 세팅할 때 30분만에 짰던 것 같다.
K. 카드 색칠 2
실버 난이도를 의도하고 낸 문제였다.
더블카운팅을 쓰는 문제라 조합론과도 관련이 있고, 참가자들 중 KMO 공부를 해본 사람이 많았어서 많이 풀릴 줄 알았는데 아니었다.
N이 작은 예제에서 모든 케이스워크의 오류가 걸러질만큼 예제도 강하게 줬었는데, 아쉽게도 다른 문제를 푸느라 다들 못 잡은 것 같다.
제목을 먼저 생각하고 끼워 맞춘 문제가 2개 있는데, 하나가 이 문제이다.
풀이
조건을 복잡하게 줬는데, $i+1$행은 $i$행을 오른쪽으로 한칸 민 배열과 같다. 1행을 일렬이 아닌, 처음과 끝이 인접한(N열 다음에 1열이 오는) 원형으로 생각하자. 일단 ?가 없다면 다음과 같이 답을 구할 수 있다.
- 1행에서 0, 1, 0이 연속으로 나오는 구간이 있다면 가운데의 1로 인해 총 $N$개의 문양이 생긴다.
- 1행에서 하나 이상의 1이 연속으로 나오는 구간이 있고, 그 구간이 1과 N을 지난다면 (l, ..., N, 1, 2, ..., r과 같은 형태) 그 구간으로 인해 총 세 개의 문양이 생긴다. 위 예제의 왼쪽 아래 그림이다.
- 1행에서 하나 이상의 1이 연속으로 나오는 구간이 있고, 그 구간이 2번 조건에 해당하지 않는다면 그 구간으로 인해 총 두 개의 문양이 생긴다.
전부 1인 경우는 예외처리해야 한다.
이제 더블카운팅을 통해 답을 구하면 된다.
L. 정기 모임 5
원래 문제는 조금 달랐는데, 정점을 선택하면 선택된 정점은 합쳐지지 않고 그 정점의 이웃들만 합쳐지는 문제였다. 그런데 그 문제를 내가 선택된 정점도 포함된다고 잘못 읽었고, 그게 더 깔끔해서 그렇게 바꿨다. 이후 p 조건이 추가되었다.
대회 준비
대회는 경기과학고등학교 본관 3층 강당에서 진행되었다. 준비할게 진짜 많았다. 학교 강당을 빌려서 책상을 배치하고, 멀티탭도 교무실에서 빌려와서 세팅했다. 출제진들은 강당 맨 뒤쪽에 앉아서 관전했다.
풍선
작년 대회와는 다르게, 일반적인 ICPC와 같이 문제를 하나 풀 때마다 풍선을 나눠주기로 했다. 예산과 관련된 문제로 헬륨 풍선을 사는 것이 불가능했고, 플라스틱 풍선 스탠드를 사서 팀마다 주기로 했다. 풍선은 색깔별로 파는 곳을 못 찾아서 색이 랜덤인 풍선 세트를 샀다. 생각보다 풍선 색깔 분포의 표준편차가 커서 괜찮았다. 풍선이 부족할 줄 알았는데, 다행이도 그런 일은 없었다.
문제가 있었는데, 지지대가 조립되어서 오지 않아서 20개가 넘는 풍선 지지대를 다 조립해야만 했다. 책상을 배치하고 책상마다 하나씩 두었다.
여담
- K와 L은 문제 제목을 먼저 정하고 거기에 문제를 끼워맞추었다. L의 제목인 "정기 모임 5"는 송년대회에 올해로 다섯 번째로 출제되는 정기 모임 시리즈이다.
- D가 들어갈 자리에는 원래 decremental convex hull을 사용하는 다이아 상위 기하 문제가 있었다.
- K가 들어갈 자리에는 코드가 300줄이 넘는 루비 자료구조 문제가 있었다.