2023 성균관대학교 프로그래밍 경진대회 후기

대회 결과

2022, 2022 소프트의 밤에서는 휴학생이라 수상권이라도 상금을 받지 못했었는데, 이번에는 복학하게 되어 상금을 받을 수 있게 되었다! SW마에스트로 코딩테스트와 완전히 겹쳐버리면서 5시간 중 중간 2시간 반을 못 쓰게 되었지만, 그래도 휴학생 제외 10등으로 마무리했다. (안 겹쳤으면 최소 6등이었다 ㅠㅠ)

문제 세트는 여기서 확인할 수 있다.

---

A. 증가 배열 만들기 (AC+1/+6min)

코포식 문제인데, 처음에 $NM$개 숫자가 필요하다고 생각해서 한 번 틀리고 다시 고쳐서 맞았다. $N+M-1$개의 숫자가 필요하고, $(i,j)$ 일 때 값은 $i+j+1$ 이다.

---

B. 토크나이저 (AC+1/+191min)

처음에 어려운 구현문제라고 생각해 C부터 풀자고 하고 넘어간 뒤, 소마 코테 끝나고 잡은 문제이다. 코테 전에 1시부터 1시 반까지 30분밖에 시간이 없었기 때문에, 시간 페널티를 생각하면 무조건 30분동안 많은 문제를 푸는게 이득이었기 때문에 차라리 C D를 풀어버리자! 했다. (근데 C밖에 못 품)

파싱이 있어 파이썬으로 푸는게 좋았겠지만, 그냥 C++로 풀었다. 한 번 틀린건 ||||나 &&&&를 생각 안하고 짜서 틀렸다.

---

C. 마법박스 (AC/+16min)

인터렉티브 문제였는데, 굉장히 빠르게 풀었다. 위기 상황일 때 초인적인 힘이 나온다는데, 돈 걸려 있는 대회에서 불리한 조건이 있어 그런지 C번 구현하는 순간만큼은 속기사 뺨쳤다. 결국 First Solve 했다. A, C까지 풀고 B 구현하다가 코테 치고 다시 왔다.

생각해보면 정답은 항상 소수임을 알 수 있다. $1~N$까지 소수 판정은 에라토스테네스의 체를 썼고$O(NlogN)$ (그냥 소수판정하면 $O(N \sqrt{N})$), N이 최대이더라도 소수 개수가 100만개 이하이므로 이분 탐색을 통해 20번 이하의 질문으로 해결이 가능하다.

---

D. 벌레컷 (AC+2/+212min)

이 문제도 소마 코테 전에 아이디어가 생각났지만 시간이 없어 구현까지는 하지 못했다. 머리, 가슴, 배를 $S_1, S_2, S_3$로 잡고, $N-2$개의 $S_1$에서 이분탐색을 돌려 가능한 경우의 수를 계산한다. 먼저 배열을 누적 합 배열로 바꾸고, 요구 조건에 따르면 $S_2 > S_3 > S_1$, $S = S_1+S_2+S_3$이고 $S, S_1$은 고정값이다.

$S_2 > S_3$는 $S_1+S_2 > \frac{S+S_1}{2}$, $S_3 > S_1$는 $S_1+S_2 < S-S_1$으로 변환이 가능하므로, lower_bound를 활용해 가능한 범위를 구하면 된다.

---

E. AB (AC/+266min)

트라이를 사용해야 할 것 같았지만 실전에서 한 번도 안써봐서 다른 방법을 모색하다가, 일단 $B$의 원소들을 뒤집어서 저장했다. 그리고 set을 활용해 원하는 경우를 찾는다면, find의 시간복잡도가 $O(|S|^2logQ)$가 될 것이고, find 개수가 많다면 터질 수 있긴 하다. 그런데 다행히 터지진 않았다 ㅋㅋ

일단 $A$의 접두사와 $B$의 접미사 쌍은 $|S|-1$개가 나오고, string set A, B에서 이분탐색을 돌린다면 쉽게 개수를 찾을 수 있다. 근데 $B$도 뒤집었기 때문에 접두사를 찾으면 되고, set에서 접두사가 특정 문자열인 개수를 찾는 문제는 이분탐색 2번으로 가능하다. 예를 들어 b, ba, bab, bc, bz가 있을 때 접두사가 ba이려면 lower_bound(ba)와 lower_bound(bb)를 해주면 경우의 수를 구할 수 있다. 근데 c++ set는 인덱싱이 안되어 있어, pbds(Policy Based Data Structure)을 활용해 order_of_key를 사용했다. 대회에서 은근 많이 쓰이는 자료구조인 것 같다. pbds에 대해서는 나중에 또 설명하겠다.

---

2022년, 2022 솦밤, 2023년 모두 참가하고 느끼는 거지만 대학교 대회 중 우리학교 대회 문제가 제일 깔끔하고 좋다고 자부한다. 업솔빙도 해야지 하고 계속 미뤘는데, 시간 나면 언젠간 해야겠다.