2021 인하대학교 프로그래밍 경진대회(IUPC) 출제 후기

2021 IUPC가 무사히 개최되었다.

 

교내대회와 Open Contest까지 진행하는동안 아무 문제없이 끝나서 정말 다행이라 생각한다.

 

대회를 운영하는건 이번이 처음인데, 문제 출제와 운영까지 있었던 일들에 대해 후기를 쓰고자 한다.

---

문제 선정

IUPC 대회는 10월 초반에 개최되었지만, 문제 출제를 준비하는 것은 5월달 부터 시작되었다.

각 4명의 출제진이 대회에 꼭 내고 싶었던 문제들과, 실버~골드 수준의 각 자료구조나 알고리즘에 해당하는 문제, 그리고 수학적인 아이디어가 필요한 문제 등등을 포함해 최대한 많은 후보 문제를 만들었다.

 

그렇게 몇 달동안은 후보 문제 추가만이 이루어졌고, 25개 이상의 문제가 후보 문제로 등록되었다.

이 문제들 중에서 재미있으면서 유익한 문제들을 고르고, 작년 대회의 스코어보드를 분석하고 IUPC에 참가할 예상 인원들의 수준을 고려하여 너무 어려운 난이도의 문제는 잘라내면서 결국 총 10개의 문제를 확정했다.

 

본선 문제로 선택되지 못한 예비문제들, 이후 대회에 쓰일 수도 있어 모자이크 처리했다.

 

그 이후로 적절한 난이도의 새로운 문제 2개를 회의를 통해 추가하면서 총 12문제를 확정지었다.

 

 

검수

지금까지의 IUPC 문제들은 데이터나 디스크립션이 조금 이상하다는 평이 많았고, 나도 그렇게 느낀 문제들이 꽤 있었기 때문에 내가 출제에 참여하는 이번 대회만은 그런일이 없도록 하겠다는 강력한 의지를 가지고 검수에 돌입했다.

 

먼저 지금까지 쓴 문제의 디스크립션을 "전부" 갈아치우는 것 부터 시작했다.

문제에 불필요한 설명은 과감히 없애고, 문제에서 설명하고 있는 용어가 있다면 이를 잘못 이해하는 경우가 있을 수 없도록 디스크립션 수정을 반복했다. 비문은 최대한 지양하고, 문법과 맞춤법에 신경을 썼다.

문제의 형식도 최대한 문제 출제 가이드라인에 맞도록 조정했다. 수식이나 변수에는 MathJax를 사용하여 가독성을 높였다.

 

데이터에도 최대한 문제가 없도록 노력했다.

모든 문제에 최소 100개의 테스트케이스가 포함되도록 많은 테스트 케이스를 만들었고, Edge Case가 있을 수 있다면 각각의 경우에 최소 20개 이상의 테스트케이스를 배정했다.

 

조금 수행시간이 애매하다 싶은 문제들은 Java와 Python으로도 풀이를 작성했고, 이에 맞게 시간제한을 조절했다.

 

이렇게 열심히 노력한 결과 외부 검수에서도 그림이나 오타등의 자잘한 오류를 제외하면 거의 말이 나오지 않았다.

실제 대회에서도 이와 관련한 질문은 나오지 않았다.

 

나로서는 정말 최선을 다했고, 정말 퀄리티 있는 대회가 되었다고 생각하고 있다.

Open Contest에도 많은 분들이 참가해서 문제들을 풀어주셨고, 재미있는 문제들이였다는 칭찬도 많이 해주셔서 감사하게 생각한다.

 

다음은 이렇게 선정된 12문제들의 출제의도와 풀이에 대해 간략하게 설명한다.

---

A. 스키테일 암호

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

23080번: 스키테일 암호

 

모든 팀이 적어도 1솔씩은 하라고 낸 문제이다.

1번째, 1+K번째, 1+2K번째... 문자를 쭉 출력하면 되는 문제이고, 반복문을 사용하는 방법만 안다면 어렵지 않게 풀 수 있었을 것이다.

 

여담으로 내가 출제한 문제 중 코드포스 A번과 같은 Constructive한 브론즈 문제가 있어 이걸 A번으로 하면 어떨까 얘기도 나왔었는데, 처음 보는 사람들은 못 풀 수도 있다고 생각되어 기각되었다.

---

B. 오델로

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

23081번: 오델로

 

단순 구현문제이다. 역시 대부분의 팀이 큰 문제 없이 풀어낼 수 있는 문제였다.

문제를 만드는것 보다도 오델로의 룰을 모르는 사람들도 문제를 이해할 수 있도록 디스크립션을 작성하는 것이 어려웠던 문제였다.

---

C. 균형 삼진법

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

23082번: 균형 삼진법

 

이 때 즈음에 삼진법 반도체에 대한 얘기들이 나오고 있었고, 이를 위해 한 비트가 3개의 상태를 가진다면 수를 어떻게 처리하게 될까? 라는 생각에서 시작되어 출제하게 된 문제이다.

백준엔 정말 다양한 진법 문제들이 있지만 마침 균형 삼진법에 대한 문제는 없기도 해서 딱 좋은 문제라고 생각했다.

 

정답 코드를 봤을 때 가장 푸는 방법이 다양했던 문제이기도 하다.

나는 가장 높은자릿수부터 숫자를 하나씩 결정한거나, 정수를 일단 삼진법으로 바꾼 다음 적절히 바꾸는 방법까지만 생각했었는데, 수학적으로 정말 간단하게 푼 코드들을 보고 감탄하기도 했다.

 

여담으로, 이 문제와 짝을 이루는 균형 삼진법 응용 문제 역시 문제 후보에 있었는데, 너무 어렵다고 생각되어 기각되었다.

---

D. Aging

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

23088번: Aging

 

OS과목에서 한번씩은 본 것 같은 설명이 디스크립션에 적혀있다. Starvation을 해결하기 위한 Aging이 적용된 스케줄러를 구현해 보라는 문제였다. 교육적인 문제이면서 긴 문제를 잘 이해하는지 독해력을 평가할 수도 있고, Priority Queue를 이용한 풀이 역시 크게 어렵지 않은 좋은 문제였다.

 

문제를 조금 잘못 이해하면 하루종일 삽을 풀수 있으니 조심하고, 문제에서 요구하는대로 스케줄러를 구현하여 잘 시뮬레이션하면 된다.

---

E. 두 반으로 나누기

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

23086번: 두 반으로 나누기

 

가장 마지막에 확정된 문제였다.

적절한 골드 중하위권 수준의 문제가 필요했고, 지금까지 사용되지 않았던 주제 중 Union-Find 자료구조, 또는 이분 그래프를 이용하여 문제를 만들자는 얘기가 나왔다.

이와 관련된 문제를 고민하던 중, 간선을 제거하면서 언제 컴포넌트가 분리되는지 확인하는 문제를 간선을 거꾸로 추가하면서 Union-Find를 이용하는 문제에 대해 이야기 하게 되었다.

하지만 이런 종류의 문제는 이미 너무나도 웰노운이었고, 대신 이분 그래프에 대해 이를 적용하면 어떨지 생각해보았더니 괜찮은 문제인것 같아 출제하게 되었다.

 

따라서 정해는 지울 수 있는 간선을 모두 지운 상태인 그래프를 이분 그래프인지 확인하면서 두 가지 색으로 칠하고, 간선을 거꾸로 추가해 나가면서 이분 그래프 여부를 판별하는 것이었다.

서로 다른 색을 잇는 간선이 추가되면 그대로 이분 그래프가 되지만, 같은 색을 잇는 간선이 추가되는 순간 이분 그래프가 아니게 된다.

초기 그래프가 하나의 컴포넌트를 가진다는 조건도 이 때문에 추가된 조건이다. 만약 이런 조건이 없는 상태로 이 방식으로 문제를 푼다면 Small to Large 기법을 추가로 사용해야 되었고, 이는 우리가 원하던 난이도가 아니었기 때문이다.

하지만 검수 단계에서부터 깨달은 사실인데, 이분 그래프 여부가 어느 한 지점을 기준으로 바뀌기 때문에 이분 탐색을 이용하여 Parametric Search를 하는 방식으로도 문제를 풀 수 있었다.

물론 이 풀이도 우리가 원하는 난이도에서 크게 벗어나지 않았기 때문에 그대로 가기로 했다.

실제로 지금까지 정답을 받은 대부분의 코드가 이분탐색으로 이 문제를 풀었다.

---

F. IUPC와 비밀번호

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

23084번: IUPC와 비밀번호

 

적절한 Case Work를 요구하는 문제를 하나 만들고 싶었고, 슬라이딩 윈도우를 추가해서 완성한 문제이다.

 

S와 T의 길이가 같을 때, S에 포함된 문자를 적절히 재배열해 T를 만들 수 있는지 여부는 두 문자열을 이루고 있는 문자의 종류와 개수가 같은지 확인함으로써 알아낼 수 있다.

여기에서 하나의 문자를 다른 문자로 바꾼다면, 한 문자는 1개 많고, 다른 한 문자는 1개 적어지게 된다.

여기에서 T의 길이가 더 길다면 S를 재배열하여 만든 부분이 아닌 바깥 부분의 문자를 바꿨을 수도 있으니 같이 처리하면 되고, T의 길이가 더 짧다면 무조건 불가능하다.

문자의 종류와 개수는 알파벳 소문자가 총 26가지이므로, 26크기의 배열을 슬라이딩 윈도우로 포인터를 이동하며 관리하면 된다.

 

정말 여담이지만, "IUPC = 인하대학교 빡코딩 대회" 는 예전부터 생각해왔던 드립이라 꼭 문제에 넣고 싶었다.

---

G. 최단최단경로

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

23087번: 최단최단경로

 

다익스트라로 최단거리를 구하고, 이 때 사용되는 간선만을 뽑아 DAG를 만든다.

이 DAG에서 최소 사용되는 간선 수를 DP를 이용해 구할 수 있고, 이 때 사용되는 간선만을 뽑아 또 다른 DAG를 만든다.

최종 DAG에서 가능한 최단최단경로의 개수를 DP를 이용해 구하면 되는 문제이다.

 

이 중 2개 이상의 작업을 한 번의 다익스트라/DP로 해결할 수도 있다.

 

교내대회를 진행할 때 제출 코드를 보면서 너무나도 안타까웠던 문제이기도 했는데, 문제를 다 풀어놓고 long long을 쓰지 않거나, 잘못된 INF값을 사용하거나, 배열 개수를 잘못하는 등의 자잘한 실수가 있는 코드가 많이 제출되었기 때문이다.

 

여담으로, 이 문제를 가장 짧은 코드로 푼 팀에게 "최단최단최단코드 상"이라는 이름의 특별상을 주기로 했었는데, 안타깝게 정답자가 없어 수여되지 못했다.

---

H. 난민

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

23090번: 난민

 

\(y = |x - a|\) 꼴의 절대값 함수들을 더해 나간다면, \(x\)가 \(a\)값들 중 중앙값일 때 최소가 된다는 수학적 지식을 이용하여 푸는 문제이다.

 

x좌표들은 문제에 영향이 없으니 따로 더해놓고, y좌표들 중 중앙값이 뭔지 계속 찾아나가면 되는데, 이는 2개의 Priority Queue로 푸는 방법이 가장 잘 알려져 있다.

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

1655번: 가운데를 말해요

 

또는 좌표압축후 세그를 만든다음 kth를 찾는 방식으로도 가능하고, 삼분탐색을 이용해 최소값을 찾는 풀이까지는 정답을 맞을 수 있다.

 

정말 여담이지만, 처음에는 "M"나라에서 내전이 일어나 "L"나라로 이민을 가는 문제였는데, 혹시나 문제가 될까봐 A나라와 B나라로 변경했다.

---

I. 판치기

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

23085번: 판치기

 

동전들의 위치는 아무 관계가 없고, 앞면이 보이는 동전의 수가 같다면 모두 같은 상태로 생각할 수 있다.

한번의 K-뒤집기로 이동할 수 있는 두 상태사이를 간선으로 연결하면 N개의 정점과 최대 N^2개의 간선으로 이루어져 있는 그래프가 되고, 이 그래프에서 최단거리를 구하는 문제가 된다.

 

문제를 그래프로 바꿔 생각할 수만 있다면 BFS 한번으로 답을 구할 수 있는 간단한 문제였다.

 

여담으로, 고등학생 때 학교에서 판치기가 유행했었는데, 나는 판치기를 정말 못했다. 언젠가는 꼭 판치기 최고의 극의인 K-뒤집기를 시전하고 싶다.

---

J. 사탕나무

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

23089번: 사탕나무

 

내가 코드포스를 시작한지 얼마 안되었을 때, 해설을 보면서 가장 기억에 남았던 알고리즘이 바로 Rerooting Technique이다.

 

https://codeforces.com/blog/entry/76150

Online Query Based Rerooting Technique - Codeforces

 

이 감동(?)을 다른 사람들에게도 전해주고 싶었지만 백준에는 관련 문제를 찾기가 너무 힘들었고, Rerooting 연습문제 비슷하게 문제를 하나 내고 싶다는 생각에 만들어진 문제이다.

 

교내대회 도중에는 문제가 정말 짧고 이해하기 쉬웠기 때문에, 난이도에 비해 많은 팀이 도전했다가 쓴 맛을 맛본 문제이기도 했다.

나이브하게 모든 정점에서 거리가 K인 점의 개수를 세는 방식은 최악의 경우 \(O(N^2)\)이기 때문에 물론 통과할 수 없다.

 

여담으로, 원래는 다른 문제들과 같이 내 본명을 사용했는데, 누군가의 요청으로 안즈가 되었다. 안즈는 사탕을 좋아하니 트리도 사탕나무로 바꿔버렸다.

---

K. 꿀벌 승연이

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

23083번: 꿀벌 승연이

 

고난이도 문제인 J와 L사이에 있어서 많은 팀들이 K까지 같이 거르는 일이 있었는데, 이 문제는 정말 말 그대로 꿀 문제이다.

단순한 격자 DP인데, 격자의 모양이 육각형일 뿐이다.

 

교내대회 당시에는 후반까지 K를 도전하는 팀이 없어서 조금 어질어질했는데, 두 팀 정도가 풀이에 성공하자 다른 팀들도 K를 보기 시작하는 걸보고 가슴을 쓸어내렸다.

---

L. Calculate! 3

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

23091번: Calculate! 3

 

출제의도는 올솔방지였다.

 

원래는 쿼리 문제가 아니었다.

ruz님이 처음에 이 문제에서 값 변경 쿼리가 없는 문제를 만들어 왔다. [u - v] 경로의 XOR 값은 [루트 - u] 경로의 XOR값과 [루트 - v] 경로의 XOR값을 XOR한 값이라는 걸 이용하는 문제였다.

문제 컨셉은 정말 좋다고 생각했지만, 이런 아이디어 원툴 문제가 이미 하나 있어서 (사탕나무), 어떻게 할지 고민 하다가 결국 이 문제를 어렵게 바꿔버리기로 했다.

뭔가 변경하는 쿼리를 넣으면 어떻겠냐는 말이 있어서 고민을 며칠동안 했었는데, 간선의 가중치가 너무 커지지 않도록 조정하면 Euler Tour Technique와 Lazy Propagation을 포함한 Segment Tree 풀이로 간선을 변경하는 쿼리도 처리할 수 있다는 것을 알아냈고, 그대로 문제에 적용했다.

 

데이터를 만들기 위해 내가 짠 정답 코드가 2번씩이나 틀린 풀이였어서 너무 고통받았었다. 결국 나이브 풀이를 포함해 서로 다른 3개의 코드로 정답코드임을 확실하게 하고 데이터를 만들었다.

Open Contest에서 과연 얼마나 풀릴지 정말 궁금한 문제 중 하나이기도 했는데, 결국 대회 시간 내에 4분이나 정답을 맞아주셨다.

---

마치며

교내대회 결과

 

교내대회 참가한 팀들이 우리 생각보다 문제들을 못 풀어서 많이 아쉬웠다.

 

이전까지 인하대학교 PS를 이끌던 사람들이 다들 졸업과 군대로 사라지기도 했고, 코로나로 인해 팀을 구성하기도 힘들었을 것이다. 컴퓨터공학과 동아리도 제 역할을 하기 힘들다 보니 신입생들은 IUPC에 대한 정보도 얻기 힘들었을 것이고, 결국 전체적인 실력의 하락으로 이어졌을 것이라 생각한다.

 

이번 대회로 인해 상위권 팀들은 더 위를 향해 가는, 첫 참가인 팀들은 PS에 관심을 갖게 되는 기회가 되었으면 참 좋을 것 같다.

 

오픈 컨테스트 결과

 

교내대회에서 풀리지 않은 문제들은 Open Contest에서 고인물분들이 속 시원히 맞았습니다를 받아주며 우리의 한을 풀어주었다.

심지어 올솔이 3분이나 나왔다! :god:

 

 

참고로, 출제진과 검수진이 매긴 문제들의 난이도는 다음과 같았다. (평균)

 

A. 스키테일 암호: B3
B. 오델로: S4
C. 균형 삼진법: S1
D. Aging: G3
E. 두 반으로 나누기: G3
F. IUPC와 비밀번호: G5
G. 최단최단경로: G2
H. 난민: P5
I. 판치기: G4
J. 사탕나무: P5
K. 꿀벌 승연이: G4
L. Calculate! 3: P2

 

과연 최종 난이도는 어떻게 정해질지 궁금하다.