중앙대학교 2025-2학기 코딩경진대회 후기

 올해 코딩경진대회가 다시 열려서, 저도 처음으로 참가해보게 되었습니다. 대회는 9월 24일 오후 6시부터 9시까지 3시간 진행하였습니다. 온라인 대회라서 집에서 봐도 됐지만 수업이 5시에 끝나기도 하고 세팅하는 것도 시간이 좀 걸릴 것 같아서 학교에서 봤습니다. 다행히도 대회 참가자들을 위해서 학교에서 강의실 몇 곳을 개방해주었네요. 결과가 얼마전에 나왔는데...

 

 

다행히 1등을 했습니다.

 

 난이도는 조금 쉽게 나온 것 같습니다. 개인적인 의견으로 난이도는 solved.ac 기준으로 S2, B1, G1, P5 정도라고 생각이 드네요.

다 풀고 시간 봤을 때 52분이었던 걸로 기억합니다. 3번, 4번에서 실수 한 번씩 해서 조금 걱정했지만 다행히 점수 -> 시간 -> 제출횟수 순으로 순위를 결정하였습니다. ICPC룰처럼 (시간+틀린횟수)로 패널티 줬다면 어쩌면 제가 1등이 아니었을지도 모르겠네요.

문제별 풀이는 간략하게 하면 다음과 같습니다.

 

1번

태그: 오프라인 쿼리

먼저 쿼리들을 순서대로 모두 저장합니다. 1번 쿼리의 유무에 따라서 다음과 같이 풀 수 있습니다.

1. 1번 쿼리(블럭 전부를 한 가지 색으로 다시 칠하는 것)가 없다면 2번 쿼리(블럭 하나를 다시 칠하는 것)는 쿼리 당 O(1) 복잡도로 충분합니다.

2. 1번 쿼리가 등장한다면, 가장 마지막으로 사용한 1번 쿼리 이전의 쿼리들은 결과에 영향을 줄 수 없습니다. 따라서 가장 마지막으로 등장한 1번 쿼리를 O(N) 복잡도로 처리하고 나머지 쿼리는 O(1) 복잡도로 처리하면 됩니다.

혹은 다음과 같은 온라인 풀이도 가능합니다.

태그: 애드 혹

바탕색이 있고 그 위에 덧칠을 한 것처럼 생각을 해볼 수 있습니다. 그러면 1번 쿼리는 덧칠한 것을 전부 지우고 바탕색을 바꾸는 것으로, 2번 쿼리는 덧칠을 한 번 하는 것으로 생각하면 됩니다. 바탕색은 정수 변수 하나로, 덧칠한 건 c++의 vector와 같은 가변 배열로 관리하여 1번 쿼리에서는 가변 배열을 비우고 2번 쿼리에서는 가변 배열에 원소를 하나 추가하는 식입니다. 배열을 비우는 것은 최악의 경우 O(Q) 복잡도지만, 분할 상환 분석을 이용하여 가변 배열의 원소를 제거하는 비용이 그 원소를 추가할 때 이미 발생한 것으로 간주하면 각 쿼리의 복잡도를 amortized O(1)으로 생각할 수 있습니다.

 

2번

태그: 애드 혹

특별히 예외 처리가 없기 때문에 쉬웠던 문제입니다. 어떤 행에서 빈 공간을 무시하고 #O# 순으로 나오면 공이 상자 내부에 있는 것으로 판단할 수 있습니다.

 

3번

태그: 기하, 정렬, 조합론, 배낭 문제

가장 긴 변 하나의 길이가 다른 변들의 길이의 합보다 strict하게 작을 때 다각형을 구성할 수 있고, 그렇지 않으면 구성할 수 없다는 것은 잘 알려진 지식입니다. 즉 찾고자 하는 것은 '크기가 3 이상이고 가장 큰 원소 하나가 다른 원소들의 합보다 strict 하게 작은 부분 집합의 수'입니다. 먼저 모든 원소를 크기 오름차순으로 정렬한 다음에 knapsack table을 관리하면 됩니다. table은 (원소의 수, 원소의 합)을 parameter로 주고 경우의 수를 값으로 저장해줍니다. 그렇게 해서 i번째 원소를 볼 때 테이블에서 [원소의 수>=3][원소의 합>i번째 원소]인 범위를 모두 합해서 답에 더해주면 됩니다. 원소의 수는 3까지만 원소의 합은 개별 원소의 최댓값+1까지만 봐도 충분하므로 테이블 크기를 조절해주면 O(N*max L) 복잡도로 시간 내에 도는 것을 알 수 있습니다.

 

4번

태그: 데이크스트라, 오프라인 쿼리, 이분탐색, 그래프 이론

dijkstra 알고리즘을 간선의 정방향으로 한 번, 역방향으로 한 번하여 총 두 번 돌려줍니다. S에서 출발하여 어떤 간선 (u, v)를 거쳐서 E로 가는 가장 짧은 경로는 (S에서 u까지 최단 경로)+(u -> v)+(v에서 E까지 최단 경로)입니다. (v에서 E까지 최단 경로의 길이는 역방향 그래프를 통하여 구하면 됩니다.) 그러면 이제 (u, v)를 제거해야하는 가장 작은 x를 알아냈습니다. 이 값들을 정렬한 다음에 이분탐색을 사용하거나 오프라인 쿼리를 사용하면 각 쿼리에 대해 빠르게 답할 수 있습니다.