SUAPC 2023 Winter 출제 후기

문제 목록: https://www.acmicpc.net/category/detail/3517

에디토리얼: SUAPC_2023_Winter_Solution.pdf

대회: https://www.acmicpc.net/contest/view/950

 

 

이번 2023 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2023 Winter) 에서 출제를 하게 되었다.

 

구체적으로 A(카트라이더: 드리프트), C(점수 내기), H(양 가두기), K(시계 맞추기) 문제를 출제했다.

 

13문제 중에 4문제니까 좀 많이 냈긴 했지만 그만큼 재미있었다.

---

목차
1. 문제 어디서 낼까
2. 문제 만들기
3. 결과
4. 데이터 만들기
5. 대회 구경
6. 마무리

---

1.

작년 말에 마지막 학기가 종강한 후 졸업 전 마지막으로 뭔가 해보고 싶다는 생각이 들었다.

 

그래서 문제 출제를 좀 하기로 했다.

 

좀더 정확하게는 원래 하고 싶었는데 종강 후에 시간이 많으니까 종강하고 나서 하기로 했다.

 

===

 

종강 전주에 백준 게시판을 돌던 중 SUAPC 출제진 모집 글을 발견하였다.

 

사실 출제진을 (그것도 백준에서) 구하는 대회는 많지 않다. 그런데 종강 시즌이라 그런지 구하는 글들이 좀 보였다.

 

나는 그 중에서도 1) 보다 official하고 2) 보다 권위 있고 3) 돈을 주는 수아피시 출제진에 지원하였다.

 

신촌연합 요쪽은 인맥도 빵빵하고 N년전부터 해와서 그런지 굉장히 체계적인 것 같다.

 

수아피시는 기본적으로 신촌연합 알고리즘 캠프 → 캠프 경시대회 → 수아피시 순서로 진행되는 신촌연합의 방학시즌 커리큘럼의 일환이다.

 

우리 고려대학교도 이에 맞서 숭고한(숭실대, 고려대, 한양대) 캠프를 만들어 진행하고 있지만, 아무래도 신촌연합이 대학도 더 많고 틀이 잘 짜여져 있어 굉장히 부럽다.

 

이런 뉴비 양성 프로그램이 잘 짜여있어야 선순환이 계속 도는데, 망할 코로나 때문에 숭고한의 인수인계가 제대로 되지 않은 것 같아 굉장히 슬프고 아쉽다.

 

"잘 되고 있던데요?"라는 말이 있지만 내가 마지막으로 볼 때만 해도 캠프는 없고 대회만 구색 갖춰 치르는 정도였다. 뉴비 유입이 제대로 안되면 무조건 고이고 망하는데...

 

===

 

아무튼 수아피시의 경우 바로 문제를 받는게 아니라 일단 출제진 지원 의사 및 출제할 문제 난이도/개수 를 먼저 받았다.

 

따라서 다행히도 종강 전주에 지원하고 종강 후에 문제를 만들어서 내는게 가능했다.

 

사실 그때까지 문제 아이디어 짜놓은건 하나도 없었다.

 

하지만 지금까지 출제해본 경험상 문제 출제가 시간이 필요한 일은 아니라서 큰 상관은 없었다.

 

2.

일단 문제를 2개 정도는 내고 싶어서, 3개를 지원하기로 했다. 사실 아무 아이디어도 없는 상태에서 1~2주만에 문제 3개를 뚝딱 만드는 것은 쉬운 일이 아니다.

 

그래서 쉬운 문제들을 내기로 했다. 쉬운 문제는 만들기도 쉽고, 세팅도 어렵지 않다. 반면 어려운 문제를 내는건 아이디어 구상도 어렵거니와, 세팅도 만만치 않다.

물론 어떤 문제를 내냐에 따라 꽤 달라지긴 한다. 예를 들어 Flow 문제를 낸다고 하면 세팅이 지옥이 된다. Flow는 알고리즘 특성상 최악의 시간을 잡아먹는 데이터를 만들기 어렵고, 사풀이를 막기 어렵다. 반면 숫자를 몇개 안 주는 DP 문제는 개날먹이다. 말그대로 숫자 몇 개씩만 써재끼면 끝이다. 

게다가 어려운 문제는 내가 푸는것도 어렵기 때문에 만드는 것도 (쉬운 문제 보다는) 어려울 수밖에 없다.

 

그래서 솔직히 다야 이상급 어려운 문제에 대한 출제비와 골드 중위 이하급 쉬운 문제에 대한 출제비는 차이가 많이 나야 한다고 생각하지만, 대부분의 경우 그런 것 같지는 않아 아쉬움이 크다.

 

아무튼 또 너무 쉬운 문제들만 내면 좀 그러니까, (실버급 하나) (골드급 하나) (플래급 하나) 이렇게 만들기로 했다.

 

===

 

실버급 하나는 화장실에서 세수를 하다가 떠올랐다. 화장실에 탁상용 시계가 있었는데, 시계의 특징을 활용해서 유사코(USACO)스럽게 잘 낼 수 있겠다는 생각이 들었다.

그래서 유사코 브론즈 느낌으로 별거 없는 알고리즘만 써서 쉽지 않은 문제를 만들어보았다.

 

그게 K. 시계 맞추기 문제이다.

원래는 M ≤ 100,000 으로 줄 생각이었지만, 그렇게 하면 ``std::set`` 풀이 등 비효율적인 코드가 TLE 난다. 어차피 쉬운 문제기 때문에 낚시도 할 겸 숫자를 작게 줬다.

숫자가 작으면 괜히 DP를 돌려야 할 것 같다거나 하는 이상한 잡생각들이 든다. 특히 팀대회에서는 문제의 난이도를 유추할 수 없기 때문에 낚시의 효과가 증폭된다.

 

골드급 문제는 저번 KCPC(고려대학교 프로그래밍 경시대회) 2021 때 내려다가 못냈던 테마로 내고 싶었다. 바로 2차원 좌표평면이다. 좌표평면에서 뭔가 돌리는 문제를 내고 싶었는데 플래급 이상의 마땅한 아이디어가 떠오르지 않았었다.

 

이거는 그냥 처음부터 쌓아올린 문제다. 원래는 우리가 분리되어도 괜찮을 때를 내려고 했다. 그러면 그냥 붙어있는 양들끼리 감싸는게 좋을 줄 알았다. 그런데 그렇지 않다는걸 깨닫고 조건을 수정했다.

조건을 수정하니 나름 괜찮은 Sweeping 문제가 되었다. 왜냐하면 무지성으로 스위핑하면 틀리기 때문이다.

이렇게 H. 양 가두기 문제를 만들었다.

 

나머지 플래급 문제를 만들기가 조금 어려웠다. 나는 트리를 나름 선호하기 때문에 트리 문제를 만들기로 했다. 트리의 지름 문제와 비슷한 느낌을 가지는 트리의 외심 문제를 상당히 흥미롭게 풀었던 기억이 있었기 때문에, 나도 그런 비슷한 문제를 만들고자 했다.

 

하지만 이건 너무 typical한 트리DP라고 reject 당했다. 더더군다나 다른 신선한 트리DP 문제가 들어왔다고 한다.

 

원래 이렇게 3문제만 만들었다가 왠지 문자열 문제를 아무도 안만들것 같아서 문자열 문제도 플래급으로 하나 급조했다.

Trie 문제도 요즘 본 적이 없어서 Trie에다가 오일러 투어를 해서 레이지를 박는 국밥 문제를 만들려고 했다.

사실 풀이를 먼저 정하고 문제를 만들려고 하면 괜찮은 문제가 잘 안나온다. 자꾸 typical한 쪽으로밖에 생각이 안나기 때문이다.

게다가 그리 시간이 많은 것도 아니었기 때문에 실제로 다소 typical하게 만들어진 문제를 그냥 냈다.

 

이렇게 총 4개의 문제를 지원하게 되었다.

 

3.

실제로 2개의 문제가 accept 되었다.

 

시계 맞추기, 양 가두기 문제에 나름 괜찮은 평가를 해주셨다. 사실 시계는 내가 봐도 괜찮은 문제다. 그리고 쉬우면서 괜찮은 문제는 보통 잘 안만들기 때문에, 빈집일거라 생각했다. 양 가두기는 사람에 따라 typical하게 느껴질 수도 있었는데, 아이디어 하나가 필요해서 accept 해주신 것 같다.

 

트리DP 문제는 역시나 typical하기도 하고 다른 트리DP 문제가 있어서 reject 당했다(G. Azber is playing at Biou's house). 요문제가 훨씬 창의적이고 좋은 문제다. (코포스럽긴 하지만)

 

문자열 문제는 보류긴 한데 대기번호 1번이라는 좋은 평가를 받았다. 왠진 아직도 잘 모르겠다. 다른 사람이 보기엔 나쁘지 않은가 보다.

 

 

아무튼 그래서 SUAPC 2023w 출제진으로서 참가하게 되었다. 개꿀

 

===

 

그런데 어떤 한 문제가 모종의 이유로 빠져버렸다. (아마 어딘가에 나왔었던 문제랑 겹쳤을 거다.)

 

그래서 보류 1등이었던 나의 문자열 문제가 그 자리를 메꾸게 되었다.

이것이 C. 점수 내기 이다.

 

===

 

게다가 쉬운 난이도 문제를 나빼고 아무도 만들지 않아 브론즈 1개와 실버 1개가 추가적으로 필요한 상황이었다.

 

그래서 카트라이더 관련된 (내생각에) 괜찮은 문제를 하나 빠르게 만들어서 제안했다.

 

근데 그게 투표 1등해서 실제로 출제하게 되었다. (A. 카트라이더:드리프트)

 

후원사 문제라서 지문을 조금 길게 썼는데, 솔직히 그게 독이 된 것 같아 조금 아쉽긴 하다.

 

나머지 실버는 pjshwa님이 Sliding Window 문제로 후원사 문제 제작해 주셨다. (F. 배너 걸기)

 

===

 

즉 첫 accept 2문제, 즉석에서 만든거 1문제, 보류 1문제 해서 총 4문제를 출제하게 되었다.

 

문제를 많이 만들수록 출제비는 많아지기 때문에 싱글벙글 준비할 수 있었다.

 

4.

내가 낸 문제들이 하나같이 데이터 만들기 좀 어려운 문제들이다.

많이 어렵진 않다. 그냥 조금 어렵다.

 

근데 A. 카트라이더:드리프트는 쉽다. 4:4 팀전에서 가능한 등수의 조합은 8C4 / 2 = 35가지 밖에 안된다.

따라서 그냥 모든 경우를 쑤셔넣고, 시간 기록 엣지케이스만 손으로 조금 넣어주면 된다.

게다가 오답이 나와봤자 잘 걸러질 것이기 때문에 가장 마음이 편했다.

 

그 다음으로 쉬운건 K. 시계 맞추기이다. 그런데 막무가내로 랜덤 박으면 큰일난다. 이게 생각보다 잘 뚫린다.

엣지케이스 수작업은 물론이요, "그럴듯한 오답" 여러 개 만들어서 일일히 저격해줘야 한다.

실제로 저격데이터가 없으면 뚫리는 오답들이 꽤 있었다.

내가 생각한 오답들은 다 막긴 했는데, 이 문제에 생각보다 다양한 풀이를 제출해 주셔서 모든 오답을 막았는지는 솔직히 아직도 확신이 서지 않는다.

저격하는 가장 쉬운 방법은 딱 하나의 시간 간격 R에 대해서만 정답이 나오고, 나머지는 M이 크게 나오는 데이터를 만드는 것이다.

물론 이런 데이터를 몇 개 넣어주긴 했는데, 그래도 SUAPC 모든 문제 중에 뚫릴 가능성이 가장 큰 문제라 대회 당일까지 계속 쫄렸다.

이 문제는 신기하게 정풀로 깔끔하게 푼 사람이 드물었다.

그리고 어려워 보이지만 정해는 나름 브루트포스라서 "매운 실버"를 생각하고 낸 문제이기 때문에 어떤 사람은 손쉽게 풀 줄 알았는데, 생각 외로 그러진 않았던 것 같다.

 

C. 점수 내기도 데이터 만드는게 그다지 어렵지는 않다. 쿼리형 문제이기 때문에 무지성 랜덤을 박아도 앵간해서는 어딘가에서 틀려주기 때문에 내가 시간이 없었거나 대충 만들고자 했다면 엣지케이스 한두개 빼고는 올랜덤 박았을 거다.

그렇지만 나는 조금의 정성을 더 가미해 엣지케이스를 꽤 여러 개 박았다.

그래도 사실 쿼리형 문제는 랜덤에 크게 의존해도 된다. 확률상...

WA는 진짜 잘 막아지고 문제는 TLE를 피하는 이상한 버킷질이나 조잡한 최적화만 저격해주면 된다.

사실 그래서 쿼리형 문제도 출제하기 쉬운 2티어 날먹 문제라고 생각한다. 근데 이건 문자열 문제이고 엣지케이스를 구상하고 제너레이터 코딩하는게 귀찮았을 뿐이다.

이것..도 누군가는 풀어줄거라 믿었지만 양옆에 B랑 D가 100점방지 문제라서 그런지 아무도 눈길을 주지 않은 것 같다.

오픈콘에서는 나름 풀렸기 때문에 다행인 문제였다.

 

마지막으로 H. 양 가두기가 데이터 만들기 제일 빡셌다. 이거는 지문 쓰는것부터 빡셌다. 그냥 개조식으로 설명하는건 매우 직관적이고 쉬운데, 줄글 형태로 스토리를 풀려니까 엄밀하게 말하기가 힘들어서 검수진 분들께 빠꾸를 몇 번 먹었다.

이친구는 WA와 TLE를 모두 막아야 하는데다가 사람마다 풀이가 진짜 천차만별에 괴상망측한 오답들이 많이 나올만한 문제다.

심지어 문제 특성상 랜덤 박아버리면 우리의 모양이 단순해지기 때문에 WA 및 TLE가 전혀 걸리지지 않는다.

물론, 모양을 적당히 정해서 복잡하게 만들 수는 있다. 그런데 그건 딱 그 모양 하나만 잡는거고, WA는 어떤 모양에서 걸릴 지 모르기 때문에 생각할 수 있는 최대한의 모양을 다 만들어줘야 한다.

 

그래서 일단 WA를 거르기 위해 양을 적게 해서(10마리, 30마리) 랜덤을 적당히 박고, "이거 안하면 틀린다" 싶은 회심의 아이디어에 대해 저격 데이터를 넣었다.

그리고 N*M 격자에 빼곡히 있는 모양, 한 줄에 쭉 있는 모양, 직사각형의 둘레에만 있는 모양, ㄴ자 모양에만 있는 경우, ... 를 추가했다.

TLE를 거르기 위해 우리의 모양이 다이아몬드일 때, 얇은 대각선 찍 모양일 때 를 추가했다. 사실 이거 말고도 몇 개 더 추가하고 싶었는데 어떤 경우에 TLE가 날 지 더이상 생각이 안나서 포기했다.

 

그래도 나름 한 80개 이하의 데이터로 최대한 넣을만한 데이터는 다 넣은 것 같아 뿌듯했고, 실제로 본대회와 오픈콘 때 앵간한 코드는 WA가 난 것을 보고 안도했다.

그리고 이 문제도 (내가 생각했던) 정풀로 푼 사람이 거의 없었다.

 

사실 4 방향에 대해서 sweeping만 해주면 됐다면 골드 중하위가 맞았을 거고 애초에 그런 typical한 문제는 accept 되지 않았을 거다. (적어도 난 그렇게 생각한다.)

그런데 정해 슬라이드에 넣어둔 "그 아이디어" 덕분에 accept 될 수 있었던 것 같다고 생각하기 때문에... 이 문제의 핵심은 "무지성 스위핑에 아이디어 얹기" 라고 생각한다.

솔직히 무지성 스위핑도 쉽진 않다. 귀찮다 많이 ㅋㅋㅋ 그리고 양 겹치는거 고려하는것도 Case work 쪽으로 생각이 기울기 시작하면 큰일 난다. 그래서 체감 난이도가 많이 높은 것 같고... 사실 대회 문제들이 올려치기가 많다. 근데 애초에 내가 이거 대회 중에 풀었어도 무조건 플래 줬다 사실. 아무튼 미안합니다 여러분들 ㅎㅎ

 

===

 

여담이지만 DP나 Output-only 스러운 문제 내시는 분들이 아주 부러웠다.

Output-only는 SPJ만 짜면 되고, DP문제는 말그대로 무지성 랜덤에 엣지 케이스 한두개만 박아도 되기 때문이다.

 

반대로 Flow 같은거 출제하신 분은... 애도합니다.

나도 Flow 한 번 출제해 봤는데 진짜 시간복잡도 꽉 채워서 도는 데이터 만들기가 말도안되게 어렵다.

그래프 문제에 랜덤만 박으면 진짜 큰일난다. 문제 폐기해야될 수준

 

5.

이상하게 대회 때 문제를 안풀고 운영만 하고 있어도 시간이 아주 잘 간다.

프리즈 후에는 제출이 별로 없긴 한데, 그 전까지는 대회 구경하는게 정말 재밌다.

 

SUAPC는 3인 1팀인데다가 컴퓨터도 3개기 때문에 템포가 다소 빠를 거라고 생각했다.

그런데 문제가 난이도순이 아니고 위에서 다음문제 뚫어주는 cubelover 팀같은 존재가 없어서 그런지 생각보다 최상위권도 진행이 느렸다.

 

특히 후원사 문제 2솔 다음이 생각보다 늦게 풀렸다.

골드 3인 M. 좋은 문자열 만들기가 이상하게 12분만에 풀리는 바람에 다른 팀들이 죄다 M번 보느라 말린 것 같다.

M번은 검수진들도 몇 번씩 말린 문제라 특히 대회에서는 말릴 수밖에 없는 문제다.

급기야 K. 시계 맞추기가 52분만에, G. Azber is playing at Biou's house가 53분만에, J. 치즈가 57분만에 풀렸다.

 

도대체 (의도상) 실딱이 문제인 K를 왜 52분간 아무도 풀지 않았는지는 아직도 잘 모르겠다.

솔직히 맨 처음에 M이 아니라 K가 풀렸으면 다른 팀들도 쉽게 풀었을 거다.

K가 쉬운 문제인걸 알고 풀면 쉬운데, 어려운 문제라고 생각하고 들여다보면 말리기 쉬울 것 같긴 하다.

그래도 나름 쉬운 문제 포지션인 K가 쉽사리 풀리지 않아 조금 아쉬웠다.

 

그리고 골드 1, 골드 2인 G와 J가 연달아 풀린 것도 조금 웃겼다. 게다가 G, K, J의 퍼솔 팀이 모두 다르다. 사실 이건 충분히 그럴 수 있다.

 

그 외에는 E가 의외로 풀렸고... L은 깡 아이디어 (깡수학) 문제라 듬성듬성 풀렸고... I는 나름 자료구조 국밥 문제인데 (인터넷 검색이 가능함에도 불구하고) 거의 안풀렸다.

그리고 플래 중하위로 의도된 C가 풀리지 않아 서러웠다. E랑 L 고민하다가 못푼것 같긴 하다. L이 진짜 풀 수 있을 것 같으면서도 못풀겠는 문제다.

 

아 그리고 H. 양 가두기에서도 생각보다 많은 팀이 말렸다. 특히 혼혈 서강..준 팀이 24번 제출했지만 결국 틀렸다. 페널티 관리가 말도안되게 아름답던데 조금 죄송스럽다. H 한 번만에 맞춘 팀은 좀 대단한 것 같다.

그래도 H는 많은 분들이 제출해주시고 또 풀어주셔서 보는 맛도 있었고 뿌듯함을 많이 느낄 수 있었다.

 

모든 참가팀이 A. 카트라이더:드리프트를 풀어주셔서 그것도 굉장히 만족스러웠다. 실제로도 지문이 난해하다는 피드백이 있었지만 어쨌든 "가장 쉬운 문제"로써의 역할을 다한 것 같아 기쁘다.

 

그리고 C. 점수 내기도 오픈콘에서는 꽤 풀렸기 때문에 이번에 출제한 A, C, H, K 문제 모두 나름 잘 냈다는 생각이 든다.

 

6.

사실 C. 점수 내기는 검수진 두 분께서 골드...를 투표하셔서 버프를 먹일까 고민 많이 하다가 그냥 냅뒀는데, 다행히 기여가 플래 3이 찍혔다.

H. 양 가두기도 사실 골드 상위를 의도하고 냈지만, 자자한 원성 끝에 플래 5가 되어버렸다. sweeping 이외의 아이디어가 어렵다는 평이 많았다. 사실 더럽게 구현하려면 끝이 없어지는 문제긴 하다.

K. 시계 맞추기도 완벽한 실버라고 생각했고 문제 선정해주신 분도 그랬고 검수진도 그랬는데, 골드 5로 올라가 버렸다. 그래도 배열이랑 반복문 개념만으로 골드급 문제를 만들었다는 의의를 가지기로 했다.

 

출제한 문제들 질도 나름 괜찮은 것 같고, 데이터도 안뚫리게 잘 만든것 같고 대회도 잘 굴러간 것 같아 전체적으로 만족스러운 대회였다.

 

 

마지막으로 고생이 정말 많아 보였던 SUAPC 운영진 분들에게 감사를 표합니다. 출제진으로 활동하게 되어 정말 좋았습니다!