본인 대학 대회인 2022 SKKU 프로그래밍 대회 in 소프트의 밤에 문제를 출제했다. Problem solving을 하면서 한 번쯤은 문제를 출제해보고 싶다는 생각을 했었는데, 이번에 기회가 생겨서 하게 되었다. 본인은 C번(수렵의 시간이다!)과 I번(전투 시뮬레이션)을 출제했다.
C. 수렵의 시간이다!
문제를 보고 아는 사람도 있을 텐데, 문제에 나온 M게임은 몬스터 헌터를 말한다. 쉬운 브론즈~실버급 문제들을 만들어야 했는데, 당시 몬스터 헌터 라이즈: 선브레이크를 즐겁게 한 경험이 있어서 해당 게임의 스킬과 괴의 연성 시스템을 가져와서 만들었다.
처음에는 원본 게임처럼 방어구 종류도 5가지고, 스킬 종류도 $N$으로 유동적으로 바뀌었다. 그리고 그냥 brute-force로 만들기엔 특색이 없어서, 스킬 종류를 $1\,000$까지 늘려 현재 상태에서 강화를 할 때 최대 이득을 set 을 이용해 $O(logN)$만에 구하도록 정했다. 하지만 이렇게 하니까 입력 형식이 난해하고 너무 어렵다는 의견이 나와서 방어구 종류를 3가지로 줄이고, 스킬 종류도 5개로 고정해서 그냥 brute-force 문제로 바꿨다.
문제 내용이 길고 구현이 조금 힘들지만, 그냥 brute-force로 모든 경우를 보면 되기 때문에 운영진 예상 난이도 실버2~1로 나왔고, C에 배치했다. 하지만 실제 대회에서는 E번보다 적게 풀린(C:9명 / E: 17명) 결과가 나왔다… 지문이 길고 구현할 것이 많다 보니 상대적으로 지문이 짧은 D/E번을 먼저 푼 것 같다. 그리고 강화 부분 때문에 구현이 많이 복잡해 지는데, 강화를 빼거나 최소한 예제 1번에 대한 그림이라도 넣었어야 하는 생각이 든다. 다음에는 최대한 이해되기 쉬운 문제를 만들어야겠다.
I. 전투 시뮬레이션
이 문제는 처음에는 Mo’s를 풀이로 만들던 문제였다. Meta Hacker Cup 2022 Round 2의 A2를 잘못된 풀이로 접근한 것에서 아이디어가 시작되었다. 그때 Mo’s 영역을 2개로 나누어서 관리하는 풀이를 생각했는데, 이 아이디어가 괜찮은 것 같아서 영역을 3개로 나누는 것으로 확장했다. Mo’s는 영역을 확장/축소시키는 연산이 빨라야 의미가 있다. 그래서 처음에는 영역을 연속된 A, B, C 3개로 나누고, A-B, A-C, B-C 3가지 경우에서 왼쪽 영역에 있는 수보다 오른쪽 영역에 있는 수가 더 큰 pair의 개수를 출력하는 것을 쿼리로 하는 문제였다. 하지만 이 문제는 마음에 들지 않았는데,
- 너무 Mo’s를 쓰라고 만든 문제 같음
- 구현이 매우 복잡함 (구현해보니까 300줄 넘게 나온 것으로 기억한다)
- 확장/축소때마다 $O(logN)$인데, 여기에 상수도 커서 $N$과 $Q$의 제한을 잡기가 힘들다
그래서 열심히 고민하다가 이 문제를 떠올리게 되었다. 추가적인 지식(Prefix Sum, 식 정리)이 필요하고, 구현도 조금 쉬워져서 이 문제로 결정했다.
그런데 출제자 회의에서 이 문제를 설명하니까, 그냥 Merge Sort Tree 쓰면 되는 거 아님? 이라는 의견이 나왔고, 생각해보니까 정말로 그래서 그냥 Merge Sort Tree를 쓰는 걸로 결정했다. 덕분에 시간복잡도가 줄어서 $N$과 $Q$ 제한을 쉽게 잡을 수 있었다.
이러면 의도한 풀이의 시간복잡도는 $O(Qlog^2N)$인데, 검수진 중 한 분이 Offline Query + Segment Tree로 $O(QlogN)$에 풀어서 해당 풀이도 추가했다. 대회 중 한 분이 이 풀이로 풀었다.
대회 때 뒤에 4문제 중 유일하게 풀린 문제가 되었는데, 구현이 힘들거나 기발한 아이디어가 요구되는 문제는 아니라서 그런 것 같다.
나머지 문제
A. 안녕 클레오파트라 세상에서 제일가는 포테이토칩
대학교 대회라 쉬운 문제들도 필요해서 만들어진 문제다. 쉬운 문제라 딱히 이슈는 없었다.
B. 장인은 도구를 탓하지 않는다
순서는 상관없는 약간 낚시성? 문제다. 이것도 딱히 이슈는 없었던 것 같다.
D. 양과 늑대
출제자 분이 인터렉티브 문제를 내보고 싶어서 낸 문제다. 하마타면 출제를 못 할 뻔한 문제다. 인터렉터를 잘못 짜서 undefined behavior인 동작이 있었는데, 이게 polygon에서와 백준에서 다르게 동작해서 ! 0 만 출력해도 맞는 경우가 생겼다! 게다가 인터렉티브 문제는 백준님께 직접 전달해서 수정해야 해서 딜레이가 꽤 걸렸다. 다행히 대회 당일 날 수정되었고 잘 작동해서 출제할 수 있었다.
대학교 대회다 보니, 이런 인터렉티브 문제에 익숙하지 않은 사람들이 많을 것 같아서 안내 메일에 인터렉티브 문제가 나오니 한 번 예제문제들 풀어보세요 라고 추가를 했다. 그 덕분인지, 생각보다 많은 사람들이 문제를 풀어주었다. 그래도 틀리는 사람들이 종종 있었는데, 가장 안타까운 경우는 풀이는 맞는데 질문할 때 개행문자(\n)을 안 넣어서 시간초과가 나는 사람들이 있었다. 만약 인터렉티브 문제를 대회 때 낼 계획이라면, 개행문자를 꼭 넣으라고 명시하는 것이 좋을 것 같다.
E. 수열의 합
원래 이 문제는 Small 버전과 Large 버전 2가지가 있었다. Small 버전은 $N$이 지금보다 작은 $100\,000$이라서 그냥 약수를 다 구하는 $O(N\sqrt{N})$로 풀 수 있고, Large 버전은 $10^{14}$라서 조화 수열을 이용해 풀어야 한다. 하지만 문제 수가 너무 많아져서 Large 버전은 제외되었고, Small 버전에 에라토스테네스의 체는 통과 못 하게 $O(N)$만 통과하도록 문제를 수정했다.
그런데 검수진 분들이 낸 체를 이용한 풀이가 빠르게 돌아가 맞는 경우들이 생겼다. 그래서 그냥 빠르게 돌아가는 체는 맞도록 결정을 했다. 대회 때 이렇게 푼 사람들도 꽤 있었다. 다만 PyPy를 쓰면 그냥 체를 써도 맞는 경우가 생기는 것을 대회 때 알았다.
F. 수확의 계절이다!
원래는 크기 제한이 있어서 2차원 배열에 풀 수 있었는데, 골드 중간 문제가 없어서 난이도를 올린 문제이다. 파라매트릭 서치를 해도 지나가는 경로들은 모두 같기 때문에 매번 좌표를 map< >에 넣을 필요 없이 미리 전처리를 하는 것이 핵심이고, 이렇게 안 하면 시간초과가 나도록 설계했다. 그래서 대회 때 시간초과가 나는 사람들이 많았다.
문제는 이 문제도 PyPy를 쓰면 좀 오래 걸리지만 전처리를 안 해도 맞는다는 점이다…(이것도 대회 때 알았다) PyPy 너무 사기에요
G. 게이트웨이 정하기
처음에는 트리의 간선에 가중치가 있고 데이터를 보낼 때 가중치만큼 나눠져서 보내지고… 이런 문제였던 것 같은데 이러니까 계속 1 이하 실수로 곱해져서 소수점 오차를 막을 수가 없었다. 그래서 출제자 분이 XOR로 바꿔보겠다고 하고 조금 수정해서 나온 문제다. XOR 문제를 많이 풀어봤다면 어렵지 않게 풀 수 있는 문제인 듯하다.
H. 현상금 헌터
이 문제는 좌표 범위가 제한되어 있었는데, 생각해보니까 현재 시간만 알고 있으면 다음 도둑을 잡는 좌표는 자동으로 정해지기 때문에 범위 제한을 없앴다.
그리고 처음에는 정수 좌표에서만 잡을 수 있었다. 그런데 그러면 지문도 조금 길어지고 개인적으로 별로 마음에 안 들었다. 조금 생각을 해 보니까 실수 좌표여도 0.5단위로만 잡는다는 것을 알 수 있었고, 깔끔하게 풀 수 있어서 수정되었다.
결국 시간만 알면 특정 도둑을 최단시간으로 잡는 좌표가 정해지고, 이게 최선이라는 것을 알기만 하면 어렵지 않지만, 이를 알기가 쉽지 않아서인지 대회 때는 제출이 없었다.
+ 저게 좀 많이 어려운지 Open Contest때도 가장 늦게 풀렸다…
J. 달나라에 사는 토끼와 우주에서 떨어지는 떡
사이클을 중심으로 생각하면 어렵지 않으나, 구현이 좀 많이 빡세다. 본인도 DFS를 3번 돌려서 겨우 풀었다. 실제 대회에서도 한 분이 막판에 시도하다가 결국 안 풀린 문제가 되었다.
K. 커모드 곰의 연어 사냥
조건이 결국 bridge들의 컴포넌트인 것을 알면 어렵지 않게 풀 수 있는 문제다. 그래서 고인물들은 쉽게 풀 수 있을 것으로 생각했으나, 막상 앞에 문제들에서 막혀서 그런지 제출도 없었다.
처음 출제해보기도 하고, 막학기라 다른 사람들에 비해 시간이 많아서 이 대회에 많은 시간을 썼다. polygon도 처음 써봤는데, 되게 CI/CD느낌이 나서 흥미로웠다. 그리고 스코어보드를 보면서 다양한 방법으로 푸는 것을 보는 것이 생각보다 재미있었다. 이제 졸업하면 Problem Solving을 잘 하진 못하겠지만, 나중에 기회가 된다면 다른 문제들도 출제해보고 싶다.
참가해주신 모든 분들과 출제자/검수진 분들, 플랫폼을 제공해주신 Starlink분들에게 모두 감사의 말씀 드립니다.