2023 고려대학교x연세대학교 프로그래밍 경시대회 출제 후기

고려대학교가 먼저인 이유는 가나다순

2023 고려대학교x연세대학교 (연고전) 프로그래밍 경시대회를 개최했습니다.

연세대는 신촌연합에 속해있지만 친구학교인 고려대학교랑도 교류가 있으면 좋을것 같다고 생각해서

고려대학교 알고리즘 동아리 ALPS와 함께 대회를 만들었습니다.

 

대회 정보 : https://www.acmicpc.net/contest/view/979

대회 문제 : https://www.acmicpc.net/category/detail/3564

문제 솔루션 : https://upload.acmicpc.net/0564fb41-dbcd-498b-92a0-37cf62f6832b/

 

출제진/검수진중 고수분들이 이렇게 많은 대회는 처음이라 같이 준비하면서 영광이였습니다.

이번 대회는 서브태스크 대회로 계획을 했는데, 중간 서브태스크는 풀만하게 만들고 100점을 맞기 위해서는 어려운 문제들이 잔뜩 출제되었습니다. 특히 저는 랭커분들이 내신 문제들은 손도 못 대겠더라고요.. 어차피 서브태스크 대회니까~ 라는 생각으로 다들 힘조절 없이 문제 내시는거 보면서 재밌었습니다. 근데 정말 좋은 문제들 같아요

 

글쓸 당시 문제 난이도.. I번은 아직 미정인데 루비가 찍힐것 같음 . .

어차피 서브태스크니까~ 라는 생각으로 다들 문제를 내다 보니 C번까지 실버다가 갑자기 D번부터 급발진하기 시작했습니다. 분명 처음 시작은 이러지 않았던 걸로 기억하는데 . .

 

TOP 10

이 대회를 만들 때 고려대학교가 워낙 잘하기 때문에 TOP 10이 다 고대로 도배가 되면 어떡하지 ?? 했는데 생각보다 연세대 분들도 잘 싸워주셔서 놀랬습니다. 연세대 최고최고~ 그럼에도 불구하고 고려대학교가 한걸음씩 더 앞서있긴 하네요. 이번 대회는 연세대가 졌지만 앞으로 또 이 대회가 계속 열리게 된다면 다음에는 연세대가 노려볼만 한 것 같아요

 

저는 이번에 A번이랑 E번 문제 출제했습니다.

제 문제 많이 풀어주세요

 

A. 당신은 운명을 믿나요? - https://www.acmicpc.net/problem/27930

초보자 좌절금지 문제였는데 그런거 치고는 살짝 생각할 부분이 있습니다.

서브태스크 1이 정말 악질인데 무조건 YONSEI를 출력하면 된다.. 사심 가득한 문제

사실 이번 대회 출제진이 kdh9949님 제외하고는 연고대 소속의 출제진이기 때문에 다들 본인 문제에 사심 가득 들어간 statement들이 많습니다. 

 

 

E. 마계안암 - https://www.acmicpc.net/problem/27934

저의 ps 역작이 되지 않을까 싶습니다. 정말 마음에 들어요

방학때 코포 E번 문제들을 돌아보다가 다익스트라를 잘 모르고 있다는 생각이 들어서 다익스트라를 공부하고 있었습니다.

다익스트라를 이용해서 w>0일때 각 정점에 도달하는 경우의 수를 구하는 문제를 풀어보고 신기하다.. 고 생각했는데 문득 헬스를 하던 도중 w=0일때의 풀이가 진짜 의도치 않게 떠오르게 되어서 집에 와서 증명을 해보게 되었습니다.

제 코포 닉네임이 Serendipity__인데 딱 이럴때 쓰는 말인 것 같아요

 

>> 문제 발상 

문제를 푸는 데 필요한 관찰들은 이렇습니다.

w>0인 문제의 풀이를 그대로 w=0인 문제에 적용했을 때, 틀리는 이유를 생각해 보면 됩니다.

그 이유는 바로 최단거리가 같은 vertex들은 다익스트라 내에서 순서가 뒤죽박죽이 되기 때문입니다.

w>0인 경우에는 그 뒤죽박죽이 되는 경우에 의해서 영향을 받지는 않는데, 이는 최단 경로를 구성하는 path에 놓인 vertex들의 최단경로가 strictly increasing이라서 그렇습니다.

그런데 w=0인 경우에는 strictly increasing이 아닌 그냥 increasing이라서, 순서가 뒤죽박죽이 되었을 때 path에 놓인 vertex들이 다익스트라 알고리즘에서 순서가 꼬여버리는 경우가 나오게 됩니다. 이런 경우를 막아야 합니다.

그런 경우를 막기 위해서, w=0인 edge들에 대해서 어떻게 처리를 해주어야 할지를 생각하게 되고, 그러다 보니 w=0인 edge들만 이용해 SCC로 묶어야 한다.. 라는 생각이 떠오르게 되었습니다. 풀이는 editorial에 작성했습니다.

 

아무튼 이걸 떠올리고 어딘가에 문제가 존재할 것 같다는 생각이 들어서 검색해 봤는데, w>0인 문제들은 대충 검색해도 나오는데 w=0은 안 나오는 걸 보고 문제은행에 저장해 두었습니다. 나중에 lky7674 선배한테 물어봐도 처음 보는 문제 같다고 해서 무조건 이걸 내야겠다고 생각했습니다. 중간에 설마 누가 내진 않겠지 하면서 조마조마 했습니다. ㅋㅋ

 

사실 이 문제 저도 처음에 풀이 내면서 틀렸고, 데이터 만들기가 정말 어려웠던 문제였습니다. 이문제 빡세게 검수해주신 jthis님한테 무한한 감사 드립니다.. 제 틀린 풀이도 잡아주시고, 데이터도 여러 방면으로 많이 추가해 주셔서 문제가 허무하게 뚫리지 않아서 정말 감사드립니다.

특히 이 문제의 맞왜틀이 정말 심했던 것 같아요. 본대회 중간에 정답률 1% 찍고 왔는데, G,H,I는 워낙 어려워서 에잉 그냥 서브태스크나 긁어야지 하고 다들 섭테 풀이를 내니까 0%가 나왔는데, 이 문제는 ㅅㅂ이게왜틀림 이런 느낌으로 무한 제출 하시는 분들이 종종 계셨습니다. 그래서 사실 제가 데이터 만들때 뭔가 실수한건 아닌가.. 라는 생각도 들어서 좀 쫄렸어요

 

 

그래도 대회는 성공적으로 마무리 된 것 같습니다. 참가자 분들도 정말 많았고..

오랜 시간동안 문제 푸시느라 고생 많으셨습니다. 다음에 또 좋은 대회 만들 수 있도록 해보겠습니다.

특히 대회 준비하는데 준비기간이 엄청 타이트한데도 좋은 문제 내주신 출제진분들과, 검수진 분들께 정말 감사 드립니다.

안녕