[대회] 2022 SUAPC Summer 후기

이번 방학에도 어김없이 SUAPC에 참가하였다.
문제는 (여기)에서 확인할 수 있고, 에디토리얼은 아직 올라오지 않은 것 같다.

ICPC에 같이 나가기로 한 팀원들과 나갔다. 우리 팀은 dong_gas, semteo04, Picasso로 이루어져 있다. 여름방학 전에 두 분께서 팀원 구한다고 학회 슬랙에 올리셨었는데, 둘 다 나보다 잘하시니까 재빨리 DM을 보내서 합류했다 ㅎㅎ; 당시에 팀이 없기도 했었고...
팀 명은 대충 앞글자를 따서 DSP로 지었는데 스코어보드 보니까 좀 구린 것 같다. 재미도 없고... ㅋㅋ 기회가 되면 ICPC는 바꿔서 나가자고 해볼 생각이다.

우리 팀은 2위로 대회를 마무리 하였다. 상금 50만 원과 현대에서 주는 상품(?)을 받는다. 뭐 사실 대회 나가기 전부터 다른 강한 팀들을 알고 있어서 1위를 기대하진 않았었다. 근데 막상 시작하고 나니까 우리팀이 생각보다 강하더라 ㅋㅋㅋ 프리즈 당시 1위로 끝났었다. 거기에 다른 팀에 비해 패널티도 여유있게 쌓았었다. 그래서 조금 아쉬운 건 있다...

대회는 학회랩실인 K512에서 진행하였다. 여러 팀이 있었고, 분위기 아주 좋았다 ㅋㅋ 대회가 온라인이라 아쉬웠는데, 서강대는 나름 오프라인 대회 느낌을 낸듯?

최종 스코어보드

프리즈 스코어보드

지난 겨울 SUAPC(1~15위가 모두 7솔)와는 다르게 스코어보드가 이쁘게 잘 뽑혔다. 특히, 마지막에 스코어보드 까는 게 진짜 재밌었다 ㅋㅋ 1~5위 팀의 순위가 한 10번은 바뀐 것 같다. 우리팀도 그렇고 다른팀들도 다 제출을 많이 해서 긴장감이 장난아니었다 ㅋㅋ 이정도면 좌셋인듯 ㅎ

특이한 점은 1~4위 중 유일하게 우리팀만 다이아 문제를 풀지 못했다...ㅎㅎ;

---

타임라인

아래 내용은 내가 기억나는 부분들을 간단하게 적어보았다. (+ 풀이를 아는 문제는 매우 짧은 풀이)

대회 초반에는
내가 A, B, C, D
샘터님이 E, F, G, H, I
피카소님이 J, K, L, M
를 읽기로 했다.



[0:03] B '내비게이션' AC (First Solve)
대회 시작하자마자 A, B, C, D를 열고, 슥 슥 슥 슥 봤다. 퍼솔을 노리기 위해 ㅎㅎ. 딱 보니 A, D는 퍼솔 문제는 전혀 아닌 것 같았고, B와 C가 좀 쉬워보였다. 하지만 SUAPC 3회 출전에 빛나는 나는 B가 후원사 문제길래 바로 B를 읽었다 ㅋㅋ. 보통 후원사 문제는 0솔 방지거나 겁나 어렵거나 둘 중 하나였었다. 암튼 바로 구현하고 AC 받았다.

그냥 잘 구현하면 되는 0솔방지문제였다.



[0:06] F '차의 개수' AC (First Solve)
샘터님이 바로 맞추셨다. 나는 대회 끝나고 문제 올라오고 풀었는데, 한 15분은 걸렸던 것 같다...

1, 2, 4, 8, 16...
1, 2, 3, 4, ...
와 같은 형식으로 출력하면 된다.
최대 -> 수열에 수를 추가할 때 지금까지의 차보다 더 큰 값들로만 새로운 차를 구성하려고 하면 된다.
최소는... 그냥 쉽다.



[0:23] M 'My뷰 꾸미기' TLE
피카소님이 한 번 슥 내셨던 것 같다. 어떤 풀이로 제출하셨는지는 잘 모르겠다.



[0:24] I '딸기와 토마토' AC
샘터님이 맞추셨다. 문제는 아직 잘 모르는데, 구현+케웤이더라. 내가 잘 말리는 분야인데 샘터님이 잘 풀어주셨다.



[0:39 ~ 0:59] C '패스' 2WA, AC
내가 본 문제다. 난 이 문제 어려운 것 같다....ㅎ;
일단 몇 개 해보니까 홀수는 무조건 안될 것 같았다. 뭐 대충 그렇게 풀고 있는데, 다른팀들이 C를 마구마구 맞추더라... 그래서 맘이 급해졌다.
그래서 급하게 몇 개를 해보았는데, 2의 제곱수면 N, 1, 2, 3, 4, 5, 6, ... , N-1 으로 되더라.
당시 여러 팀이 맞추길래 이런 느낌의 애드혹일 것 같아서 코포 A번 풀 때처럼 바로 제출했는데, 올라가지도 않고 틀리더라...ㅋㅋ!

뭔가 큰일났음을 느끼고 몇 개를 더 해보았다. 이때 샘터님도 샘터님이 맡은 문제 중 바로 풀만한 건 없다하셔서 잠깐 봐주러 오셨다.

뭐 그래서 각각 고민하기로 했고 나는 적당히 브루트포스 코드를 짜서 몇 개를 돌려보았다. 돌려보니 짝수는 무조건 되는 느낌이었다. 그래서 샘터님과 짝수일 때 적용되는 일반해를 찾으려 고민했고, 둘이 거의 동시에 찾았다 ㅋㅋ 내가 이렇게 하면 되네요 하면서 보여주니 똑같은 거 보여주시더라. 풀이가 같아서 확신을 갖고 제출했는데, 98%에서 틀렸다...

N=2일 때 if문으로 예외처리를 했었는데, 거기서 실수가 있었다. 1분만에 찾고 다시 제출해서 맞았다…

먼저 N을 사용하고, 1, N-1, 2, N-2, ... 이런식으로 와리가리 치면 모든 수를 다 한 번씩 사용할 수 있다.



[1:25] J '김밥' AC
C를 맞추고 스코어보드를 보니 A와 D는 안풀리기도 했고, 풀기도 싫게 생겨서 팀원들에게 남는 문제 달라고 했다. 그래서 받은 게 이 문제다. 조금 고민해보니 그냥 플4 세그+스위핑인게 보였다. 잘 구현해서 제출했고 바로 AC를 받았다.

좌표압축을 한 뒤, 기준을 맞춰 잘 정렬한 다음 세그로 앞 부분 훑으면서 최댓값을 갱신해주면 된다. 전형적인 문제라고 생각했었는데, 출제자 정해는 이게 아닌 것 같다. 근데, 너무 세그+스위핑처럼 생겨서... 내 주위도 다 이렇게 푼 것 같다.



[1:53 ~ 1:57] L '피라미드' 1WA AC
피카소님이 풀어주셨다. 혼자 푸신거라 문제나 풀이를 잘 모른다.

정확히 기억은 안나지만 이때쯤부터 우리 팀이 1등이었던 것 같다. 속으로 신났었다 ㅋㅋ



[2:01] M 'My뷰 꾸미기' AC
나는 김밥을 풀고 샘터님과 이 문제를 잡았다. 이 당시에 상위권에 조금 풀려 있었다. 수식은 굉장히 깔끔했고, 어떻게 구현하는지가 문제였다.

샘터님은 고민하셨고, 나는 뭔가 검색하면 깔끔하게 나올 것 같아서 n과 m 대충 정해서 나온 수열을 oeis에 돌려봤다. 뭐가 나오긴 나오는데 잘 못알아보겠어서 포기했다.

그러던 와중 샘터님이 nCr=nCn-r 이용해서 바꾼 식을 보여주셨는데, 그 식들의 합이 하나의 Combination인 것이 보였다. 역시 샘터님이다... 보통은 내가 구현을 잘 못해서 샘터님이 구현을 하시지만, 이 문제는 구현은 간단해서 그냥 내가 구현을 하기로 했다. 아무래도 나보다는 나보다 잘 하는 사람이 5분이라도 더 고민하는 게 이득이니까! ㅋㅋ

아 이 문제는 검색으로 푼 팀이 많더라. 본 대회도 검색이 가능한 대회였어서... 검색이 불가능 했더라면 이득을 많이 볼 수 있었을 것 같다 ㅋㅋㅋㅋ

풀이는 n, m이 7, 9일 때의 예시로 대신한다.

[2:17, 2:38] E '1-3 트리' 2WA
이때쯤 나랑 샘터님은 K번 고민을 하고 있었고, 피카소님이 E를 풀고 계셨다. 두 번 정도 내셨는데, 둘 다 올라가다가 틀린다고 하셨던 기억이 난다. 그 중 하나는 51%였다.



[2:53] K '줄 세우기' AC (First Solve)
M을 풀고난 뒤, 샘터님에게 K번 문제 설명을 들었다. 그리고 맨 마지막 합친 결과만 알게 되면 누적합으로 쉽게 풀 수 있는데, 어떻게 알 수 있을지는 생각하지 못한 상태라고 하셨다. 그래서 고민을 시작했다. 처음에 이것저것 고민하다가 줄을 합친다는 부분에서 자연스레 스몰투라지가 생각났다. 그래서 그 말을 했더니, 이 문제는 작은 거에서 큰 걸 합치는 게 아니라 합치는 걸 정해줘서 안 될 것 같다고 하셨다. 한 몇 분 더 생각하다가 줄을 덱으로 표현하면 항상 작은걸 큰 거에 합칠 수 있다는 걸 깨달았다! 이때 기분이 진짜 좋았다 ㅋㅋㅋㅋ
나는 K를 구현하러 갔고, 샘터님은 피카소님과 같이 E를 보러 가셨다.

암튼 나는 스몰투라지, 오프라인쿼리, 덱, 누적합을 이용하여 풀었다. 스몰투라지 기법을 이용해서 한 번 쭉 합친다. 덱을 이용하면 항상 작은 줄을 큰 줄에 붙일 수 있다.
그 후 누적합 배열을 만들어 두고 다시 쿼리를 훑으면서 Union-Find를 사용하면 된다. 3000B짜리 코드를 짜서 좀 불안했는데, 다행히 한 번에 맞췄다.

gumgood님 말로는 그냥 Union - Find 만으로도 풀린다고 한다... djs100201도 내 풀이랑 다르던데 여러 풀이가 있는 듯 하다.



[3:03] E '1-3 트리' AC
내가 K를 구현하고 있는데, 샘터님과 피카소님이 열심히 얘기하시더니 몇 개의 반례를 찾으셨더라. K를 풀었더니 구현만 하면 된다고 하셨던 기억이 있다. 이 문제는 1등팀이 24트만에 맞추었고, 3등팀이 12트, 4등팀은 못맞춘 걸 보면 우리팀 선배들이 매우 잘 풀어낸 것 같다....

암튼 프리즈 직후에 AC를 추가하면서 9솔로 단독 1위가 된 것을 확신했다...


이쯤에서 A, D, G, H 중에서 뭘 풀지 팀원들이랑 고민을 했다. D는 일단 너무 어려워보여서 버리기로 했다. H는 문자열 문제였는데, meque98 팀이 난이도에 비해 빠른 시간에 AC를 받았더라. meque98이 SCPC 나간다고 이것저것 고급 알고리즘을 최근에 많이 밀었던 걸 알고 있어가지고 팀원들에게 뭔가 서픽스어레이, LCP 뭐 이런 알고리즘 쓰는 문제일 거라 얘기했다. 나와 피카소님은 아예 공부해본 적도 없었고, 샘터님도 자신없다고 하셔서 H도 깔끔하게 버리기로 했다. 뭐 그러던 와중에 피카소님이 A를 보더니 어 이거 예전에 연습셋 돌 때 만난 확률 dp문제랑 거의 유사하다고 하셨다.



[3:34] A '수 맞히기 게임' AC
풀이가 꽤 금방 나왔고, 피카소님이 구현하셨다. 바로 맞추면서 10솔이 되었다. 그냥 여기서 대회가 끝나면 좋겠다는 농담을 했던 것 같다 ㅋㅋ 하나 더 풀면 무조건 1등이란 생각을 했다.

재밌는 점은 A번 문제는 지금 골3인데 프리즈 전에 상위권이 아무도 A를 풀지 않아서 본대회에서 거~의 안 풀린 문제이다 ㅋㅋㅋ 확실히 대회는 문제 각각의 난이도 외의 요소도 작용하는 것 같다.



[~5:00] G 'AND, OR, XOR' 3TLE, 3WA
피카소님이 A를 구현하러 가셨고, 샘터님과 나는 G를 풀기로 했다. 근데 뭐 풀 수가 없었다. 그러다가 문제가 너무 깔끔하고 이쁘게 생겼어서 뭔가 똑같은 문제가 무조건 있을 것 같다는 생각을 했다. 그래서 우리팀에서 블루따리를 맡고 있는 나와 피카소님은 검색을 시작했고, 샘터님은 조금 더 고민하는 시간을 가졌다.

열심히 검색하던 중 피카소님이 Convolution, SOS DP, FWHT 등의 키워드들을 발견하였고 관련된 링크를 샘터님께 드렸다. 샘터님은 보시더니 삼성소멤에서 비슷한 글을 보신적 있으시다고 하셨다. 그 글을 찾으셨는데, 대회 당일 삼성 소멤 페이지가 막혀 있었다..... 뭐 그래도 샘터님이 뭔가 해볼 수 있다고 하셔서 FWHT자료 코드를 복붙해와서 열심히 무언가를 하셨다.

나와 피카소님은 관련 내용을 1도 모르기 때문에 그냥 비슷한 자료들을 열심히 찾아보고 있었다. 도와주고 싶었는데 도와줄 수가 없었다....

암튼 그렇게 구현을 해서 내는데 TLE와 WA가 났다. 샘터님이 복붙한 블로그에 오타가 있다는 것을 대회 끝나기 10분 전 쯤 발견했다. 뭐 이것저것 고쳐서 계속 제출을 했지만 결국 맞추지 못했다....

랩실 건너편에는 djs100201, pjh6792(rebro), lem0nad3로 이루어진 팀이 있었는데 이 팀이 한 4시 언저리부터 계속 뭔가 엄청난 제출을 하는 것 같았다. 그러다가 한 4시 40분쯤이었나 갑자기 51%까지 올라간다고 하더라. 51% 듣자마자 E번인 것을 알아냈다. 아까 우리팀이 51%에서 고통받고 있었기 때문에 ㅋㅋ

나는 속으로 제발 반례를 찾지마라 라는 생각을 하고 있었다 ㅋㅋ 저 팀이 막 자꾸 반례를 찾았다고 무조건 맞다고 얘기할 때마다 개무서웠다... 근데 다행히 계속 51%에서 틀린다고 하던게 들려왔다 ㅋㅋ.

그러고 있었는데 57분쯤인가? 진짜 찾았다고 막 셋이서 얘기하던게 또 들려왔다...

나는 한 59분부터는 그냥 컴퓨터 시계만 보고 있었다. 그렇게 6시가 되었고 대회는 끝이 났다. 저 팀은 왜 제출 안되냐고 막 짜증내고 있어가지고 우리는 우승이라 생각하고 좋아했다 ㅋㅋ

그렇게 대회가 끝난 줄 알았는데 대회 끝나고 한 15초 뒤였나? 갑자기 저 팀이 소리를 막 지르는 거다. 알고보니 59분 51초에 제출했던 마지막 코드가 대회 종료 뒤에 채점이 돌아갔는데 그게 AC였던 거다.....



대회 종료 후에(?) 1등을 뺏기는 기이한 경험을 했다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

---

1. 지난 UCPC 예선에서 나때문에 개같이 멸망해서 속상했는데 이번에 꽤 좋은 순위를 받아서 기분이 좋다. 나도 1인분은 한 것 같고... 팀원들에게 고맙다. 나보다 잘하는 사람들인데 나랑 해줘서 고맙다ㅋㅋ!

2. SUAPC Winter에 이어 두 번째 준우승이다 ㅋㅋ 콩의 기운이..

3. djs100201, pjh6792(rebro), lem0nad3로 이루어진 "우승하러 왔습니다"팀이 우승하였다. 닉값 ㄷㄷ.. 사실 대회 전에는 당연히 이 팀이 우승할 줄 알았다. 막상 해보니 우리도 나쁘지 않아서 더 아쉬웠다 ㅋㅋㅋ

4. 알고리즘 공부가 안 되어 있어서 H를 시도도 못한 건 좀 뼈아프다.. ㅎ;

5. 대회에서 플래티넘 문제들을 풀 수 있어서 나름 뿌듯했다. 특히 K번 맞췄을 때 많이 행복했다. 이런 거 한 번 느낄때마다 PS가 다시 재밌어진다 ㅋㅋ

6. 1등 팀 외에도 연세대 팀이나 swoon이 있는 정열맨 팀이 강해서 무서웠다.. 패널티가 비교적 낮아서 2등을 할 수 있었던 듯. 서강대 팀이 아니라 프리즈 이후에 어떻게 되었는지 모르는 상태로 스코어보드를 보니까 너무 무섭더라...

7. 다른 팀들 후기도 궁금하다. 써 줘!

8. 운영진, 출제진, 검수진분들 모두 고생하셨습니다.

9. 즐 추석!