본문 바로가기

기타/후기

2022 서강대학교 청정수컵💧 출제 후기 (짧)

반응형

 

어제 본 대회, 오늘 Open Contest가 종료되면서 대회가 완전히 끝났다. 

 

 

지금까지 문제 출제를 제외하곤 PS와 관련된 할 수 있는 것은 다 해본 것 같은데, 운 좋게 출제의 기회까지 얻어서 마지막 퍼즐까지 맞춰졌다.

 

평소에 새로운 문제를 생각하거나 문제를 풀면서 새로운 아이디어를 떠올리는 스타일이 아니라 출제는 못할 것 같다고 생각해왔는데, 마침 쉬운 난이도의 대회를 학회 내에서 개최한다는 소식을 듣고 머뭇거리다가 한번 지원을 해봤다. 

 

난이도도 어렵지 않고, 문제도 크게 새롭진 않은 문제라 생각보다 아이디어는 금방 떠올랐다. 

 

대회 운영에 참여하기보단 사실상 출제만 해서, 출제 계기나 내가 출제한 문제에 대해서만 짧게 적어보고자 한다. 

처음 polygon도 써보고 문제나 대회가 만들어지는 과정도 알게 되어 여러모로 재밌는 경험이었다. 

검수를 해본 경험이 있지만, 생각보다 신경 써야 할 디테일이 이렇게 많을 줄은 몰랐다. 예전의 검수를 정말 대충 한 거구나 생각이 들 정도였다. 

 

더불어 오프라인으로 진행된 대회를 운영진분들이 열심히, 잘 준비해주신 것 같아서 감사함을 전하고 싶다. 


문제는 브론즈 1문제와 골드 1문제, 총 2문제를 출제했고 모두 채택되었다. 

 

고인물이 싫어요 (청정수 Round E번 - Gold)

 

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

 

25187번: 고인물이 싫어요

첫째 줄에 물탱크의 수 $N(1 \leq N \leq 100\,000)$과 파이프의 수 $M(0 \leq M \leq 200\,000)$, 그리고 물탱크에 방문할 횟수 $Q(1 \leq Q \leq 100\,000)$가 주어진다.  둘째 줄에 $1$번부터 $N$번 물탱크까지 순서대

www.acmicpc.net

 

출제를 해봐야겠다고 생각하고 당일날 제작한 문제이다. 

먼저, div2의 출제범위는 특별한 알고리즘이 필요하지 않은 문제들이었고, div1은 기본적인 실버~골드 이하의 알고리즘들이었기 때문에 그중 Union-Find를 이용해서 문제를 만들어볼 만하지 않을까 생각했다. 

그리고, 대회 컨셉이 높은 실력을 가지지 않은 '청정수'들을 위한 대회이기 때문에 그 반대인 '고인물'을 배척(?)하자는 의미에서 "고인물이 싫어요"라는 제목을 만들고 노드를 물탱크로 구성했다. 

 

이렇게 원래는 Union-Find 문제를 생각했지만, 대부분의 검수진들이 단순히 BFS/DFS로 전처리하는 풀이도 제공을 했고, 그 풀이가 초심자 입장에선 더 쉬울 수 있기에 메인 솔루션을 그래프 탐색으로 변경했다. 그에 따라 난이도도 1 티어 정도 낮아졌다. 

 

그리고 청정수와 고인물의 풀이의 차이가 확연히 드러났던 게, 본 대회 때에는 대부분의 참가자들이 그래프 탐색으로 해결하려는 모습을 보였지만, Open Contest에서는 Union-Find 풀이가 대부분이었다. 

또, 본 대회 때 E를 푼 참가자들이 처음엔 각 쿼리 별로 BFS를 수행하여 시간 초과를 받았다가, 코드를 수정하며 AC를 받는 모습을 보니 나름 문제 의도가 잘 반영된 것 같다. 

 

 

인생은 한 방 (청정수 Round A번 - Bronze)

 

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

 

25183번: 인생은 한 방

문자열 $S$의 부분 문자열이란, 문자열의 연속된 일부를 의미한다. 

www.acmicpc.net

 

브론즈급 문제의 지원이 적다는 소식을 듣고 브론즈 문제는 뭐가 있을까 생각해보니, 오히려 쉬운 문제가 떠올리기 매우 힘들었다. 브론즈 문제들은 웬만하면 이미 다 있는 문제이고, 또 조금만 응용해도 난이도가 올라가버리니 만들기가 쉽지 않았다. 

그러던 중 신촌역 주변 신호등을 건너다, 로또 판매점에 길게 줄을 서있는 모습을 보고 "저 가게는 돈을 얼마나 벌까..." 생각하다가 갑자기 떠오른 문제가 바로 이 문제이다. 

 

쉬운 문제였음에도 불구하고 데이터를 충분히 만들지 못해서 검수 과정에서 반례들이 많이 나왔고 다행히 본 대회 때는 별 문제가 없었다. 

 

 

문제 제작에 도움을 주신 많은 분들에게 감사드립니다 :)

 

 

반응형