숭고한 알고리즘 대회 출제 후기

지난주 알프스 내부대회에 이어 18, 19일 이틀간 숭고한 알고리즘 대회를 진행했다.

 

기도를 해야할 거 같은 굉장히 성스러워보이는 이름이지만 3년째 이어오고 있는 숭실대, 고려대, 한양대 연합 대회다.

 

지난 2년간은 알고리즘 캠프 4일 + 대회 1일로 이루어졌었는데 올해는 코로나로 인해 대회만 진행했다.

 

여기에서 문제를 풀어볼 수 있고 (코드포스), 지문 및 풀이는 여기에서 확인 가능하다.

 

내가 낸 문제는 Advanced I. 찾아라 드래곤볼!, Marathon J. 3N 투어링, Marathon M. 리그 오브 숭고한, 이렇게 총 3문제다.

 

찾아라 드래곤볼 문제는 대충 HLD와 Lazy propagation과 sparse table과 euler tour technique을 짬뽕시킨 희대의 쓰레기 문제다. 사실 보스 난이도로 내려고 했던 문젠데 이보다 더한 문제가 H번에 존재하는 바람에 준보스가 되었다. 물론 둘 다 대회 4시간동안 0제출로 끝났지만 ㅋㅎ.

이 문제는 "욱제님의 재입대를 기원하는 문제를 만들겠습니다."라는 말을 모 슬랙에서 했었고, 열심히 짱구 굴리다가 생각해낸 문제다. (군필이라면 이 제목의 의미를 알 수도 있다.) 사실 처음에는 경로 업데이트가 아니라 정점 업데이트였으나 검수진들이 내 정해보다 훨씬 쉬운 풀이를 발견한 것도 있고, 완벽한 상위호환 문제가 존재한다는 걸 뒤늦게 깨달아서 작정하고 HLD만 쓰도록 문제를 갈아엎었다.

한 번 츄라이 해보십쇼 다들

 

3N 투어링은 굉장히 무난한 문제라고 생각된다. 코포에서 흔히 볼 수 있는 constructive 문제?

이름이 왜 "3N" 투어링이냐면 원래 3N 시리즈가 있었는데 다 사라지고 정신차리고 보니 얘만 남았다. 처음엔 지문도 거기에 맞춰서 작성했다가 결국 오리지널 느낌의 지문으로 바뀌어버렸다.

그리고 대회가 시작하고나서 깨달아버린 건데 N제한 10만인데 데이터를 만들 때 N제한 1000인줄 알고 만들었다. 근데 어차피 풀이는 똑같아서 조용히 넘어갔다. if(N>1000)while(1); 이딴 코드 내도 통과한다.

N이 1일 때 답이 없다고 제출한 코드가 생각보다 많아서 신기했다. 그리고 내 정해가 제일 안좋은 방법이라는 사실도 깨달아버렸다. ㄹㅇ 이 문제 푸신 분들 아이디어 엄청 좋음...

 

리그 오브 숭고한 문제는 할 말이 없다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ pdf 지문만 6페이지가 나왔다. 이 문제와 비슷한 깡구현 문제가 있었으면 좋겠다는 의견이 나와서 초보자들을 위해 난이도 많이 낮춰서 냈다. 근데 정작 초보자는 건드리지도 않고 고인물만 와서 놀다가 갔음.

테스트케이스는 117개고 문제 특성상 제너레이터를 사용할 수가 없어서 100% 수작업으로 만들었다. 그래서 $N$, $M$ 제한이 15, $T$ 제한이 50이지만 실제로 116개의 데이터에 대해서는 $N \leq 6, M \leq 6, T \leq 30$이고 마지막 1개의 데이터에 대해서만 꽉 채운 케이스다. 특히 예제 만드는데 고통 많이 받았다. 복합 케이스는 예제뿐이고 모든 케이스는 코너케이스로만 이루어져서 실제로 WA 코드를 보면 100개 이상의 케이스는 통과하는 모습을 많이 볼 수 있었다.

암튼 사람들 고통받는 모습을 상상하며 만든 재밌는 문제였다. (물론 그 이상으로 내가 고통받았다.)

 

드디어 출제진으로 참가했던 대회들이 끝났다. 이제 본격적으로 알고리즘 대회 참가 + 동아리 내부 프로젝트를 위해서 빡씨게 구를 생각이다.