나는코더다 2019 송년대회 이야기

작성일 | In , |

머릿말

2019년 12월 12일과 14일에 진행되었던 나는코더다 2019 송년대회(교내 / Open)에 관하여, 이제나마 글을 적는다.

그 당시 나는 대회가 끝나자마자 이 글을 올리고 싶었는데, 개인 블로그가 없었는지라… 많이 늦었지만, 최대한 기억을 되살려서 글을 몇 자 적어본다.

2019년이 되자마자 나는 ‘나는코더다 기장으로서 대회를 열어야 한다’는 생각을 가지고 있었다. 연초부터 세빈이를 나와 함께 할 출제위원 자리로 앉혀놓고, 대회 문제를 준비하였다. 거의 1년 가까이 문제 아이디어를 모아두었기 때문에, 출제에 있어서 큰 어려움은 없었던 것 같다.

대회 문제는 나와 세빈이가 전부 만들었지만, 대회를 운영함에 있어 그 나머지 부분은 여섯 분의 훌륭한 외부검수진이 빈틈없이 채워주셨다. (사전순으로) cubelover, imeimi2000, jwvg0425, koosaga, rkm0959, TAMREF. 모두 귀중한 시간을 내주시며, 문제의 퀄리티를 크게 높여주심과 동시에, 대회 전반에 있어 값진 피드백을 아낌없이 주셨다. 이 분들에게 다시 한 번 감사의 말씀을 드린다.

또한, 송년대회가 더욱 즐거운 대회가 될 수 있도록 상품과 간식 등을 아낌없이 지원해주신 NEXON과 관계자 분들께도 깊은 감사의 말씀을 드린다.

대회 개요

문제 이름 출제자 First Solve (교내) First Solve (Open)
평면 분할 윤교준 지학 전공 (김수민, 신재훈) - 4분 N/A
라면 사기 윤교준 킹장배빵빵 (황인성, 김도영B, 이도훈) - 80분 august14 - 11분
분할하기 윤교준 대가리 큰 곰돌이 푸를 사냥하는 명 윅은 노래를 부르다가 특별상만을 노린다. (성재용, 신명진, 조강현) - 26분 ainta - 15분
다오의 데이트 윤교준 1111 (박준호) - 38분 povwhm - 27분
참 어려운 문제 윤교준 HLD조아 (정희승, 임성재, 최승민) - 192분 cki86201 - 29분
촛불과 그림자 윤교준 No Solve No Solve
피아노 연주 김세빈 뚝심햄구이 (이종영, 안지민, 최은수) - 214분 tlwpdus - 22분
보고 정렬 김세빈 🇰🇷815🇰🇷 (고동현, 이민제, 이강민) - 19분 kcm1700 - 29분
비행기 타고 가요 윤교준 뚝심햄구이 (이종영, 안지민, 최은수) - 23분 ainta - 78분
Bad Hair Day와 기댓값 김세빈 뚝심햄구이 (이종영, 안지민, 최은수) - 136분 ainta - 159분
정점 찾기 윤교준 🇰🇷815🇰🇷 (고동현, 이민제, 이강민) - 185분 august14 - 99분
정기 모임 김세빈 뚝심햄구이 (이종영, 안지민, 최은수) - 195분 onjo0127 - 158분
분수 계산 윤교준 의문부호의 꼭두각시 (김석표, 이민규, 이민준) - 172분 ainta - 90분

“평면 분할” 문제는 교내 대회에만 출제되었다. 놀랍게도 교내와 Open 모두에서 “촛불과 그림자”를 제외한 모든 문제가 풀렸다.

여담이지만, “촛불과 그림자”를 제외한 모든 문제의 출제자 정해 코드는 아주 짧다. (“촛불과 그림자” 제외) 평균 C++ 코드 길이는 700 bytes밖에 되지 않는다. 대회 문제의 퀄리티와 풀이의 깔끔함을 강조하고 싶다.

세빈이가 모든 문제의 풀이를 아주 깔끔하게 정리해주었다. [세빈이의 풀이 슬라이드]

대회 문제

평면 분할

개요

출제자 : 윤교준 / 데이터 제작자 : 윤교준
운영진의 최단 코드 : 200 bytes (C++), 49 bytes (Python)
교내 First Solver : 지학 전공 (김수민, 신재훈) - 4분

이차원 평면에 기울기가 $-1$, $0$, $1$인 직선을 최대 $N$개 그릴 수 있다.
직선에 의해 분할되는 영역의 개수의 최댓값을 구하시오.

모든 참가자가 풀 수 있는 문제를 하나는 내야겠다고 생각해서 만들었다. 난도가 아주 낮기 때문에 Open에는 출제하지 않았다.

교내의 잘하는 팀은 문제를 읽자마자 바로 풀지 않을까 생각했지만, 실제로는 First Solve가 의외의 팀이 대회 시작 후 4분에 푼 것이라 당황스러웠다.

정답률은 84%로 최대고, 참가한 모든 팀이 풀어서 ‘맞았습니다’를 받았다. 다만, $\frac{N(N+1)}{2} + 1$를 출력하는 오답 코드가 많아서 아쉽다.

풀이

한 점에서 만나는 세 직선이 있다면 이들 중 하나를 살짝 평행이동함으로써, 세 직선이 한 점에서 만나지 않도록 함과 동시에 답을 더 크게 만들 수 있다. 고로, 해의 어느 세 직선도 한 점에서 만나지 않는다.

기울기가 $-1$, $0$, $1$인 직선을 각각 $a$, $b$, $c$개 그린다고 하자. 그러면 분할되는 영역의 수는 $(a+1)(b+1)(c+1) - abc$다.

$a+b+c \le N$를 만족하는 모든 $(a, b, c)$ 쌍에 대하여 영역의 수를 구해, 그 최댓값을 출력하면 된다.

더 고민해보면, 답은 항상 $\left\lfloor{\frac{N^2}{3}}\right\rfloor + N + 1$임을 알 수 있다.

라면 사기 (Small / Large)

개요

출제자 : 윤교준 / 데이터 제작자 : TAMREF, 윤교준
운영진의 최단 코드 : [Small] 479 bytes (C++) / [Large] 496 bytes (C++)
교내 First Solver : 킹장배빵빵 (황인성, 김도영B, 이도훈) - 80분
Open First Solver : august14 - 11분

$N$개의 라면 공장이 있다. 각 공장에서 정해진 수량의 라면을 사고자 한다.
연속한 1개, 2개, 3개의 공장에서 라면을 하나씩 구매하는 비용이 각각 $B$, $B+C$, $B+2C$다.
최소 비용으로 구매할 때, 그 금액을 구하시오.

IZhO 2011의 Skyline 문제에서 제한을 크게 한 문제다. 교내 대회에는 $N \le 10^4$, $A_i \le 10^4$, $B = 3$, $C = 2$라는 추가적인 조건을 넣어서 Small 버전으로 출제하였다. 그렇기에 Small 버전으로 문제를 접한 교내 팀은 옳바른 풀이를 찾는 것이 Large 버전보다 더 어려웠을 것이라 생각한다. 동적계획법 풀이는 시간복잡도가 $O(N^3)$로 느리고, 그렇다고 $O(N^2)$ 혹은 $O(NX)$에 동작하는 올바른 풀이는 찾기 어렵기 때문이다.

정해는 놀랍게도 선형에 풀린다. 모두가 Greedy 문제임을 알지만, 올바르게 접근하기 어려움은 사실이다. 교내와 Open 모두에서 정답률이 17%임이 이를 말해준다. Scoreboard가 비공개였다면 모두가 한 번씩은 제출하고 틀리지 않았을까 생각한다.

개인적으로 내가 만든 가장 아름다운 문제라고 생각한다. 짧은 Description, 깔끔한 소스코드, 그러나 어려운 Greedy 풀이. 덤으로, Open에서 4위를 한 ainta가 이 문제를 풀었다면 3위를 차지하여 상품을 얻을 수 있었다. 어떻게 보면 이 문제가 상품 수상권을 갈랐다고도 말할 수 있을 것이다.

풀이

만약 $B < C$라면, $C := B$라고 가정해도 답이 변하지 않는다. 이제, $C \le B$가 성립한다.

$1$번 공장부터 $i$번 공장까지 최소 비용으로 라면을 구매하는 해를 이용하여, $i+1$번 공장까지 구매하는 최적해를 구하는 방법을 서술할 것이다.
아래의 세 과정을 순서대로 시행하되, 각각의 과정을 최대한 많이 시행한다:

  1. “$i$번 공장에서 비용 $B$로 라면 구매”를 “$i$번과 $i+1$번 공장에서 비용 $B+C$로 라면 구매”로 변경.
  2. “$i-1$번과 $i$번 공장에서 비용 $B+C$로 라면 구매”를 “$i-1$번, $i$번, $i+1$번 공장에서 비용 $B+2C$로 라면 구매”로 변경.
  3. $i+1$번 공장에서 비용 $B$로 라면 구매.

정당성 증명은 꽤 단순하다. 각 라면마다 B, C, D 중 하나의 알파벳을 적는다고 하자. 각 알파벳의 의미를 설명하자면:

  • “B를 적는 것”은 “그 라면을 비용 $B$로 구매함”을
  • “C를 적는 것”은 “이전의 B가 적힌 라면과 엮어, 라면을 비용 $C$로 구매함”을
  • “D를 적는 것”은 “두 공장 전의 B가 적힌 라면과, 이전의 C가 적힌 라면과 엮어, 라면을 비용 $C$로 구매함”을 의미한다.

총 구매 비용은 $B \times (\text{B가 적힌 라면의 개수}) + C \times (\text{C나 D가 적힌 라면의 개수})$이므로, B를 최대한 적게 적는 것이 목표다.

이제 위에서 서술한 과정의 의미를 파악해보자. 각 과정의 의미는 다음과 같다:

  1. $i$번 공장의 “B가 적힌 라면”을 최대한 많이 이용하여, $i+1$번 공장의 라면에 C를 적는다.
  2. $i$번 공장의 “C가 적힌 라면”을 최대한 많이 이용하여, $i+1$번 공장의 라면에 D를 적는다.
  3. 남은 $i+1$번 공장의 라면에 B를 적는다.

만일, 위와 같은 과정으로 만들어지지 않은 해가 있다면, 그 해에서 B를 C로 고치거나, C를 D로 고치는 작업을 항상 한 번 이상 할 수 있다. 따라서, 제시한 Greedy 풀이는 정당하다.

분할하기

개요

출제자 : 윤교준 / 데이터 제작자 : 윤교준
운영진의 최단 코드 : 239 bytes (C++)
교내 First Solver : 대가리 큰 곰돌이 푸를 사냥하는 명 윅은 노래를 부르다가 특별상만을 노린다. (성재용, 신명진, 조강현) - 26분
Open First Solver : ainta - 15분

어떤 집합이 Bitwise-or 연산에 대하여 닫혀있다면, 그 집합을 “좋은 집합”이라고 하자.
전체집합 $U = { 0, 1, \cdots, 2^N - 1 }$의 부분집합 $A$에 대하여, $\left|A\right| = K$고, $A$와 $U \setminus A$가 모두 좋은 집합이면, $A$를 “$N, K$-분할”이라고 하자.
$N$과 $K$가 주어질 때, “$N, K$-분할”의 존재성을 밝히고, 만일 존재한다면 그 예를 아무거나 하나 출력하시오.

아이디어가 있어야 풀 수 있는 문제를 만들어보았다. 이 문제를 푸는 데, 출제한 나는 며칠이 걸렸고, 검수진 몇몇은 반나절 이상 걸리길래, 나는 문제의 난도가 높다고 생각했다. 교내 대회에서 18팀 중 절반 이상이 못 풀지 않을까 예상했는데, 실제로는 26분만에 First Solve가 나오고, 총 18팀 중 13팀이나 풀어서 굉장히 놀라웠다.

다양한 풀이가 있을 것이라고 생각하고 출제를 했는데, 대부분의 참가자 풀이가 의도된 풀이와 유사하였다. Special Judge는 Or-convolution을 이용하여 $O(2^N N)$에 구현할 수 있으나, 내가 귀찮아서 구현의 정확도가 우선이라고 생각해서 $O(2^{2N})$로 naive하게 구현하였다.

풀이

$N,K$-분할은 항상 존재하며, 이러한 집합을 만드는 방법은 단순하다.

다음 $N+1$개의 집합을 생각하자:

\[\{ 0 \}, \{ 1 \}, \{ 2, 3 \}, \{ 4, 5, 6, 7 \}, \cdots, \{ 2^i, 2^i + 1, \cdots, 2^{i+1} - 1\}, \cdots, \{ 2^{N-1}, 2^{N-1}+1, \cdots, 2^N - 1 \}\]

이제 우리는 다음 두 가지 성질을 관찰할 수 있다:

  • 각 집합의 크기는 $1, 1, 2, 4, \cdots, 2^i, \cdots, 2^{N-1}$다.
  • $N+1$개의 집합 중 몇 개를 골랐을 때, 이들의 합집합과 그의 여집합은 항상 좋은 집합이다.

고로, 우리는 모든 $N,K$-분할을 만들 수 있다. $1 \le K < 2^N$라면, 최상위 비트가 $K$에 포함된 수의 집합이 곧 $N,K$-분할이 된다.

다오의 데이트

개요

출제자 : 윤교준 / 데이터 제작자 : 윤교준
운영진의 최단 코드 : 870 bytes (C++)
교내 First Solver : 1111 (박준호) - 38분
Open First Solver : povwhm - 27분

이차원 격자판 위에 다오와 디지니가 서 있다.
다오는 최대 $N$번 움직일 수 있으며, 각 움직임마다 두 방향 중 한 쪽으로만 이동할 수 있다.
다오와 디지니가 만날 수 있는지 판별하고, 만일 가능하다면 그 방법을 구하시오.

올해 나는코더다 송년대회는 처음으로 외부 기업으로부터 후원을 받았다. NEXON 사회공헌팀에 직접 후원 관련 연락을 드렸고, NEXON 분들께서 흔쾌히 허락해주셔서 정말 기뻤다. 출제·검수 비용과 교내 대회장에 비치할 다과·음료 구매비, 참가자 간식 비용, 우승 상품 등을 모두 지원해주셨다. 학생 대회에 굉장히 큰 후원을 해주셨음에도 불구하고, NEXON은 그 어떤 후원 조건도 제시하지 않으셔서, 감사함을 표현하고자 이 문제를 만들었다.

문제 컨셉은 크레이지 파크에서 가져왔다. 문제를 제작하면서 크레이지 파크를 찾아봤는데 어느새인가 서비스를 종료했더라…. 좌우지간, 후원기업 NEXON에 내가 바치는 문제였기에, 문제 구성과 난이도, 데이터 모두에 신경을 아주 많이 썼다.

쓰다보니 생각이 났는데, 문제의 아이디어는 정종광 선생님께서 제공해주셨다. 출제에 도움을 주신 것에 대하여 정종광 선생님께 고마운 마음을 전해드리고 싶다.

풀이

다오가 움직일 수 있는 방법은 총 $O(2^N)$가지다. $N \le 20$으로 굉장히 작기 때문에, 모든 경우를 전부 시도해도 괜찮다.

의외로, 정답률은 교내 22%, Open 40%로 낮은데, 이는 내가 문제 설명을 깔끔하게 쓰지 못했기 때문이라고 생각한다.

참 어려운 문제

개요

출제자 : 윤교준 / 데이터 제작자 : 김세빈
운영진의 최단 코드 : 816 bytes (C++)
교내 First Solver : HLD조아 (정희승, 임성재, 최승민) - 192분
Open First Solver : cki86201 - 29분

각 정점에 색이 칠해져 있는 트리가 주어진다.
조상-자식 관계이면서 색이 같은 두 정점이 존재하지 않도록 트리의 루트를 잡을 때, 루트로 가능한 정점을 모두 구하시오.

그냥 갑자기 이런 문제가 떠올라서, 풀리는지 제대로 확인도 안 하고 대회 문제 Shortlist에 던져놓았다. 나는 ‘열심히 코딩하면 $O(N lgN)$ 즈음에 풀리겠지’까지만 생각했는데, 세빈이와 imeimi2000가 뭔가 뚝딱뚝딱 하더니 갓 풀이를 만들어 놓아서 정말정말 신기했다.

데이터를 만들기 아주 어려운 문제라고 생각한다. $O(N^2)$ 시간 커팅 야매라던가, 코딩 미스라던가, 랜덤을 섞다던가…. 통과시키면 안되는 풀이가 아주 많고, 트리와 색을 구성하는 것이 아주 까다로움에도 불구하고, 데이터는 아주 완벽하다고 생각한다. 열심히 준비하느라 고생한 세빈이에게 아낌없이 박수를 쳐주자.

풀이 1

이 문제는 교내에서 두 팀, Open에서 네 명이 풀었고, 전부 본 풀이와 비슷한 방법으로 해결하였다.

트리 중 간선 ${ u, v }$을 생각하자. 이 간선을 끊는다면, 트리는 두 개의 트리 $T_u$와 $T_v$로 분리된다. 여기서, $T_u$는 정점 $u$가 포함된 트리, $T_v$는 정점 $v$가 포함된 트리다.

만일, $u$와 색이 같은 $T_v$ 상의 정점이 존재한다면, $T_u$의 모든 정점은 답의 후보에서 제외된다. 이렇게 모든 $N-1$개의 간선에 대하여, 답의 후보를 제거하자. 남은 후보 정점은 모두 루트가 될 수 있음을 보일 수 있다.

따라서, 우리가 구현해야 하는 부분은 크게 두 가지로 볼 수 있다:

  • $T_v$의 정점 중 $u$와 색이 같은 정점이 존재하는지 판별 : DFS Ordering과 같은 색을 가진 정점의 index를 모아두는 $O(N)$ 전처리로, 각 쿼리마다 이분탐색 등으로 $O(\lg N)$에 판별할 수 있다.
  • 답의 최종 후보 정점 결정 : 각 간선에 대하여, $O(1)$에 답이 될 수 없는 부트리의 루트에만 정보를 저장한 후, $O(N)$의 DFS를 통하여, 최종 후보를 알아낼 수 있다.

시간복잡도는 $O(N \lg N)$, 공간 복잡도는 $O(N)$다. 구현 방식에 따라 코딩량이 크게 다른 듯 하다.

풀이 2

이 풀이는 내가 생각한 방법이다. 아무 생각 없이 손만 열심히 움직이는 풀이다.

색이 $C$로 같은 정점을 모두 모아, 트리 압축을 해보자. 이제 두 가지 경우가 있다:

  • 색이 $C$인 정점 중 Leaf가 아닌 정점이 존재하는 경우 : 모든 정점이 답이 될 수 없다.
  • 색이 $C$인 정점이 모두 Leaf인 경우 : 압축된 트리 중 색이 $C$가 아닌 모든 정점이 답의 후보가 될 수 있다.

모든 색에 대하여, 위의 과정을 진행한 후, 모든 답의 후보의 교집합을 구하면 그것이 답이 된다.

트리 압축 테크닉을 언급하고 싶어서, 본 풀이를 적었다. 시간복잡도와 공간 복잡도 모두 $O(N \lg N)$다.

풀이 3

세빈이의 풀이 슬라이드를 보면, “DFS를 돌면서 각 색깔별로 따로 스택을 관리하여 선형에 풀 수 있다.”고 적혀 있는데, 나는 이 의미를 모르겠다. 선형 풀이도 $O(N \lg N)$ 풀이처럼 다양한 듯 하나, 여기서 나는 imeimi2000의 갓 풀이만 설명할 것이다.

다음을 차례대로 관찰하자:

  1. 유일한 색을 가지는 정점의 집합을 $S$라 하자. 답은 $S$의 부분집합이다.
  2. 풀이 2에 의해, 답이 되는 정점은 여러 부트리의 교집합의 형태를 가진다. 고로, 답이 되는 정점은 모두 이어져있다.
  3. 인접한 두 정점 $u, v \in S$을 생각하자. $u$가 루트가 될 수 있다면, $v$ 또한 루트가 될 수 있다.
  4. 따라서 루트가 될 수 있는 정점을 하나만 찾을 수 있다면, BFS 따위를 통하여 다른 모든 답을 $O(N)$에 구할 수 있다.

이제 우리는 루트가 될 수 있는 정점 하나를 찾는 데에 집중할 것이다. 조금 더 정확하게, $1$번 정점과 가장 가까우면서 루트가 될 수 있는 정점 $r$을 찾을 것이다. (답이 공집합이 아니라고 가정하고 있음에 유의하라.)

$1$번 정점을 루트로 했을 때, 정점 $v$의 부트리에 $v$와 색이 같은 정점이 있다면, 우리는 $v$를 “충돌 정점”이라 부르자. 만약에 그 어떤 충돌 정점도 존재하지 않는다면, $r = 1$다. 이제 충돌 정점이 있는 경우에 대하여 다음을 관찰하자:

  1. 모든 충돌 정점은 $1$번 정점과 정점 $r$을 잇는 경로 위에 존재한다. 만일 그렇지 않다면, 이는 $r$이 답이 될 수 없음을 유도한다.
  2. $1$번 정점과 가장 먼 충돌 정점을 $x$라 하자. $r$은 $x$의 부트리에 존재한다.
  3. $r$의 부모 정점은 $x$다. $r$의 부모 정점이 $p \ne x$라면, 다음과 같은 모순이 일어난다:
    1. $p \in S$라면, $r, p \in S$가 서로 인접해 있고 $r$은 답이 될 수 있으므로, $p$ 또한 답이 될 수 있다. 따라서 정의에 의해 $r = p$여야 한다.
    2. $p \notin S$라면, $p$와 색이 같은 정점 $v \ne p$가 존재한다. $r$이 답이 될 수 있으므로, $v$는 $p$의 부트리 안에 있어야만 한다. 이 경우, $p$는 충돌 정점이 되므로, 정의에 의해 $x = p$여야 한다.
  4. $x$의 부트리에 $x$와 색이 같은 정점은 $r$의 부트리에 존재한다.

이제 위의 모든 내용을 종합하여, 아래의 알고리즘을 시행하자:

  1. 한 번의 DFS로 $O(N)$에 정점 $x$를 구한다.
  2. 과정 1.에서 충돌 정점이 없었다면, $r = 1$다.
  3. 과정 1.에서 충돌 정점이 있었다면, 다음 조건을 만족하는 정점 $y$를 찾아, $r := y$로 설정한다.
    1. $y$는 $x$의 자식.
    2. $y$의 부트리 중 $x$와 색이 같은 정점이 존재.
  4. $r$이 답이 될 수 있는지 한 번의 DFS로 $O(N)$에 판별한다.
  5. $r$이 답이 될 수 있다면, BFS 등으로 모든 답을 $O(N)$에 구한다.

우리가 논리를 전개하기에 앞서, 우리는 “답이 공집합이 아님”을 가정하였다. 그러나, 답이 공집합이더라도 위의 알고리즘은 과정 4.에 의해 올바른 답을 알려준다. 따라서, 위의 알고리즘은 정당하다.

시간복잡도와 공간 복잡도 모두 $O(N)$다.

촛불과 그림자

개요

출제자 : 윤교준 / 데이터 제작자 : 윤교준
운영진의 최단 코드 : 2615 bytes (C++)
교내 First Solver : N/A
Open First Solver : N/A

볼록 다각형 내부에 볼록 다각형이 포함되어 있다.
쿼리로 촛불의 위치가 주어질 때, 안쪽 다각형에 의하여 만들어지는 그림자 영역의 넓이를 구하시오.

출제진이 두 명인데, 한 명(본인)은 기하가 세상의 전부라고 생각하고, 또다른 한 명(김세빈)은 기하를 혐오하나 풀라고 하면 군말없이 푸는 사람이다. 그렇다면, 기하 문제가 나온다는 것은 예상 범위 안이라고 생각한다.

교내 대회에서 라이브러리를 미리 준비해서 사용할 수 있게 한 가장 큰 이유가 이 문제의 존재다. ‘기하 라이브러리로 한 번 풀어볼테면 풀어봐라’ 느낌으로 출제했는데, 아무도 기하 라이브러리를 준비하지 않은 점이 조금 아쉽다. 사실 이런 류의 문제가 좋지 않음은 인지하고 있었으나, Open All Solve 방지용으로 출제한 점도 없지 않아 있다.

Open 대회 1위와 2위 수상자는 다른 11개의 문제를 모두 풀고 시간이 남아, 본 문제에도 소스코드를 제출하였으나 아쉽게도 맞지 못하였다. 그들이 제출한 소스 코드를 공개하자면:

1
Ainta trolling so hard
taeyeon_ss의 C++14 코드 (채점 번호 : 16464908)
1
2
3
4
5
#include<iostream>
using namespace std;
int main(){
    cout << "Ainta trolling so hard" << endl;
}
taeyeon_ss의 C++14 코드 (채점 번호 : 16464935)
1
E번 보고 저녁 먹으러 갑니다 ^^
tlwpdus의 Text 코드 (채점 번호 : 16464795)
1
2
3
4
5
6
7
8
#include<bits/stdc++.h>

using namespace std;

int main() {
    cout << "Hello World!" << endl;
    return 0;
}
tlwpdus의 C++14 코드 (채점 번호 : 16465014)

네 번의 제출이 있었으나, 한 번의 컴파일 오류를 제외하고 모두 ‘틀렸습니다’ 판정을 받았다. 살짝만 고치면 정해가 됨에도 불구하고, 그들이 왜 소스코드를 고치지 않았는지 나는 모르겠다.

풀이

촛불의 위치가 쿼리로 주어지지만 않았더라도 이 사단이 나지는 않았을 것이다. 우리는 하나의 쿼리를 $O(\lg N + \lg M)$에 풀기 위하여 다음을 모두 구현하여야 한다:

  • 점과 볼록 다각형 간의 위치 관계 판별 (내부, 외부, 경계 위 판별)
    • 볼록 다각형을 윗쪽 껍질과 아랫쪽 껍질로 분해한다면, 이분 탐색을 이용하여 $O(\lg V)$에 판별할 수 있다. 여기서 $V$는 꼭짓점의 개수다.
  • 볼록 다각형 외부의 점에서 다각형에 그은 접선 구하기
    • 설명의 편의를 위하여, 외부의 점을 $A$, 다각형의 꼭짓점을 $P_1, P_2, \cdots, P_V$라 하자.
    • 아까와 비슷하게, 다각형을 윗쪽과 아랫쪽으로 분해하자. 점 $A$와 각 껍질의 꼭짓점을 잇는 직선의 기울기는 삼분 탐색이 가능한 형태다. 고로, 각 껍질에 대하여 삼분 탐색을 이용하여 접선을 구한다.
    • 또다른 방법으로, 세빈이가 사용한 방법을 소개한다. 직선 $\overleftrightarrow{A P_1}$과 다각형의 교점을 생각하자. $P_1$가 아닌 교점이 선분 $\overline{P_k P_{k+1}}$ 위에 존재한다면, 두 접점은 각각 $P_1, \cdots, P_k$ 중에 하나, $P_{k+1}, \cdots, P_V$ 중에 하나다. 접점은 각 범위 내에서 이분 탐색으로 찾을 수 있다.
    • 두 방법 모두 시간복잡도는 $O(\lg V)$다.
  • 볼록 다각형과 반직선의 교점 구하기
    • 반직선을 $\overrightarrow{AB}$라 하자. 또한, 점 $A$와 $B$는 모두 다각형 내부에 존재한다고 하자. 반직선과 다각형의 교점이 선분 $\overline{P_k P_{k+1}}$ 위에 존재한다면, 두 반직선 $\overrightarrow{A P_1}$와 $\overrightarrow{A P_k}$가 만드는 영역에 점 $B$가 존재하지 않는 반면에, $\overrightarrow{A P_1}$와 $\overrightarrow{A P_{k+1}}$가 만드는 영역에는 점 $B$가 포함된다.
    • $k$의 값은 이분 탐색을 이용하여 $O(\lg V)$에 찾을 수 있다. 이후, 교점의 좌표는 두 직선의 식을 연립하여 구할 수 있다.
  • 부채 형태의 다각형의 넓이 구하기
    • 다각형 $O P_s P_{s+1} \cdots P_e$의 넓이는 $\overrightarrow{O P_i} \times \overrightarrow{O P_ {i+1}}$의 Prefix Sum을 $O(V)$에 전처리해둠으로써 $O(1)$에 계산할 수 있다.

위의 소과정을 모두 구현하였다면, 이들을 조합하여 각 쿼리에 대해 $O(\lg N + \lg M)$에 답할 수 있다. 시간복잡도는 $O(N + M + Q(\lg N + \lg M))$, 공간 복잡도는 $O(N + M)$다.

첨언

내가 문제를 만들고 데이터를 만들었기 때문에, 자업자득으로 나 또한 출제 고통을 엄청 받았다. 올바른 정해 코드를 작성하기까지 수차례 소스코드를 갈아엎었고, Naive 코드와 Checker 코드 또한 작성하기 까다롭기에 힘들었다. 두 거대한 볼록 다각형이 서로 포함 관계에 있어야 하기에, 데이터를 만들기 위하여 다른 문제에 비해 꽤 많은 시간을 들였다.

시간 제한이 1초로 빡빡한 이유는, 좌표 범위의 제약으로 인하여 $N$과 $M$이 $10^5$이 될 수 없기 때문이다. 실수 오차가 $10^{-6}$ 이하인지 엄밀하게 검증하지 않아서, 좌표 범위를 대충 작게 주었는데, $N = 10^5$인 데이터를 만들 수 없다는 점이 조금 아쉽다. 그렇다고 다시 작업해서 이를 고치고 싶지는 않다.

피아노 연주

개요

출제자 : 김세빈 / 데이터 제작자 : 윤교준
운영진 최단 코드 : 711 bytes (C++), 374 bytes (Python)
교내 First Solver : 뚝심햄구이 (이종영, 안지민, 최은수) - 214분
Open First Solver : tlwpdus - 22분

$M$개의 음으로 이루어진 곡을 피아노로 연주하려고 한다.
각각의 음을 어떤 손가락으로 연주할지 결정하여 곡의 난이도의 최솟값을 구하시오.

이 문제는 교내 대회에서 세빈이가 가장 아쉬워한 문제다. 정말로 적게 잡아도 전체의 1/4 이상은 풀 것이라고 예상하였는데, 실제로는 모든 팀이 이 문제를 풀려는 시도를 하지 않아, 결과적으로 1위 팀이 대회가 끝나갈 무렵에 푼 것이 전부였다. 1위 팀이 어려운 문제를 먼저 빠르게 풀어버려서 다른 팀에게 난이도에 대한 혼란을 주고, B번 문제였던 “라면 사기”가 아주 어려웠기 때문에, 대부분이 이 문제를 잡을 시간이 없었을 것이라고 추측해본다.

교내 대회에서는 한 팀밖에 풀지 못했던 반면에, Open에서는 6명이 쉬운 냄새를 잘 맡고 찾아와 풀어주셨다. Open에서라도 잘 풀려서 다행이라고, 세빈이는 대회를 되돌아보며 말하곤 한다.

풀이

곡의 난이도를 결정하는 식 $\left| \left( P_{i+1} - P_i \right) - \left( X_{F_{i+1}} - X_{F_i} \right) \right|$의 의미를 파악한다면, 문제를 더 쉽게 이해할 수 있다. 이는 “인접한 두 음을 연주할 때, 손이 움직이는 거리”로 생각하는 것이 좋다.

이제, 이분 탐색을 적용하여, 최솟값 문제를 결정 문제로 환원하자. 즉, 손이 한 번에 최대로 $L$만큼만 움직일 수 있을 때, 곡을 완주하는 것이 가능한 지 판별하면, 전체 문제를 푸는 데 충분하다.

각 음을 연주할 수 있는 손가락의 번호는 항상 구간을 이룬다는 것을 관찰하여야 한다. 예를 들어, 첫 번째 음부터 $i$번째 음까지 차례대로 연주하여, $i$번째 음을 $S_i$ 이상 $E_i$ 이하 번째의 손가락으로 연주할 수 있다고 하자. 그렇다면, $(i+1)$번째 음은 $S_{i+1}$ 이상 $E_{i+1}$ 이하 번째의 손가락으로 연주할 수 있으며, 이 값은 $S_i$와 $E_i$로부터 계산할 수 있다. 이것이 성립하는 이유는 인접한 손가락의 거리가 $K$로 일정하기 때문이다.

고로, $S_1 = 1$, $E_1 = N$으로 두고, $S_i$와 $E_i$ 값을 차례대로 구하면, 결정 문제를 풀 수 있다. 하나의 결정 문제는 $O(M)$에 풀 수 있으므로, 전체 문제를 $O(M \lg X)$에 해결할 수 있다.

여담

본 문제의 초기 버전에서는 $X_i$ 값이 모두 입력으로 주어졌다. 이 경우에는 각 음을 연주할 수 있는 손가락의 집합이 구간을 이루지 못하기 때문에, $X_i = (i-1)K$로 수정하였다.

독자는 초기 버전의 문제를 $O(M \sqrt{N} \lg X)$나, 혹은 이보다 빠르게 풀 수 있겠는가?

보고 정렬

개요

출제자 : 김세빈 / 데이터 제작자 : 김세빈
운영진 최단 코드 : 239 bytes (C++)
교내 First Solver : 🇰🇷815🇰🇷 (고동현, 이민제, 이강민) - 19분
Open First Solver : kcm1700 - 29분

수열에서 어떤 구간을 잡아 랜덤 셔플하는 작업만을 이용하여, 주어진 순열을 효율적으로 정렬하시오.

길이 $200$의 순열을 $2500$번 이하의 랜덤 셔플을 이용하여 정렬하는, 참신한 문제다.

백준님께서 나는코더다 대회에 Interactive 문제를 낸다면 이 유형을 구현해주겠다고 약속해주셔서, 나와 세빈이가 출제한 두 개의 Interactive 문제 중 하나다. 랜덤 셔플을 정말로 ‘랜덤’하게 구현해야 하기 때문에, Interactive 유형이 아니라면 출제될 수 없는 문제라고 생각한다. 나는코더다 2019 송년대회를 기점으로 하여, 앞으로 Interactive 유형의 질 좋은 문제가 많이 나오기를 기대한다.

나는 이 문제가 교내 팀에게 꽤 당혹스럽게 느껴질 것이라 예상하였으나, 전체 18팀 중 14팀이나 풀어버렸다. 특히, “🇰🇷815🇰🇷” 팀이 읽자마자 풀어서 제출한 장면이 매우 인상 깊다.

세상에는 다양한 정렬 알고리즘이 있으나, 어떤 알고리즘을 채택하여 어떻게 구현하느냐에 따라서 필요한 랜덤 셔플의 횟수가 다르다는 점이 이 문제의 매력같다. 정답률 또한 교내 37.5%, Open 58%로, 이 문제가 그렇게 쉽지만은 않다는 것을 잘 보여준다.

풀이

다양한 풀이가 있을 것이라고 생각한다. 운영진은 크게 두 가지 풀이(삽입 정렬과 퀵 정렬)를 가지고 있으며, 대부분의 참가자도 이 두 가지 중 하나로 풀었다. 여기서는 제일 설명이 깔끔한, 삽입 정렬 풀이를 소개한다.

다음 알고리즘은 대략 $O(N \lg N)$번의 랜덤 셔플로 순열을 정렬한다:

  1. 아직 정렬되지 않은 최초의 위치를 찾는다. 즉, $A_s \ne s$인 최소 $s$를 찾는다.
  2. 만약 그러한 $s$가 존재하지 않는다면, 순열 $A$는 정렬되었으므로 종료한다.
  3. 만일 그러한 $s$가 존재한다면, $A_e = s$인 $e$를 찾은 후, $[s, e]$를 랜덤 셔플한다.
  4. 다시 과정 1.로 돌아간다.

위 알고리즘을 간략하게 설명하자면, $s$가 제자리를 찾을 때까지, 구간 $[s, (s \text{가 존재하는 위치})]$를 랜덤 셔플하는 것을 반복하는 것이다.

이제, $s$가 제자리를 찾기 위하여, 평균적으로 몇 번의 랜덤 셔플이 필요한지 계산해보자. 특정한 수 하나를 $n$칸 왼쪽으로 옮기는 데 필요한 횟수의 기댓값을 $D_n$라고 정의하자. 정의에 의하여 다음 귀납식을 세울 수 있다:

\[D_n = 1 + \frac{0 + D_1 + D_2 + \cdots + D_n}{n+1}\]

세빈이의 풀이 슬라이드에 적힌 풀이법을 이용하면 다음을 알 수 있다:

\[D_n = 1 + \sum_{k = 1}^{n} \frac{1}{k} \approx 2 + \ln n\]

따라서, 총 랜덤 셔플 횟수의 기댓값은 $O(N \lg N)$다. 실제로 검수 과정에서 셔플 횟수가 $1200$번을 넘은 경우가 단 한 번도 발생하지 않았다.

비행기 타고 가요

개요

출제자 : 윤교준 / 데이터 제작자 : TAMREF
운영진 최단 코드 : 1143 bytes (C++)
교내 First Solver : 뚝심햄구이 (이종영, 안지민, 최은수) - 23분
Open First Solver : ainta - 78분

$N$개의 도시가 있다.
비용 $A_i$로 $[B_i, C_i]$의 도시에서 $[D_i, E_i]$의 도시로 이동할 수 있다.
$K$번 도시에서 출발하여, 각 도시로 이동하기 위하여 필요한 최소 비용을 구하시오.

Trivial한 자료구조 문제를 생각하다가, 적당한 양산형 문제를 하나 만들었고, 그것이 이 문제다.

교내 팀 중 “뚝심햄구이”가 23분만에 푼 것이 놀라운데, 대회가 끝나고 들어보니 팀원 중 한 명이 만든 문제와 유사했다고 한다. 기존에 공개된 문제와 대회 문제간의 유사도를 비교하는 작업을 열심히 했음에도 불구하고, 이를 걸러내지 못한 점이 아쉽다. 다만, 풀이를 정확하게 안다고 해도 23분이라는 짧은 시간 안에 정확하게 코딩했다는 점은 칭찬을 해주고 싶다.

풀이 1

문제 설명을 그래프로 환원하자. 즉, $[B_i, C_i]$의 정점에서 $[D_i, E_i]$의 정점을 향하는 가중치 $A_i$의 간선이 아주 많이 있는 그래프에서, 정점 $K$를 시작점으로 하여 Dijkstra 알고리즘을 시행하는 문제라고 생각할 수 있다.

여기서 우리는 가장 큰, 그러나 유일한 문제점에 부딪힌다: “그래프의 간선이 너무 많다.”

이 문제를 해결하기 위하여, Segment Tree의 아이디어를 적용하자. 두 구간 $[B_i, C_i]$과 $[D_i, E_i]$는 Segment Tree의 $O(\lg N)$개의 노드들로 표현할 수 있다. 다시 말하면, 아랫방향으로 가중치 $0$으로 연결된 Segment Tree와, 윗방향으로 가중치 $0$으로 연결된 Segment Tree를 이용하여, 간선 $[B_i, C_i] \times [D_i, E_i]$를 $O(\lg N)$개의 추가 간선만으로 모두 표현할 수 있다.

결과적으로 우리는 간선의 개수를 $O(N + M \lg N)$개로 줄였다. 시간복잡도는 $O(N \lg N + M \lg ^2 N)$ 혹은 $O(N \lg N + M \lg N)$다.

풀이 2

풀이 1에서 세빈이가 제안한 개선안이다. 위에서 Segment Tree를 이용하여 구간을 $O(\lg N)$개의 노드로 대체했던 것을, Sparse Table의 아이디어로 구간을 $2$개의 노드로 대체할 수 있다.

이 경우, 간선은 총 $O(N \lg N + M)$개로, 시간복잡도는 $O(N \lg ^2 N + M \lg N)$ 혹은 $O(N \lg N + M \lg N)$다.

풀이 3

이제 그래프를 명시적으로 그리지 않고, Dijkstra 알고리즘을 적용하는 방법을 생각해보자.

$[B_i, C_i]$의 정점 중 $K$번 정점과 가장 가까운 정점을 $V_i$라 하자. 간선 $[B_i, C_i] \times [D_i, E_i]$가 의미있는 경우는 오직 $V_i$에서 $[D_i, E_i]$로 거리 정보를 뿌려줄 때뿐이다.

이러한 아이디어를 활용하여 다음 알고리즘을 작성할 수 있다:

  • ”$[s, e]$의 정점의 최단 경로 길이는 $w$ 이하다”는 정보를 $(w, s, e)$라고 표현하자. 또한 아직까지 방문하지 않은 정점의 집합을 $V$라 하자.
  1. Priority Queue $\zeta$에 $(0, K, K)$을 넣는다. 또한 $V := \{ 1, 2, \cdots, N \}$라 하자.
  2. $\zeta = \emptyset$라면, 알고리즘을 종료한다.
  3. $\zeta$에서 $w$가 가장 작은 $(w, s, e)$를 pop한다.
  4. $V \cap [s, e] = \emptyset$일 때까지 다음을 반복한다:
    1. $[s, e]$ 중 아직 방문하지 않은 정점 $v$를 잡자. 즉, $v \in V \cap [s, e]$인 $v$를 아무거나 하나 잡자.
    2. $K$번 정점에서 $v$로 가는 최단 경로의 길이는 $w$라고 저장한다.
    3. $V := V \setminus \{ v \}$
    4. $v$를 포함하는 모든 구간 $[B_i, C_i]$에 대하여, $\zeta$에 $(w + A_i, D_i, E_i)$를 넣은 후, 구간을 삭제한다.
  5. 과정 2.로 돌아간다.

구간을 찾고, 지우는 과정은 Segment Tree를, 구간 내에서 아직 방문하지 않은 정점을 찾는 것은 Disjoint Set을 이용하여 구현할 수 있다. 시간복잡도는 $O(N \lg N + M \lg N)$다.