저번 달 말에 2022 인하대학교 프로그래밍 경진대회에서 출제와 운영을 했다. 현장 대회로 진행되었고, 약 3년 만의 현장 대회였기 때문에 기존 현장 대회를 진행했던 운영진들은 다 졸업하고 인수인계 하나 없이 시작했기 때문에 준비할 것도 많았고 우여곡절도 많았다. 무사히 끝난 데 감사함을 느낀다.
대회 준비 초기에 팀 대회로만 진행되던 대회를 개인 대회로 진행하는 쪽으로 방향을 틀었다. 그 이유는, 코로나 때문에 20 이하 학번들이 팀 빌딩을 하기가 상당히 어려운 상황이었기 때문이다. 또한, 학교 측에서 1학기에 대면 수업을 진행함에 따라 2년간 비대면으로 열렸던 대회가 대면으로 열릴 수 있는 가능성이 생겼다. 3월쯤에 확진자가 하루에 몇십만 명씩 나왔을 때는 긴가민가했는데 결국 대면으로 개최될 수 있었다.
기존 IUPC는 ICPC를 표방한 대회로 팀 단위로 문제를 풀 때마다 헬륨 풍선을 하나씩 달아주는 전통이 있었다. 하지만, 개인 대회에서 문제를 맞출 때마다 헬륨 풍선을 달아주기엔 비용적인 문제도 있었고(헬륨 풍선은 생각보다 많이 비쌌다) 적은 인력으로 커버하기도 쉽지 않았다. 내가 맞춘 문제별로 풍선 모양 스티커를 주는게 어떻냐고 의견을 냈고, yooshnn이 스티커를 디자인해줘서 스티커를 주문해서 받았고, 대회 끝나고 참가자들에게 나눠주었다.
그밖에도 수십 개의 멀티탭을 구매해서 참가자들이 사용할 수 있게 배치하고, 수상자 패널을 직접 접착보드에 붙여서 만드는 등등 온갖 잡일을 진행했다. 5시간 동안 문제를 풀며 고생할 참가자들을 위한 간식도 준비했다. 본 대회 및 Open Contest 참가자를 위해서 solved.ac 뱃지 및 배경을 지급하고 싶었고, 별 문제 없이 지급될 수 있었다. (항상 빠른 답장해주신 shiftpsh님 감사합니다)
나름 대학 생활하면서 겪은 일 중 가장 큰 일이기 때문에 재미도 있었고 얻은 것도 많은 것 같다. 특히 운영진들과 합심해서 대회 전날 이것저것 준비했던 일들은 잊지 못할 추억이 된 것 같다.
개인전으로 대회를 열기로 했기 때문에, 문제 수를 기존 12문제에서 10문제로 축소시켰다. 대신, 백준에서 열리는 Open Contest는 기존 문제를 강화한 Hard 문제 2문제를 추가하여 12문제로 진행했다. 나는 공식 대회 4문제 + Hard버전 1문제를 출제하게 되었다. 아래에는 출제된 문제들에 대해서 간단한 코멘트를 달겠다.
* 문제 정렬은 가나다순입니다 *
문자열에 대한 이해가 있으면 풀 수 있는 간단한 문제다. 다만, 구현 방향에 따라 구현량이 조금 많을 순 있다.
간단한 반복문과 조건문을 사용할 수 있다면 풀 수 있는 문제이다.
좌우 대칭이라는 키워드에서 Manacher를 직관적으로 떠올릴 수 있다. 트리에서 대칭 판별을 하기 위해서는 먼저 트리를 배열로 바꿔야 하는데, 이것을 ETT로 해결할 수 있다. 이때, 단순히 노드의 정수를 가지고 Manacher를 돌리면 반례가 생긴다. 노드의 정수와 깊이를 pair로 묶어 대칭 판별을 해야 제대로 된 답을 얻을 수 있다. 당연히 Manacher 대신 Hashing을 사용해서 문제를 풀어도 된다.
본 대회에서 수상 커트라인을 가른 문제이다. 기본적으로 BFS를 사용하여 문제를 해결하는데, 주사위 굴리기를 구현해야 해서 번거로운 구현이 조금 들어간다. 나는 F와 난이도가 비슷하다고 생각했는데, 실제 대회에선 E보다는 많은 사람들이 풀어주었다.
내가 만든 문제이다. 참가자들이 풀 만한 문제들을 모두 풀고 나서 더 이상 풀 문제가 없다고 판단했을 경우 건드릴 수 있는 문제로 사용되었다. 문제가 요구하는 사항은 상당히 명확하고 구현 방향도 어렵지 않게 캐치할 수 있다. 구현량은 적다고 하긴 힘들지만 크게 많지도 않아서 생각보다 많이 풀릴 수 있을 것이라고 생각했었는데 아니었다. Open Contest에서도 단 5명만이 해결했고, Platinum V 티어를 받았다.
내가 만든 문제이며, 본 대회에서 대상 및 금상 수상자를 가른 문제이다. naive한 풀이로 시작해서 관찰을 하며 시간 복잡도를 점점 줄여가는 방식으로 해결할 수 있다. 풀이 방법은 크게 두 가지인데, 첫 번째는 적당한 y = x + k 직선을 그어 제 1, 3사분면의 직사각형과 겹치는 격자점의 개수를 세서 해결하는 방식이고, 두 번째는 나올 수 있는 정사각형의 최소 크기, 최대 크기를 미리 구해놓고 모든 크기에 대해 수학적으로 개수를 세는 것이다. 두 풀이 모두 O(N)의 시간 복잡도를 가진다.
이 문제는 사실 O(1)으로도 풀 수 있다. 처음에는 몰랐는데 ANZ님이 풀이를 발견해서 Hard를 Open Contest에 넣기로 하였다. 위의 첫 번째 풀이로 직사각형과 겹치는 격자점의 개수를 셀 때, 격자점의 개수가 일차식 형태로 표현될 수 있음을 관찰할 수 있다. 일차식이 제 1, 3사분면의 직사각형에 대해서 2개씩 나오므로 두 식을 곱해서 이차식으로 바꿔 시그마 합 공식으로 문제를 해결할 수 있다. 나는 직사각형의 꼭짓점 8개를 정렬하고 스위핑을 통해 이를 구현했다. 이 방법 말고도 꽤 어려운 포함 배제의 원리를 사용한 풀이도 존재한다.
케이크가 최대 10조각이므로 1024가지의 모든 조합을 시도해보면 문제를 해결할 수 있다. 실수 자료형을 사용할 경우 float을 쓰면 정확도 문제로 오답이 나올 가능성이 있으므로 double을 써야 한다. 실수 자료형을 사용하지 않는 풀이도 있는데, 분수를 직접 구현하거나 lcm(1, 2, 3, ..., 25)를 이용하는 방법이 있다.
케이크 조각이 많아졌기 때문에, 위의 방법으로는 풀 수 없고 새로운 방식으로 접근해야 한다. 크게 두 가지 풀이가 있던 것 같은데, 나는 Meet in the Middle 방식으로 1/1 ~ 1/18까지의 케이크 조합으로 만들 수 있는 모든 크기를 구하고, 1/19 ~ 1/25까지의 케이크 조합으로 만들 수 있는 모든 크기를 구한 후 두 결과를 이분 탐색으로 합쳐주는 풀이를 만들었다. 보통 Meet in the Middle은 가운데에서 쪼개기 때문에 이러한 문제를 풀어보지 않은 사람들에게는 상당히 어렵게 다가올 수 있다고 생각한다. 이 문제는 무려 Diamond V 티어를 받았다.
내가 만든 문제이다. 배열에 수를 추가할 때마다 그 수를 사용할 것인지 사용하지 않을 것인지에 따라 두 가지 경우의 수가 나온다. 기존에 구한 답과 현재까지의 최솟값을 변수에 저장해놓으면 O(N) 풀이를 완성할 수 있다.
여담으로, 문제에서 설명한 내용을 Segment Tree, Sparse Table 등으로 구현할 수 있는 RMQ를 사용하여 그대로 구현하면 O(NlogN)이기 때문에 문제를 해결할 수 있다.
내가 만든 문제이다. 원래는 조금 전형적인 dp문제를 의도하고 만들었는데, 간단한 그리디로도 해결할 수 있는 것을 알고 더 좋았다. 문제를 dp로 해결하려면 dp[i][j]를 i번째 글자까지 봤을 때 마름모 활성화 상태가 j인 최소 입력 횟수로 잡고 점화식을 세우면 된다. 그리디는 조금 더 간단한데, 바꿔야 하는 글자가 연속 1개면 별 버튼을 사용하는 것이 무조건 이득이고, 연속 2개 이상이면 마름모 버튼을 사용하는 것이 무조건 이득이다.
마지막 문제이기도 하고 디스크립션이 조금 길어서 아쉽게도 많은 사람들이 시도하지 않은 문제이다. 본 대회에서는 1명이 풀었으며, 무려 36번만에 문제를 맞췄다. 풀이 방법은 크게 두 가지인데, 나는 방어력을 매우 큰 값으로 설정해 최대 획득 가능 금화를 dp로 미리 구해놓고, 방어력을 기준으로 Parametric Search를 하며 동일한 dp를 진행하는 방식으로 풀었다.
'History' 카테고리의 다른 글
| 쿠팡 신입 개발자 취업 후기 (4) | 2023.09.21 |
|---|---|
| 2021 ICPC Asia Seoul Regional 참가 후기 (0) | 2022.03.24 |
| 2021 IUPC(인하대학교 프로그래밍 경진대회) 후기 (0) | 2021.11.17 |
| UCPC 2021 예선 참가 후기 (0) | 2021.08.01 |
| 2021 IGRUS Newbie Programming Contest 개최 후기 (0) | 2021.04.05 |
