2019 아주대학교 프로그래밍 경시대회(APC) 풀이

Ajou-Programming-Contest , 2019-APC-solutions

2019 아주대학교 프로그래밍 경시대회 (APC)

2019년 5월 26일 제9회 아주대학교 프로그래밍 경시대회(APC, Ajou, Programming Contest)가 열렸습니다.

APC는 아주대학교 학생들을 위한 교내대회로, 경인지역 6개대학 연합 프로그래밍 경시대회 shake!에 출전할 10명의 대표학생을 선발하는 선발전을 겸하고 있습니다. 추가로 2019 APC는 성균관대학교와 한국항공대학교의 2019 shake! 학교 대표 선발전 역시 겸하였습니다.

2019 APC는 정보통신대학 학생을 위한 Divison1과 비전공생 및 복수전공생 학생을 위한 Division2로 나누어 진행되었습니다. Division1의 경우 2019 APC는 Division1 8문제와 Division2 6문제로 구성되었으며 그중 4문제가 공통문제라 총 10문제로 이루어져 있습니다. 자세한 구성은 아래와 같습니다.

Division 1 (문제 풀어보기, 아래 문제를 누르면 해당 풀이로 이동합니다.)

A. APC는 왜 서브태스크 대회가 되었을까?
B. 세훈이의 선물가게
C. 묘수풀이: 모독
D. 그래서 팩 주냐?
E. 아름다운 만영로
F. 아싸 너!
G. 문제집 만들기
H. 이건 버그야!

Division 2 (문제 풀어보기, 아래 문제를 누르면 해당 풀이로 이동합니다.)

A. APC는 왜 서브태스크 대회가 되었을까?
B. 세훈이의 선물가게
C. 생명 게임
D. 묘수풀이: 모독
E. 아싸 너!
F. 문자열 장식

이 포스트는 2019 APC 문제의 풀이와 출제진이 각 문제에 바란 역할과 사담이 담겨있습니다. 순서는 Divison 1, 2가 섞인 알파벳 순입니다.

대회의 방향

2019 APC는 아주대학교 학생을 위한 교내대회일 뿐만 아니라 3개 대학의 shake! 선발전을 겸하고 있으며 동시에 대회 플랫폼인 Beakjoon Online Judge에서 Open Contest 역시 진행되었습니다. 아주대학교 Division 1, 2 / 성균관대학교, 한국항공대학교 선발전 / Open Contest 총 5개 대회가 한 번에 진행되기 때문에 대회 당일 출제진들의 부담도 있었지만 무엇보다 신경 썼던 것은 문제의 난이도 커브였습니다.

Division을 나누었더라도 이제 막 언어를 배우는 신입생부터 백전노장까지 참가할 수 있는 대회에서 적절한 문제 수로 모든 참가자를 배려하기는 어려웠습니다. 그래서 한 문제당 Small/Large의 서브태스크를 쪼갠 뒤 Small을 위한 솔루션이 따로 존재하도록 문제를 만들고, 다듬고, 칼질하였습니다. 목표는 “누구나 무언가는 얻을 수 있는 대회” 였습니다.

특히 신경썼던 것은 문제 설명이었습니다. 프로그래밍 대회와 문제풀이를 처음 접하는 참가자들도 많았기 때문에 설명이 충분한지, 이해하기 어려운 표현은 없는지를 계속 검토했고 이해에 도움을 줄 그림과 예제 역시 신경써서 제작하였습니다. 그러다보니 문제가 길어져 이것 나름대로 참가자들에게 피로감을 줄 수 있었지만 이해를 우선하는 것이 맞다고 생각했습니다. 또한 교내대회를 겸하기 때문에 대부분의 문제는 대학교 전공과정에서 접할 수 있는 내용 안에서 출제하려 노력하였습니다.

난이도를 Small, Large에 넓게 분포시키다 보니 Open Contest를 제외한 대회의 참가자들에게는 Small 문제를 먼저 풀도록 유도할 필요가 있었습니다. 이를 위해 Small과 Large 문제의 배점을 각 100점, 40점으로 많은 차등을 두었습니다. 결과적으로 Small 전략 유도는 성공적이었지만, 교내에서 Large 문제들이 빛을 보지 못해 많이 아쉬웠습니다. 어쩌면 모두가 만족할 수 있는 대회라는 것은 유니콘 같은 게 아닐까요?

1A/2A. APC는 왜 서브태스크 대회가 되었을까? (문제)

spectaclehong과 Acka가 함께 출제했습니다. 대회의 A번의 경우 선제 전에 미리 만들지 않아도, 출제 과정에서 자연스럽게 만들어지곤 합니다. 이 문제 역시 좋은 서브태스크 대회를 위해 고민하다 참가자들이 이 고뇌를 함께 알아줬으면 좋겠다! 하는 마음에 만들어진 문제입니다.

모든 문제 중 가장 쉬운 문제로 모든 참가자가 한 문제 이상은 풀기를 바라며 제작되었습니다. 문제에 있는 표는 실제 Division1 문제에 대한 출제진 평가 난이도 스포일러입니다. 이 힌트를 발견하고 따라 푸는 참가자가 있기를 바랐지만 가뜩이나 긴 지문에 다들 스크롤을 내린 것 같습니다.

서브태스크1 - C++ 풀이 코드
- $N=K$ 이기 때문에 현정이가 풀 수 있는 모든 문제의 점수 합이 답입니다.
서브태스크2 - C++ 풀이 코드
- 현정이는 주어진 $N$개의 문제 중 $K$개의 문제만 풀 수 있습니다.
- 현정이가 100점을 얻을 수 있는 문제 개수를 $A$개, 140점을 얻을 수 있는 문제 개수를 $B$개라고 합시다.
- 140점을 얻는 문제를 많이 풀수록 이득이므로, 실제로 140점을 얻는 문제 개수를 $cnt2 = min(B, K)$라고 정의합시다.
- 남은 문제를 100점짜리 문제로 채워야 하므로 그 개수를 $cnt1 = min(A, K - cnt2)$라고 하면 답은 $cnt2 \times 140 + cnt1 \times 100$ 이 됩니다.

문제 본문은 2019 APC가 왜 Small/Large로 이루어진 서브태스크 형식을 채택하게 되었는지에 대한 역사와 교내 참가자들을 위한 대회 전략 힌트를 담고 있습니다. 참고로 저는 정말로 APC를 참가해본 적이 없습니다. 출제는 4년이나 했지만 이 소망은 결국 이루지 못하고 졸업하게 될 것 같습니다.

1B/2B. 세훈이의 선물가게 (문제)

제가 출제한 문제로, 가장 많은 수정이 이루어졌던 문제입니다. A번 보다는 어려우면서 C번보다는 쉽고, 기본적인 자료구조나 아주 쉬운 알고리즘을 사용하는 문제를 목표로 여러 문제들이 거쳐 갔으며, 가장 마지막에 확정된 문제다 보니 외부검수 때까지도 문제 본문이 완전하지 못했습니다. 덕분에 많은 피드백을 받았고 예쁜 그림을 통해 일반 참가자들의 이해를 최대한 끌어올..리려고 노력했는데 잘 되었다면 좋겠습니다.

서브태스크1 - C++ 풀이 코드
- 상민이와 지수 모두 주문이 들어오면 한 번에 모든 포장을 끝냅니다.
- 따라서 입력 순서에 따라 각자 개수만큼 선물을 가져오게 되는데, 이 선물 번호를 하나씩 증가시키며 상민이의 버퍼와 지수의 버퍼에 따로 기록해두면 됩니다.
서브태스크2 - C++ 풀이 코드
- 두 사람은 선물 하나를 포장할 때마다 시간이 걸립니다.
- 주문 및 포장 시간에 따라 번갈아 선물을 가져가는데, 이때 두 사람의 남은 주문 중 더 빨리 시작하는 포장 시간을 찾아 해당 아르바이트생의 버퍼에 쌓아둡니다.
- 큐나 Two-Pointer 알고리즘으로 이를 해결할 수 있습니다.
- 풀이 슬라이드를 보시면 한 단계씩 진행되는 그림과 함께 설명을 보실 수 있습니다.

Open Contest 외에서도 라지까지 많이 풀릴 거라고 예상했고, 그렇게 의도한 난이도였는데 스몰 배점이 너무 컸기 때문인지 교내와 선발전에서 라지가 생각만큼 많이 풀리진 않았습니다.

2C. 생명 게임 (문제)

spectaclehong이 출제하였습니다. Division 2에서 세 번째로 쉬운 문제를 목표로 많은 후보 문제가 거쳐 갔고, 그중 가장 적절하다고 생각되는 문제를 다듬어 배치한 문제입니다.

서브태스크1
- $K=1$이기 때문에 모든 시간에 대해 8방향을 다 보는 시뮬레이션 방식으로도 문제를 풀 수 있습니다.
서브태스크2
- $K$가 커지면 서브태스크1과 같은 방식으로는 시간복잡도가 $O(NMT \times {K}^{2})$이 되어 시간초과가 납니다.
- 각 시간마다 2차원 배열에서의 누적합을 이용하면 $O(NM)$의 전처리를 통해 $(r_1, c_1)$ ~ $(r_2, c_2)$의 누적합을 $O(1)$만에 구할 수 있으므로 이를 $O(NMT)$로 다시 줄일 수 있습니다.
- 누적합에 대한 설명 역시 풀이 슬라이드에서 그림과 함께 보실 수 있습니다.

교내에서 스몰까지만 풀렸습니다. 전공학생들과 shake! 진출권을 노리는 학생들이 모두 Division 1으로 빠지면서 생긴 현상임을 알고 있음에도, Division 2에 남은 세 문제 중 추가로 풀린 문제가 없어 많이 슬펐습니다.

1C/2D. 묘수풀이: 모독 (문제)

제가 출제한 문제입니다. 이전 문제들이 큐, 투포인터, 누적합 등 비교적 간단한 자료구조/알고리즘을 요구하는 문제고, 다음 문제부터는 본격적인 알고리즘 문제들이기 때문에 그 간격을 메울 문제가 필요했습니다. 출제된 문제 중 모독이 선택되었는데, 결과적으로 1D보다도 덜 풀린 문제가 되었습니다.

“모독”이라는 특정 게임의 효과를 설명하는 내용이라 해당 게임을 모르는 참가자들에게는 꺼릴만하지 않았나 하는 생각이 대회 끝나고 들었습니다. 출제진 4명 모두가 해당 게임 유저이며 설명을 최대한 친절하게 한다고 했는데 오히려 그게 지문을 읽는 피로감을 높인 것 같습니다. 외에도 해당 게임 유저들에게는 너무 익숙한 개념이라 이런 부분에서 차이가 발생하는 것은 공평하지 못한 것 같아 문제의 완성도와는 별개로 반성하고 있습니다.

서브태스크1 - C++ 풀이 코드
- 현정이의 전장에는 최대 하나의 하수인만 존재합니다.
- $N=0$이라면 현재 전장에서 모독각이 성립하는지 확인합니다.
- 현재 하수인들의 생명력이 있을 때 모독각이 성립하는지를 판단하기 위해서는 카운팅 소트를 통해 1부터 최대 생명력까지 빈 구간이 없는지 확인해도 좋고, 단순히 소팅하여 1이 존재하는지와 소팅했을 때 $i$번째 생명력이 $i-1$번째 생명력과 1 이하로 차이나는지 확인하는 방법도 가능합니다.
- $N=1$이라면 현정이 전장의 하수인이 상대 전장의 어떤 하수인을 공격할지 모든 결정을 다 확인할 수 있습니다.
- 모든 서브태스크 상황에서 모독은 항상 마지막에 써도 가능/불가능이 바뀌지 않습니다.
- 따라서 현정이의 하수인이 상대 전장의 $[1, M]$번 하수인 중 하나를 공격한 뒤 모독각이 성립하는지를 확인하면 됩니다. 이때 상대 하수인을 공격하지 않는다는 선택지도 있음에 주의합니다.
서브태스크2 - C++ 풀이 코드
- 현정이의 $[1, N]$번 하수인이 각자 공격할 상대 하수인을 결정하면, 모든 경우의 수를 다 확인할 수 있습니다.
- 현정이의 $[1, N]$번 하수인은 각자 공격하지 않거나, 상대 하수인 중 $[1, M]$번 중 하나를 공격할 수 있습니다. 공격하지 않는다는 것을 0번을 공격한다로 처리하면 편리합니다.
- 총 경우의 수는 ${(M + 1)}^{N}$가지가 나옵니다. 각 경우를 DFS 등으로 시뮬레이션한 뒤, 모독각을 확인합니다.
- 공격할 때에는 공격력이 작은 하수인부터 공격해야 합니다. 만약 현정이의 $n_1, n_2$ 하수인이 모두 상대방의 $m_1$ 하수인을 공격해야만 모독각이 성립하는 경우, $n_1$의 공격력이 $n_2$의 공격력보다 크고, $m_1$의 생명력이 $n_1$의 공격력보다 작다면 $n_1$이 $m_1$을 공격하면 $m_1$이 죽기 때문에 $n_2$가 $m_1$을 공격할 수 없게 됩니다. 예제 5번을 직접 해보시면 좀 더 이해가 쉽습니다.

서브태스크2의 마지막 주의점이 예제 5번입니다. 출제진 모두가 한 번씩 놓쳤던 부분으로, 저도 자려다가 문득 생각이 나 데이터를 보강하고 솔루션을 수정하였습니다. 출제 기간이 두 달이나 있었던 점에 진심으로 감사합니다. 이 케이스를 예제로 주느냐 마느냐로 결과가 많이 차이 날 듯해 많이 고민하였는데, C번 치고 코드 구현량이 있는 편이라 다른 곳에서 고생하지 말라고 5번 예제로 추가하게 되었습니다. 결과적으로 좋은 선택이었다고 생각합니다.

1D. 그래서 팩 주냐? (문제)

역시 제가 출제한 문제입니다. Division1의 A, B, C, D를 출제하게 되었는데 문제 풀을 구성할 때 spectaclehong과 myHan이 신나서 교내대회 높은 난이도 문제를 마구 내길래 저는 허리 문제를 출제하려고 노력했습니다. 정작 허리가 아니라 발목 문제가 부족했던 것 같지만, 이 노고를 누가 알아줬으면 좋겠어서 슬쩍 적어봅니다. 출제된 문제 중 DP 문제가 너무 쉽거나 난해하여 다 탈락하고 남게 된 유일한 DP 문제입니다.

서브태스크1
- 원본 문제인 서브태스크2의 풀이가 DP고, 데이터 제한을 줄인 나이브 풀이 중 마음에 드는 게 없어 스몰 문제를 만들기 위해 여러 시도를 했던 문제입니다. 결과적으로 입력 그래프의 형태를 제한했고, 마음에 드는 난이도의 문제가 되었습니다.
- 시작 화제와 $N$번 화제를 제외한 모든 화제의 들어오는 간선과 나가는 간선의 수가 1이라는 것은 시작 화제를 고르면 $N$번 화제까지는 일직선으로 대화가 진행됨을 의미합니다.
- 어떤 시작 화제 $S$를 준표가 골랐을 때, $S$에서 $N$으로 향하는 직선 대화 중 화제의 개수가 짝수인 것의 개수를 $even$이라고 합시다. 이때 두 번째 화제를 고르는 것은 만영이며, 당연히 짝수 경로의 화제를 고르려 할 것입니다. 즉 $S$ 화제로 시작했을 때 준표는 $even$번만 정색하면 만영이가 홀수 경로를 고르게 할 수 있으며, 이후는 직선 대화로 준표가 $N$번 화제를 고르게 됩니다.
- 단, $S$에서 시작하는 홀수 경로가 없다면 준표는 $S$를 시작 화제로 골라서는 안 됩니다.
- 따라서 정답은 홀수 경로가 존재하는 모든 시작 화제의 $even$값 중 최솟값이 됩니다.
- 홀수 경로의 존재 여부와 짝수 경로의 개수는 BFS/DFS 등의 그래프 탐색 기법을 이용하면 쉽게 구할 수 있습니다. 서브태스크1의 $N$ 제한은 1,000인데 이는 adjacency list를 이용한 그래프 표현에 익숙하지 않은 학생들을 위해 $N$x$N$ 배열로 그래프를 표현할 수 있도록 줄인 것입니다.
서브태스크2
- 어떤 대화 $v$에서의 최소 정색 횟수를 구하기 위해서는 이후 대화에서의 최소 정색 횟수를 먼저 알아야 합니다. 각 시작 화제에서 DFS 탐색을 하며 방문을 종료할 때 아래 테이블을 채우면 이런 동작이 가능합니다.
- $DP[v][0]$: $v$ 화제를 준표가 골랐을 때, 준표가 이후 $N$번 화제를 고르기 위해 해야 하는 최소 정색 횟수
- $DP[v][1]$: $v$ 화제를 만영이가 골랐을 때, 준표가 이후 $N$번 화제를 고르기 위해 해야 하는 최소 정색 횟수
- 각 화제로 오는 경로가 홀수였는지 짝수였는지에 따라 이후 각자의 행동이 달라지므로 각 화제를 누가 고른 상태인지에 대한 정보가 추가로 필요합니다.
- 두 테이블의 점화식은 조금 다르며, 이는 풀이 슬라이드에서 그림과 함께 보시는 것을 추천드립니다.

1E. 아름다운 만영로 (문제)

myHan이 출제했고 spectaclehong이 본문을 작성하였습니다. 문제도 깔끔하고 myHan이 출제한 문자열 3문제 중 가장 먼저 내야 하는 문제 1Pick으로 뽑혔습니다. 문자열 문제들이 종종 그렇듯 다양한 풀이가 가능해 개인적으로 좋아하는 문제입니다.

서브태스크1
- 입구에서부터 DFS를 통해 탐색하며 지금까지 지나온 꽃을 기록해둡니다.
- 어떤 쉼터 $v$에 도착했을 때 지금까지 지나온 산책로의 길이가 $|P|$보다 길거나 같다면 마지막으로 지나온 산책로의 꽃 $| P |$개가 만영로와 일치하는 확인하고, 일치한다면 답을 1씩 증가시킵니다.
- 한 번 확인하는 데에는 $O(|P|)$의 시간복잡도가 걸리므로, 서브태스크1을 $O(N|P|)$의 시간복잡도로 풀 수 있습니다.
- 각 쉼터에 대해 만영로의 몇 번째까지 동일했나를 기록하는 BFS로도 풀 수 있습니다.
서브태스크2
- 서브태스크2는 $N$과 $|P|$가 더 크기 때문에 같은 방법으로는 시간초과를 받게 됩니다.
- $N$개의 산책로를 다 방문하여 확인하는 것을 피할 수 없다면, 만영로와 비교하는 부분의 로직을 살펴봅시다. 이를 문자열 매칭 알고리즘을 통해 줄일 수 있습니다.
- 첫 번째 방법은 DFS 탐 색과 함께 지나온 산책로의 해시값을 굴려나가며(누적 가산하여) 만영로의 해시값과 한 번에 비교하는 Rabin-Karp 알고리즘입니다. 풀이 슬라이드에 그림과 함께 설명되어 있습니다.
- 두 번째 방법은 KMP 알고리즘입니다. 만영로에 대한 failure function을 미리 구해두고, $v$에서 $u$로 향하는 산책로에 대해 해당 인덱스의 다음 꽃과 일치하는지, 아니라면 failure link를 재귀적으로 타고 알맞은 인덱스를 찾아갑니다. 그리고 이대로 작성하시면 시간 초과를 받습니다.
- 이 문제를 만들 때에 가장 노력했던 부분으로, 만약 $|P|$의 마지막 한자리를 두고 갈 수 있는 쉼터들이 굉장히 많고, 해당 쉼터들이 모두 failure link를 $|P|$만큼 거치게 된다면 최악의 시간복잡도는 여전히 $O(N|P|)$입니다.
- KMP의 선형 시간복잡도는 문자열 역시 선형일 때만 성립한다는 것을 기억합시다. 이를 해결하기 위해서 우리는 한 번 경험한 failure link의 종착점을 기록하고, 이후 이를 참조하는 방법이 있습니다. 네, memoization인가 하는 그거요. 각 failure에 대해 유효한 상태는 총 (만영로의 길이)$\times$(꽃의 종류)이므로, 총 시간복잡도는 $O(N + 26|P|)$로 줄어듭니다.

출제자인 myHan은 원래 KMP를 정해로 문제를 설계했지만, 롤링해싱의 간편함에 반하여 해시를 정해로 바꾸었다고 합니다..만 사실 KMP로 풀이 슬라이드를 만드는 게 더 힘들어서 정해를 바꾼 게 아닐까 싶습니다. 트리에서의 라빈카프와 트리에서의 KMP memoization 둘 모두 서로의 장점이 있으니 한 번씩 해보시면 좋을 것 같습니다.

1F/2E. 아싸 너! (문제)

spectaclehong의 야심작1입니다. 대회가 5월이었는데 이 문제의 컨셉에 대해서는 1월부터 들었던 것 같습니다. 출제진 내에서도 난이도 평가가 상이했던 문제입니다. 물론 spectaclehong만 쉽다고 하고 저는 가장 어려운 문제로, 다른 두 출제진은 두 번째로 어려운 문제로 평가했습니다. 객관적인 난이도로는 1H가 1F보다 어려운 것은 맞지만, 제가 이 문제의 풀이 컨셉을 듣고도 계속 못 풀었기 때문에 그렇게 측정되었습니다.

난이도 있는 아이디어 문제를 만드는 사람을 보면 참 신기하고 부럽습니다. 이 문제 덕분에 전체 난이도 및 분야가 더 다양해질 수 있었습니다. spectaclehong 최고야!

서브태스크1
- $N$이 최대 7이기 때문에 모든 원순열은 $[1234567, 7654321]$ 범위의 숫자로 식별할 수 있습니다.
- 첫 원순열을 큐에 넣고, 가능한 모든 변환을 해보는 형태의 BFS를 통해 문제를 해결할 수 있습니다.
서브태스크2
- 이제 $N$은 최대 1,000입니다. 당연하지만 전탐색 등의 방법으로는 시간 내에 해결하기도 힘들고, 각 상태를 식별하기도 힘듭니다.
- 아이디어성 문제기 때문에 빠르게 spectaclehong이 그린 예쁜 풀이 슬라이드를 감상합시다. 하지만 제가 해당 그림만으로 이해를 못 해 결국 모든 경우를 다 그려보고서야 풀었기 때문에, 혹시 저와 같은 분이 계실까 봐 그림에 대한 설명을 추가해드립니다.
- a₁으로부터 시계방향으로 두 칸 떨어진 사람만 계속 지목해봅시다.
  a₁ a₂ a₃ a₄ a₅ a₆ a₇ a₈ … a_N-3 a_N-2 a_N-1 a_N 상태에서 a₃을 지목하면
  a₂ a₁ a₃ a₅ a₄ a₆ a₇ a₈ … a_N-3 a_N-2 a_N-1 a_N 이 됩니다. 이 상태에서 a₅를 지목하면
  a₂ a₃ a₁ a₅ a₆ a₄ a₇ a₈ … a_N-3 a_N-2 a_N-1 a_N 이 됩니다. 이 상태에서 a₆을 지목하면
  a₂ a₃ a₅ a₁ a₆ a₇ a₄ a₈ … a_N-3 a_N-2 a_N-1 a_N 이 됩니다. 이를 반복하면 어느 순간
  a₂ a₃ a₅ a₆ a₇ a₈ … a_N-3 a_N-2 a₁ a_N-1 a_N a₄ 가 됩니다.
  (a_N-3, a_N-2 와 a_N-1과 a_N은 N이 홀수인지 짝수인지에 따라 바뀔 수 있습니다.)
  두 번만 더 해봅시다. 이 상태에서 a_N을 지목하면
  a₄ a₃ a₅ a₆ a₇ a₈ … a_N-3 a_N-2 a_N-1 a₁ a_N a₂ 이 됩니다. 이 상태에서 a₂를 지목하면
  a₃ a₄ a₅ a₆ a₇ a₈ … a_N-3 a_N-2 a_N-1 a_N a₁ a₂ 가 되며, 총 $N-2$번의 연산을 통해 모든 자리가 반시계방향으로 2칸 이동한 원순열을 만들 수 있습니다.
- 따라서 우리는 $N$이 홀수일 때는 언제나 가능하며, $N$이 짝수일 때 짝수 칸 이동한 원순열 역시 가능한 것을 알 수 있습니다. $N$이 짝수일 때 홀수 칸 이동한 원순열은 불가능한데, sepctaclehong이 외부의 도움을 받아 증명해냈지만 제가 듣지 않아 알려드릴 수가 없네요.
- 이제 문제는 지목 횟수인데, 최악의 경우 $N$이 홀수일 때 시계방향으로 한 칸 이동하기 위해서는 반시계방향으로 2칸씩 이동하는 연산을 $N - 1$번 하게 됩니다. 서브태스크2는 충분히 통과하겠군요.
서브태스크3
- 아래를 보기 전에, 서브태스크3의 경우 이 방법을 먼저 찾은 분들을 위한 보너스 점수 개념으로 만점까지 노력할 필요는 없다는 spectaclehong의 말을 미리 전합니다.
- $N$이 1999, 2000이 되면 어떻게 될까요? 짝수의 경우 중간을 기점으로 가까운 쪽으로 시계/반시계방향을 정하여 돌리면 $N/4$번 연산으로 가능합니다. 하지만 홀수칸 이동을 하려면 아무리 잘 돌려도 $N/2$번의 연산이 필요합니다.
- 이제 새로운 규칙을 발견해야할 때입니다. 이번에는 시계방향으로 한 칸만 움직이는 것을 목표로 합니다. 이를 위해 $a_1$으로 부터 시계 방향으로 두 칸 떨어진 사람을 지목한 뒤, 반시계 방향으로 한 칸 떨어진 사람을 지목하는 것을 반복합니다.
- a₁ a₂ a₃ a₄ a₅ a₆ a₇ a₈ a₉ a₁₀ a₁₁ 상태에서 a₃을 지목하면 a₁을 한 칸 당겨옵니다.
  a₂ a₁ a₃ a₅ a₄ a₆ a₇ a₈ a₉ a₁₁ a₁₀ 이 됩니다. 이 상태에서 a₂를 지목하면 a₁을 한 칸 밉니다.
  a₂ a₃ a₁ a₅ a₄ a₆ a₇ a₈ a₉ a₁₁ a₁₀ 이 됩니다. 다시 a₄를 지목하면
  a₂ a₃ a₅ a₁ a₄ a₇ a₆ a₈ a₉ a₁₁ a₁₀ 이 됩니다. 이 상태에서 a₅를 지목하면
  a₃ a₂ a₅ a₄ a₁ a₇ a₆ a₈ a₉ a₁₁ a₁₀ 이 됩니다. 이 상태에서 a₆을 지목하면
  a₃ a₂ a₅ a₄ a₇ a₁ a₆ a₉ a₈ a₁₁ a₁₀ 이 됩니다. 이 상태에서 a₇을 지목하면
  a₃ a₂ a₄ a₅ a₇ a₆ a₁ a₉ a₈ a₁₁ a₁₀ 이 됩니다. 이 상태에서 a₈를 지목하면
  a₃ a₂ a₄ a₅ a₇ a₆ a₉ a₁ a₈ a₁₀ a₁₁ 이 됩니다. 이 상테에서 a₉를 지목하면
  a₃ a₂ a₄ a₅ a₆ a₇ a₉ a₈ a₁ a₁₀ a₁₁ 이 됩니다. 점점 자리를 찾아가네요. 이제 a₁₁을 지목하면
  a₂ a₃ a₄ a₅ a₆ a₇ a₉ a₈ a₁₀ a₁ a₁₁ 이 됩니다. 이 상태에서 a₁₀을 지목하면
  a₂ a₃ a₄ a₅ a₆ a₇ a₈ a₉ a₁₀ a₁₁ a₁ 이 됩니다. 와! 10번의 지목으로 반시계향으로 정확히 한 칸씩 움직였네요.
- $N-1$번의 연산을 통해 반시계 방향으로 1칸 움직이는 방법을 알아냈으므로, 홀수 칸을 이동하는 경우 1칸을 위와 같은 방식으로, 나머지를 2칸씩 이동하는 방식으로 처리하면 총 ${N}^{2}/4$의 지목 내에 원하는 원순열을 만들 수 있습니다. 물론 $N$이 짝수이며 홀수칸 이동하는 경우는 불가능이므로 제외됩니다.

출제자인 spectaclehong은 이 문제에 대해 “참가자들이 후반에 할 게 없으면 손으로 끄적이다 번뜩하고 풀어주지 않을까?”하며 참가자들의 무료함을 달래줄 거라고 했지만, 대회장에서 종이에 열심히 원순열을 그리는 사람은 없었습니다. 안타깝군요.

2F. 문자열 장식 (문제)

myHan이 출제했고 Acka가 본문을 작성하였습니다. Divison 2의 마지막 문제입니다. Division 2의 경우 비전공자들을 위한 라운드이기 때문에 다른 의미로 고민이 많았습니다. 되도록 심화전공자가 아니어도 알 수 있는 자료구조/알고리즘을 출제범위로 두었고 문제풀이가 처음인 참가자가 대부분이기 때문에 데이터의 크기도 구현하기 쉬운 쪽으로 다듬었습니다.

서브태스크1
- 문자열의 길이가 10만이기 때문에 모든 부분 문자열을 다 확인하는 방법은 시간초과입니다. 아무리 스몰이라도 Division 2의 마지막 문제인데, 단순한 나이브보다는 좀 더 고찰이 필요합니다.
- 이 문제는 Two-Pointer 알고리즘으로 해결할 수 있습니다.
- 현재 확인하고 있는 부분문자열을 $[l, r]$이라는 구간으로 표현합시다. $[l, r]$구간에 모든 패턴이 다 등장한다면, $l$을 증가시킵니다. 만약 한 패턴이라도 부족하다면 모든 패턴을 포함할 때까지 $r$을 증가시킵니다. 이 경계가 되는 모든 부분문자열 중 길이가 최소인 것이 답이 됩니다.
- 이제 모든 패턴이 등장하는지를 어떻게 확인하느냐에 대한 문제인데, 스몰의 경우 패턴의 최대 개수가 10, 각 패턴의 최대 길이가 100이하이므로, 단순 반복문을 통해 구현해도 $O(|S| \times sum(|P|))$의 시간복잡도로 구할 수 있습니다.
서브태스크2
- 패턴의 개수와 길이가 늘어났습니다. 이건 패턴이 등장하는 곳을 전처리하고, 한 번에 확인하라는 의미겠죠?
- 온갖 패턴 매칭 알고리즘이 유효합니다. KMP, Rabin-Karp, Z, Aho-Corasick 등등을 이용하면 패턴의 등장 위치를 전처리하는 데에 $O(|S| + sum|P|)$, 모든 패턴을 포함하는 최단 부분문자열을 탐색하는 데에 $O(|S| N)$이 듭니다.

원래는 제한이 조금 다른 형태로 Aho-Corasick 문제였습니다. myHan이 출제한 문자열 세 문제는 각각 KMP, Aho-Corasick, Suffix Array를 요구하는 문제였는데 이미 후반 난이도 문제가 충분하기도 하고 다른 두 문제는 교내 대회에 내기에는 요구하는 알고리즘이 교과 범위 밖이라 우선 Division 1에 만영로를 배치하였습니다. 이후 각 셋에 문자열 문제는 하나면 족하다 싶어 Aho-Corasick을 칼질하여 지금의 문자열 장식 문제가 되었습니다..만 Division 2에서 시도조차 없이 남겨져 아쉬웠습니다.

1G. 문제집 만들기 (문제)

yuiop8747가 출제한 문제를 Acka와 spectaclehong이 똑같이 오해하여 만들어진 문제입니다. 원본 문제가 뭐였는지는 아무도 모릅니다.

서브태스크1
- 각 문제를 풀기 위해 먼저 풀어야 하는 문제 중 문제집에서 순서가 가장 앞인 것을 $front$, 가장 뒤인 것을 $back$이라고 합시다. $front$와 $back$은 모두 문제집에서의 순서입니다.
- $[x, y]$ 구간의 모든 $front$와 $back$이 $[x, y]$ 안에 있으면 해당 문제집은 풀 수 있습니다.
- 요약하면, $[x, y]$ 구간의 $front$ 최솟값 $F$와 $back$ 최댓값 $B$에 대하여 $x \le F, B \le y$여야만 해당 문제집을 풀 수 있습니다.
- 이를 발견하지 못하더라도 위상 정렬을 통해 비슷한 접근을 할 수 있습니다.
- $N$과 $Q$가 최대 1,000이므로 각 질문에 대해 $O(N)$의 시간복잡도로 문제를 해결할 수 있습니다.
서브태스크2
- $[x, y]$ 범위에서의 최솟값과 최값을 빠르게 구해야 합니다.
- Segment Tree를 통해 Range Minimum(Maximum) Query를 각 질문마다 $O(logN)$에 구현할 수 있습니다.
서브태스크3
- 관계가 삭제되거나 추가됩니다.
- 관계를 추가하는 것은 Segment Tree의 값을 갱신하는 것으로 해결할 수 있습니다.
- 관계를 삭제하기 위해서는 지금까지의 유효한 관계가 기록되어 있어야 합니다. 이는 각 문제마다 set 등의 자료구조를 통해 저장해둘 수 있습니다.
- 관계를 삭제할 때 $front$나 $back$ 값이 변하면 새로운 값으로 Segment Tree를 업데이트합니다.

yuipo8747이 생전 처음 하는 출제에 데이터를 만드느라 많이 고생한 문제입니다. 그 노력이 빛을 봤는지 G번에 배치되었음에도 A, B번 다음으로 많이 풀렸습니다. 물론 모두 스몰이었지만..

대회 초중반즈음 다른 문제보다 G번 스몰이 먼저 풀리고, 이후 다른 참가자들도 연달아 푼 것을 보면 앞의 문제들보다 이 문제가 참가자들에게 더 쉽거나 편하게 다가왔다는 건데, 그게 이 직전의 최소 최대만 보면 된다는 이 문제의 핵심 아이디어가 쉬웠던 건지, 위상 정렬이 참가자들에게 더 익숙한 알고리즘이었던 건지 출제진 모두 의아했습니다. 물론 문제 배치가 라지 난이도를 따라가기에 1G의 스몰은 쉬운 편이 맞지만, C, D의 스몰보다 압도적으로 많이 풀린 것은 의외였습니다.

1H. 이건 버그야! (문제)

spectaclehong의 야심작2이자 2019 APC 최고난이도 문제입니다. 앞의 문제들과도 난이도 격차가 꽤 있으며, 결과적으로 교내대회에서 아무도 보지 않았습니다. 그리고 5개 대회를 합쳐 누구도 풀지 않은 비운의 문제입니다.

출제자의 욕심으로 전투력 계산식이 더 어려운 쪽으로 변경되는 바람에 코딩량이 늘어난 문제입니다. 2019 APC의 경우 코딩이 깔끔한 문제들을 지향했는데 결과적으로 “묘수풀이: 모독”과 이 문제 덕분에 머리도 손도 심심하지 않은 셋이 되었습니다.

서브태스크1
- 정점의 개수가 최대 100개인데 질문의 개수는 최대 100,000개입니다. 이럴 때는 당연히 100개에 대해 전처리로 답을 구해두고, 질문마다 구해둔 답을 출력하는 것이 좋습니다.
- 서브태스크1의 경우 상민이가 고른 각 정정에 대해 지수의 선봉을 남은 $N-1$개의 지역 모두에 대해 계산하더라도 시간 내에 구할 수 있습니다.
- 물론 Division 1의 마지막 문제인 만큼 스몰 솔루션도 알고리즘과 구현량이 있는 편입니다.
서브태스크2
- 트리에서의 DP지만, 정점 기준이 아닌 간선 기준의 DP를 해야 합니다.
- DFS를 통해 일반적인 트리 DP와 같이 풀면 솜털 모양의 트리 등에서 시간초과를 받게 됩니다.
- 한 정점을 루트로 둔 트리에서 필요한 정보들을 계산해둡니다.
- 이후 DFS Order에 따라 루트를 각 정점으로 옮겼을 때 필요한 정보들을 갱신합니다.
- 혹시 이런 문제를 풀어본 적이 없다면 이 문제가 처음 경험을 쌓는 용으로 좋으니 추천드립니다.

마치며

지금까지 준비했던 어떤 대회보다도 오랜 기간, 많은 에너지를 쏟은 출제 과정이었습니다. 운영을 위해 많은 지원해주신 아주대학교 SW중심대학 사업단분들, 외부검수진분들, 출제진 및 대회에 도움 주신 모든 분께 감사드리며 특히 저에 이어 이번 년도 기꺼이 총책임을 맡고 잘 해내어 준 spectaclehong에게 감사합니다.

매년 출제진의 난이도 측정은 실패하지만 올해는 그래도 많이 엇나가지 않은 것 같아 다행입니다. 내년 대회를 누가 맡을지, 어떻게 될지 저는 아무것도 모르고 싶고 모르겠지만 어쨌든 2020 APC도 무사히 치러져 각자에게 의미가 되었으면 좋겠습니다.

Open Contest 참가자를 위해 많은 준비를 했는데, 다른 대회와 겹치면서 참가자가 적었던 것이 아쉽습니다. 이후에라도 이 문제들이 많은 사람들에게 풀렸으면 좋겠습니다.

2019 아주대학교 프로그래밍 경시대회(APC) 풀이