2021 나코더 송년대회 후기

2021 나는 코더다 송년대회 스코어보드

결과 : 2위 (7솔,시간페널티 922분)

 

나코더 송년대회는 경기과학고등학교의 PS 동아리 '나는코더다'에서 주최하는 연례 행사이다. 카카오, 넥슨 등의 후원을 받아 진행되어 상품도 푸짐하여 경기과학고등학교의 많은 학생들이 참가하며, 이후에 열린 오픈 콘테스트에도 재학생이 아닌 분들이 많은 관심을 가지고 참여해주신 것으로 알고 있다. 이 대회를 준비해주신 출제진, 검수진, 그리고 후원자분들께 감사드린다.

 

필자가 속한 팀은 "본선도 좋은 결과가 있으면 좋을 것 같습니다"라는 팀으로, 팀명은 우리 팀원 중 한 명이 NYPC2020 현장스케치에서 인터뷰했던 대사를 그대로 활용하였다. (궁금하면 유튜브에 영상을 찾아보길 바란다.) 팀은 다양한 대회에서 준수한 성적을 거두며 유력한 국가대표 후보로 지목받고 있는 CF 레드 코더 한 명, 전반적으로 두뇌 회전이 빠르며 수학적 사고력이나 복잡한 구현을 요하는 문제에 특히 능한 CF 오렌지 코더 한 명, 그리고 필자로 구성되었으며, 계절학교 계속반 중 경기과학고 2학년 3명으로 이루어진 팀이었다. 이 자리를 빌어 부족한 실력의 필자를 팀에 넣어준 나머지 두 친구에게 고맙다는 말을 전하고 싶다.

 

그 외 1위를 차지한 팀은 1학년 팀으로, 아직 1학년임에도 불구하고 세 학생 모두 NYPC 1519부문 본선에서 3위 이내의 성적을 기록한 적이 있으며, CF 기준 레드와 오렌지를 오가는 실력이다. 해당 대회에서도 이 중 한 학생이 다이아3 난이도의 DP문제인 F번을 풀어내며 1위를 차지하였다. 3위 팀은 3학년 팀으로, 해당 대회의 1위, 2위, 3위를 각 학년이 하나씩 나눠가지는 아름다운 그림이 나왔다.

 

대회는 중반까지 '부릉부릉 이환버스' 팀과 '본선도 좋은 결과가 있으면 좋을 것 같습니다' 팀이 엎치락뒤치락하는 양상이었으며, 3위 아래의 팀들과도 크게 차이가 나지 않았다. 그러다가 '부릉부릉 이환버스' 팀이 7솔을 하며 2솔차 1위로 올라섰고, 2위 팀부터 4위 팀까지 모두 5솔로 프리즈를 맞이했다. 프리즈 이후에도 꽤 많은 문제가 풀렸고, 1위, 2위, 3위, 4위의 차이가 각각 1솔씩 벌어진 상태로 대회가 마무리되었다.

 

우리 팀은 CF 레드 코더가 ABCD번, 필자가 EFGH번, CF 오렌지 코더가 IJKL번을 관찰하기로 하였다. 초반에 ACD와 IK를 빠르게 풀며 가장 먼저 5솔에 도달했고, 이 중 K번은 퍼솔 타이틀도 얻었다. 쉬운 문제를 가장 잘하는 팀원이 풀어 사소한 시간 페널티를 줄였고, 구현과 수학을 잘하는 팀원이 구현 문제인 I번과 정수론 문제인 K번을 맡아 빠르게 풀었다. 사다리 타기를 통해 맡을 문제를 결정했었는데, 결과적으로 봤을 때 각 팀원의 실력 및 장단점에 맞게 잘 배정된 것 같다.

사실 G에 대한 관찰도 초반부터 활발한 소통을 통해 잘 이루어졌지만, 한참 빙빙 돌아가는 회전목마처럼 풀이를 생각한 데다가 그 풀이에 약간의 허점이 있어 3시간 이상을 고생했다.

그리고 B번에 대한 이야기를 안 할 수가 없는데, B번은 모두가 아는 삼분탐색과 다익스트라 알고리즘을 알고 있었다면 해결할 수 있는 문제였다. 티어도 P4로 높지 않고 구현이 복잡하지도 않은데 프리즈 전까지 그 어떤 팀도 이 문제를 풀지 못했다. 처음 1시간 동안 제출한 팀이 없는 것을 보고 다들 어려운 문제라고 생각하고 건드리지 않은 것 같다. 우리 팀에서도 ACD를 빠르게 풀어낸 친구가 B를 읽고 루비인 것 같다며 G를 풀기 시작했다(?). 결국 이 문제는 프리즈 후에 문제를 처음 읽은 필자가 풀었는데, 구현을 하면서도 어려운 문제일 것이라는 선입견 때문에 풀이에 대한 확신이 없었다. 최종적으로도 이 문제는 1, 2, 3위 팀만 풀게 되었다.

내가 맡았던 EFGH의 난이도가 순서대로 R4/D3/P3/D1이었고, 그 와중에 G번 문제에서 팀이 단체 뇌절을 하며 필자는 프리즈 전까지 한 번의 제출도 하지 못했다. 이 점이 조금 답답하긴 했지만 팀 연합으로 하는 대회가 처음이어서 상당히 재미있었다. 우리 팀은 플래티넘 이하의 난이도는 전부 풀었으며, 다이아 이상의 난이도는 못 푼 셈이 되었다. ABCD를 맡았던 팀원이 ACDG를 풀고, EFGH를 맡았던 필자가 B를 풀며 모든 팀원이 '자신이 맡은 문제 중 Platinum 난이도 이하의 문제'만큼 풀게 되었고, 실수가 있었던 것에 비하면 매우 만족스러운 결과였다.

 

해당 대회의 출제진 세 분은 모두 계절학교 코치로 영입되었고, 국대급 실력을 가지고 계신 분들이라는 것을 알기에 그 분들께서 정성들여 출제한 문제들을 풀어볼 수 있는 것도 좋은 경험이었다. 문제들에 대한 간단한 설명, 풀이(아는 것만)는 아래에 적어두었다.

 

문제

 

A - 아기 홍윤(G5)

길이 N의 수열의 특정 구간을 bitwise or 하였을 때 정확히 K가 되는 구간을 찾는 문제이다.

제한 : N<=20만 / 시간 1초

https://www.acmicpc.net/problem/24023

 

풀이)

K에서 1이 아닌 비트가 어떤 수 A[i]에서 1이라면 그 숫자는 아예 사용할 수 없으므로 '사용 불가'를 표시해둔다. '사용 가능'한 수들은 '사용 불가'가 된 수들에 의해 구간으로 나누어지며, 해당 구간들을 각각 bitwise or 하였을 때 K가 되는지 확인해주기만 하면 된다. O(N)에 해결할 수 있다.

 

B - 삼색 그래프(P4)

정점 N개, 간선 M개로 이루어진 무방향 연결그래프의 간선에는 빨간 간선, 파란 간선, 검정 간선이 있다.

분말스프를 빨간 간선에 뿌리면 모든 빨간 간선의 가중치 +1

분말스프를 파란 간선에 뿌리면 모든 파란 간선의 가중치 +1

분말스프를 X스푼 이하로 뿌려서 1번 정점에서 N번 정점으로 가는 최단경로를 가장 길게 만들고 싶다.

이 때 최단경로의 최댓값을 찾는 문제이다.

제한 : N,M<=20만, X<=1e9 / 시간 7초

https://www.acmicpc.net/problem/24024

 

풀이)

분말스프를 아끼는 것은 의미가 없으니, X스푼을 모두 쓰면 된다.

X스푼 중 빨간 간선에 t스푼, 파란 간선에 X-t스푼을 뿌리는 경우 다익스트라를 통해 최단경로의 값을 구할 수 있다.

이 때 각 최단경로의 값은 t에 대한 일차함수이기 때문에 t에 대한 그래프의 개형이 Convex하게 나오고, 따라서 최댓값을 삼분탐색을 통해 찾아 줄 수 있다. 시간복잡도는 O(MlogNlogX)이 된다.

 

C - 돌의 정령 줄세우기(G4)

1부터 N까지 서로 다른 키를 가진 N개의 돌의 정령이 있다.

돌의 정령은 자신보다 키가 큰 돌의 정령 너머로 볼 수 없다.

i번째 돌의 정령이 오른쪽으로 j번째 돌의 정령까지 볼 수 있다면 i번째 돌의 정령의 시야 점수는 j-i점이다.

만약 오른쪽에 자신보다 큰 돌의 정령이 없다면 시야 점수는 1e9점이다.

길이 N의 수열 A가 주어지는데, 각 A[i]는 다음을 의미한다.

A[i]<0 : i번째 돌의 정령의 시야점수는 |A[i]| 이하여야 한다.

A[i]>0 : i번째 돌의 정령의 시야점수는 A[i] 이상이어야 한다.

이 조건을 만족하도록 돌의 정령의 순서를 결정하는 문제이다.

제한 : N<=7만, |A[i]|=1,2,...,N 중 하나 / 시간 2.5초

https://www.acmicpc.net/problem/24025

 

풀이)

N부터 1까지 수를 쭉 쓴다.

구간 [s,e]가 -1로 이루어진 구간이라면 [s,e+1] 구간을 뒤집는다.

이렇게 되면 A[i]가 양수인 돌의 정령들의 시야 점수는 모두 1e9점이 되고,

A[i]가 음수인 돌의 정령들의 시야 점수는 모두 1점이 되어 주어진 조건을 만족한다.

시간복잡도는 O(N)에 짤 수 있을 것 같다.

 

D - 기차 여행(P2)

송죽국은 N개의 도시가 일렬로 늘어서 있는 모양이고, 순서대로 1번, 2번, ... , N번 도시이다.

i번 도시에서는 순환선에 탑승하여 L[i]번 도시와 R[i]번 도시 사이에 내릴 수 있다.

단, 지나가는 열차에 도중에 탑승하는 것은 불가능하다.

재민이는 Q개의 여행 계획을 세웠으며, i번째 계획은 U[i]번 도시에서 시작해서 V[i]번 도시로 여행하는 것이다. 이 때, 각 쿼리마다 갈아타는 횟수를 최소화하려고 한다.

제한 : N<=20만, Q<=10만, 1<=L[i]<=i<=R[i]<=N, 1<=U[i],V[i]<=N / 시간 4초

https://www.acmicpc.net/problem/24026

 

풀이)

추후 다른 글에 작성하여 링크를 걸어두겠습니다.

 

E - 두 트리(R4)

N개의 정점으로 이루어진 빨간색 트리와 파란색 트리가 있다.

빨간색 트리와 파란색 트리의 정점을 일대일 대응시켜 새로운 그래프를 만든다.

이 때 합쳐진 그래프에는 중복 간선이 없어야 한다.

이러한 일대일 대응을 구하는 문제이다.

제한 : N<=20만 / 시간 2초

https://www.acmicpc.net/problem/24027

 

풀이)

언젠가 풀이를 이해하는 날이 오면 다른 글에 작성하겠습니다.

 

F - 사진 촬영(D3)

N명의 친구들이 사진을 여러 장 찍으며, 모든 친구들이 적어도 한 장의 사진에 최소 한 번씩 등장한다.

N명의 친구들은 현재 일렬로 서서 사진을 찍기를 기다리는 중이다.

사진을 촬영하는 데에 드는 비용은 방법에 따라 다르다.

1. i번 사람의 독사진을 촬영하는 데에 드는 비용 A[i]원

2. 인접한 두 사람의 위치를 바꾸는 데에 드는 비용 C원

3. 연속한 K명 이상의 단체사진을 찍는 데에 드는 비용 B*(구간 길이)원

이 때 최소 비용을 구하는 문제이다.

제한 : N<=5000, A[i],B,C<=1e9, 1<=K<=N / 시간 2초

https://www.acmicpc.net/problem/24028

 

풀이)

언젠가 풀이를 이해하는 날이 오면 다른 글에 작성하겠습니다.

 

G - 정기 모임 3(P3)

정점이 N개인 트리, i번째 간선은 A[i]번 정점과 B[i]번 정점을 연결

정점-정점 거리 : 트리에서의 유일한 단순 경로에 포함되는 간선의 수

한 정점에 최대 한 명까지 참석 가능

정부가 X단계 방역 지침을 시행 -> 트리 위에 서 있는 임의의 두 사람 사이의 거리 정확히 X

X=1, 2, ..., N일 때 모일 수 있는 최대 인원을 구하는 문제이다.

제한 : N<=20만, A[i],B[i]<=N / 시간 1초

https://www.acmicpc.net/problem/24029

 

풀이)

추후 다른 글에 작성하여 링크를 걸어두겠습니다.

 

H - 향수(D1)

수직선 도로에 N명의 사람이 있다.

이 중 i번째 사람은 l[i]에서 r[i]까지 양의 방향으로 걷는다.

수직선 곳곳에는 K개의 향수를 설치할 수 있다.

닫힌 구간 [ l[i], r[i] ]에 향수가 있으면 i번째 사람은 향기를 맡고 w[i]만큼의 행복도를 얻는다.

단, 한 사람이 향기를 두 번 맡는다고 더 많은 행복도를 얻지는 않는다.

행복도가 최대가 되도록 하는 향수의 위치를 알아내는 문제이다.

제한 : K<=N<=20만, |l[i]|, |r[i]|<=1e9, 1<=w[i]<=1e4 / 시간 8초

https://www.acmicpc.net/problem/24030

 

풀이)

언젠가 풀이를 이해하는 날이 오면 다른 글에 작성하겠습니다.

 

I - 카카오 택시(P2)

둥둥섬은 N개의 교차로가 수직/수평 방향 도로로 연결되어있다. 교차로의 x, y좌표는 전부 짝수이다.

두 교차로의 x좌표가 같고 y좌표가 2 차이난다면 두 사거리 사이에 세로 방향 도로 존재

두 교차로의 y좌표가 같고 x좌표가 2 차이난다면 두 사거리 사이에 가로 방향 도로 존재

신호등은 K초 주기로 일정한 패턴 반복, 상태는 1/2/3/4로 주어진다.

1 : 세로만 통행 / 2 : 가로만 통행 / 3 : 좌회전 / 4 : 우회전

택시는 어떤 도로의 중점에서 출발, 1초에 2m씩 이동, 신호 대기 이외의 이유로 멈추지 않는다.

아무리 기다려도 갈 수 없는 경우 즉시 유턴하여 돌아나온다.

택시에 탑승했을 때 택시의 좌표와 방향을 알고 있다고 한다면, T초 후 택시의 위치를 구하여라.

제한 : N<=10만, K<=10, x,y<=20만, T<=10^18 / 시간 2초

https://www.acmicpc.net/problem/24031

 

풀이)

모든 상태는 NK가지 뿐이다. 뇌를 비우고 전탐색을 해주면 된다.

코드는 가장 짧게 짜면 2300B 정도, 길게 짜면 4000B 정도까지 나온다고 한다.

그래서 아이디어가 없음에도 불구하고 P2라는 높은 티어를 받은 것 같다.

 

J - 깔때기와 비커(D3)

N층의 깔때기가 있고, 가장 위의 깔때기가 1번, 가장 아래의 깔때기가 N번이다.

i층의 깔때기는 구간 [ L[i], R[i] )의 액체를 구간 [ M[i], M[i+1] )으로 모은다.

Q번의 장난을 치는데, i번째 장난은 다음과 같다.

S[i]번째 깔때기가 있는 층 위로 균일하게 전체 범위에 단위 길이당 1의 물을 뿌리고, E[i]번째 층 아래 구간 [ X[i], Y[i] )에 비커를 설치하여 얼마의 물이 모이는지 측정한다.

각 장난에서 모이는 물의 양을 구하는 문제이다.

제한 : N,Q<=50만, L,R,S,E,X,Y<=1e9 / 시간 4초

https://www.acmicpc.net/problem/24032

 

풀이)

언젠가 풀이를 이해하는 날이 오면 다른 글에 작성하겠습니다.

 

K - 맥스웰의 악마(P4)

길이 L과 R의 두 관이 칸막이 하나를 사이에 두고 붙어있다.

안에는 N개의 입자가 움직이고 있으며, i번 입자는 x[i], d[i], w[i]로 표현된다.

x[i]는 입자의 초기 위치를 나타내며, d[i]는 초기 운동 방향, w[i]는 입자의 질량을 의미한다.

입자는 닫힌 칸막이나 관의 끝에 부딪히면 운동 방향이 반대가 되고, 속력은 유지된다. 입자끼리의 충돌은 무시한다.

적절한 시점에 칸막이를 열고 닫아 충분히 긴 시간이 흐른 후 오른쪽 관에 있는 입자들의 질량 합을 최대화할 때, 이 최댓값을 구하는 문제이다.

제한 : N<=20만, L,R,w<=1e9 / 시간 1초

https://www.acmicpc.net/problem/24033

 

풀이)

칸막이를 열 때 동시에 오는 두 입자의 위치를 서로 바꾼다고 생각하면, 간단한 관찰을 통해 x[i]를 gcd(2L,2R)로 나눈 나머지가 같은 두 입자들 사이를 항상 바꿀 수 있다는 사실을 알 수 있다. 따라서 교환할 수 있는 입자 중 값이 큰 것부터 오른쪽에 넣을 수 있는 만큼 넣어주면 된다.

단, 처음 위치와 방향이 같은 입자는 하나의 입자로 합쳐서 생각해야한다. 우리 팀은 이 사실을 간과하여 1번 틀렸다.

 

L - 선형대수학(D4)

P1x1+P2x2+...+Pkxk=A

Q1y1+Q2y2+...+Qkyk=B

(단, 0<=x1,x2,...,xk<=1)일때, 해가 존재하는가?라는 문제를 만든다.

k개의 순서쌍 (Pi,Qi) 중 몇 개만 사용하여 문제를 만드는데, 새로운 순서쌍을 추가하거나 있던 순서쌍을 제거하는 방식으로 만든다. 이는 Q개의 쿼리로 표현된다.

1 a b : A=a, B=b로 설정한 뒤 문제를 출제한다. 이 때 문제의 답을 출력한다. (YES/NO)

2 c : 현재 문제에 c번 순서쌍이 있으면 제거하고 없으면 추가한다.

제한 : N,Q<=30만, Pi,Qi<=1e9, a,b<=1e15 / 시간 2초

https://www.acmicpc.net/problem/24034

 

풀이)

언젠가 풀이를 이해하는 날이 오면 다른 글에 작성하겠습니다.