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

대회 결과

첫 오프라인 교내대회이다. 프리즈 풀린 후에도 6솔브/1등을 유지했다. A~F 중에서는 C 빼고 말린 문제 없이 빠르게 다 떠올라서 1등을 차지할 수 있었다.

문제 세트는 여기서 확인할 수 있다. (A~E는 아주대 대회 문제, F~H는 성대에서 추가로 낸 문제)

---

A. 이 대회는 이제 제 겁니다 (AC/+0min, First Solve)

$max(A+C, P)$를 출력한다.

---

B. 마라탕후루 (AC/+11min)

각 꼬치마다 $|A(i)-B(i)| \over |Q-P|$를 계산한다. $Q = P$인지, $A(i) < B(i)$ 이면서 $Q < P$인지 등을 체크해야 한다.

---

C. 밤양갱 (AC+2/+28min)

daldidalgo N개, daldidan 1개를 만드는 최소 operation은 아래 전략으로 구할 수 있다.

1. daldidalgo는 (d)(a)(l)(d)(i)(dal)(g)(o)로 8번만에 만들 수 있다.

2. 한 번 daldidalgo를 만들면, $2^N$개의 daldidalgo는 $N$번만에 만들 수 있다.

3. daldidan은 (daldida)(n)으로 2번만에 만들 수 있다.

4. daldidan은 어떤 조건에 따라 앞 daldidalgo들과 같이 복사해 (daldidalgodaldida)(n)처럼 묶일 수 있다.

4번 조건이 생각하기 까다로워서 2번 틀리고 맞았다. 정답을 수식으로 표현하면 $9 + \lceil log_{2}{(N+1)} \rceil$이다. 대회 중에는 이런 식의 일반화를 못 해서 $N = 2^i$일 때 $10 + \lceil log_{2}{N} \rceil $, 아닐 때 $9 + \lceil log_{2}{N} \rceil$로 나눠서 풀었다. (머리가 안 좋으면 코드가 고생..)

---

D. 렬정! 렬정! 렬정! (AC/+34min, First Solve)

배열 크기가 $100$ 이하이고, 원소의 범위가 $1$부터 $5000$까지이고, 더하고 뺄 수 있는 수의 범위가 $10^6$까지임을 조합해보면,

연산을 $\lfloor {N \over 2} \rfloor$번 사용해 연산마다 $A(i) + (10^{6} - i \times 5000)$, $A(N-1-i) - (10^{6} - i \times 5000) $를 적용한다. 항상 내림차순으로 만들 수 있고, $N$의 기우성과도 관계없이 풀림을 알 수 있다.

---

E. 너 재능 있어 (AC/+55min, First Solve)

2차원 DP 문제이다. $N \times M$  배열을 만든 후 dp를 돌린다. $dp(i,j)$는 i번 이기고 j번 졌을 때의 최대 점수, $dp(0,0) = 0$, $ans = dp(N,M)$이다.

$dp(i,j) = max(dp(i-1,j)+W_i, dp(i,j-1) - L_j)$인데, 조건에 따라 $L_j$를 잘 핸들링하면 된다. 시간복잡도는 $O(NM)$이다.

---

F. 이상한 트리 해싱 (AC/+76min)

동형이 아닌 트리가 존재하기 매우 어렵다는걸 알 수 있다. 실제로 $10^{18}$ 이하에는 총 4가지 해시값 $(2^4, 2^8, 2^{16}, 2^{32})$에만 답이 존재함을 증명할 수 있고 (대회에서는 증명 이런거 없이 감으로 풀었다.), 각각 동형 아닌 트리 구해서 출력해준다. (출제자 Coxie 님이 증명도 해주셨다.)

---

G. AK47 (WA)

F 풀고 1시간 반 넘게 G만 붙들었다. 대회 중에 이상한 풀이에 매몰돼서 계속 틀리다가 마무리했다. 풀이는 슬라이딩 윈도우 비슷하게 윈도우 크기를 $N/2$로 해서 미는거라고 하더라

이상한 풀이는 다음과 같다.

1. 한 구간(처음에는 1~N)에 대해 3분할해서 3분할한 구간이 각각 $R_1,R_2,R_3$라고 할 때, $R_1, R_3$에 2개의 질의를 한다. 결과가 각각 OO/OX/XO/XX일 때로 나눠서

2. OO일 때는 $R_1, R_3$에 각 1개, OX일 때는 $R_2, R_3$에 각 1개, ... 이런식으로 풀었다.

3. 하나의 위치를 찾았다면 남은 1개는 구간을 각 2분할해서 찾는다.

반례가 없는줄 알고 계속 붙들었는데, 끝나자마자 생각났다. (그래도 G,H 푼 사람이 없어 다행히 1등 유지했다.)

---

사실 이 글은 대회 치고 거의 8달만에 쓰는건데, 2025 성균관대 프로그래밍 경진대회 열리면 사람들 많이 보겠죠? 그 때는 출제나 검수하고 있을 것 같네여 ㅋㅋ 성대 소프트/지솦 25학번 환영합니다~