제 1회 숙명여자대학교 교내 알고리즘 경진대회 후기 (출제)

먼저 1회 대회에 문제를 낼 수 있게 해준 숙명여대 도도님께 감사의 말씀을 전합니다.

 

맨 처음에 출제 제의를 받았을 때 정말 기분이 좋았었다.

알고리즘을 시작한 지 이제 1년 되었는데 벌써 벽이 느껴지고, 잘하는 사람들은 많고

같이 알고리즘 하던 사람들은 한두명씩 탈알고를 하여 알고를 버릴까 했다.

 

이제 직접 대회에 참가하는건 힘들다고 생각이 들어 출제로 방향을 돌리기로 했다.

그래서 2020 신촌 윈터 알고리즘 캠프에서 출제를 한 번 해봤는데, 생각보다 너무 재밌었다 (그리고 돈도 준다).

그래서 출제할 기회만 계속 노리고 있었는데 이렇게 빠르게 기회가 올 줄은 몰랐다.

 

B. 눈덩이 굴리기

이 문제는 BFS, DFS를 모르던 시절

극한의 케이스워크로 1로 만들기 문제를 푼 뒤,

정해인 완전탐색을 보고 맨 처음 만든 문제이다.

 

N이 10이라 그냥 2^N 돌려도 되고 

dp로 N^2도 된다.

 

간단한 완전탐색이라 B번에 배치했지만

다른 문제들에 비해서는 생소했었는지 풀린 문제들 중 가장 적게 풀린 문제가 되었다.

근데 실3은 너무 underrated인거 같기도 하다.

 

C. 헌내기는 친구가 필요해

이 문제는 새내기시절 코로나때문에 친구를 못만들고

화가 잔뜩 나 있을 때 만들었던 문제이다.

 

그냥 평범하게 BFS를 돌리고 만난 친구 수를 세어 주면 되는 문제인데

특정 언어의 DFS인 경우 시간 초과가 나는 경우가 있었다.

그래서 특정 언어에서의 DFS를 오답으로 할 것이냐 아니면

시간을 엄청 늘릴 것이냐로 고민했었는데,

15초를 줘도 못돌길래 N제한을 반토막 내버렸다.

 

탐색 문제를 낼 때 자바가 너무 거슬린다.

 

F. 펭귄 네비게이터

먼저 이 문제는 한 번 바뀌었었다.

앞 문제들을 보니 너무 탐색밖에 없길래 무조건 F, G는 다른 문제를 내기로 마음먹었었다.

일단 F를 정수론으로 정했었는데

 

원래 문제는 구간의 gcd를 구하는 문제였다.

세그를 이용해 QlogN으로 푸는 문제였는데

백준에 그 상위호환 문제가 이미 있었다.

 

살펴보니 레이지로 업데이트까지 시키던데 아무튼 너무 슬펐다.

 

정수론 문제를 다시 내기 위해서 여러 것들을 찾아보다가 조합론을 보게 되었다.

그 중 카탈란 수열을 보게 되었는데, 너무 재밌어보여서 

연습 문제 중 하나를 형태를 변형해서 내게 되었다.

 

카탈란인걸 꽁꽁 숨겨서인지 보통 카탈란은 G3으로 평가되는데 

고수분들이 카탈란인지 아는게 힘들다고 G2를 줬다.

근데 너무 웰논인거같아서 다음부터는 이런건 안내야겠다.

 

 

G. 도도의 수학놀이

이 문제도 한 번 바뀌었는데,

원래 바뀌기 전 F번은 P5-P4정도 난이도로 생각하고 있었다.

하지만 문제가 갑자기 바뀌면서 골드로 난이도가 떡락하니 

대회에 플래문제가 없는 상황이 일어났다.

그래서 급하게 도도의 수학놀이를 수정했다.

 

원래 이 문제의 a_i 제한은 9였다. 따라서 먼저 9와 6만 바꿔두고

수 크기 순으로 정렬하면 끝이었다.

 

하지만 난이도를 올리기 위해서 a_i제한을 올리고 수 중 하나를 

한 번 더 사용할 수 있도록 해서 플래티넘까지 난이도를 올렸다.

 

이 문제가 대회중에 100번 이상 시도되었는데

시도 수가 올라가는 것을 보면서 너무 안타까웠다.

 

이 문제는 내가 만든 문제 중 처음으로 플래티넘을 받았는데

낚시 요소가 너무 많아서 그런 것 같다.

평균 시도 횟수가 6을 넘어가던데 다들 많이 틀려주시니 기분이 좋다.

 

 

재밌는 경험이었고 검수진으로라도 다음 대회에 참가할 수 있으면 좋겠다.

끗