2024 SUAPC winter 후기

1등은 연세대의 AKARAKA!

 

SUAPC winter에서 1등했습니다.

팀명은 AKARAKA, 어떻게 보면 연세대의 암구호라고 생각해도 좋은데 여태까지 아무도 이 팀명을 쓴적이 없길래 제가 제안했습니다. ICPC 팀명 그대로 SCC 시리즈를 할 생각도 있었지만 그냥 땡겼습니다. 대신 이 팀명을 쓴다면 반드시 좋은 결과를 가져와야 된다고 생각했습니다.

 

결과는 11솔입니다. 베트남 가기 직전에 나름 만족스러운 결과였던 것 같습니다.

작년에 팀연습은 많이 했는데 저희가 각자 체급이 부족하다고 생각해서 이번 방학에는 쭉 개인연습으로 돌린게 도움이 됐던 것 같기도 합니다. 이번에 유난히 신청도 많고 잘하는 팀들도 많이 신청해서 이번시즌 1등은 쉽지 않을 거라고 생각했습니다. 확실히 1년 넘게 같이 팀연습도 하고 대회를 치르다 보니 팀 대회중에 운영이 꽤 안정적으로 되는 것 같습니다. 저희도 나름 짬이 생긴 걸까요 ..

 

 

간단하게 대회 timeline을 따라가 보면서 어떤 일이 있었는지 문제 리뷰를 해보겠습니다.

대회가 끝나고 나서 안 일이지만 꽤 많은 퍼솔을 가져왔던 것 같습니다.

사실 퍼솔에 아무 의미를 두지는 않기도 하고 저희가 원래 퍼솔이 별로 없는 팀인데 컨디션이 좋았던 것 같습니다.

 

M - 엘리스 트랙 매칭 (00:01, First solved) - ystaeyoon113

쉽습니다. 사실 문제 읽다가 풀이가 생각나는게 있어도 남은 문제 다 보고 들어가는걸 선호하는데 이건 너무 쉽기도 하고 그냥 빠르게 페널티 없애는게 이득인 거 같아서 냈습니다.

 

A - 가상 검증 기술 (00:02, First solved) - playsworld16

뭔 문제인지 모르지만 쉬운 것 같습니다. 맨 앞뒤에 쉬운 문제들이 있는것 같네요

 

C - 스펀지 (00:07, First solved) - playsworld16

앞 담당인 playsworld16이 알아서 잘 밀어준 것 같습니다.

 

H - 신촌 통폐합 계획 (00:13, First solved) - coconut99

coconut99도 본인 영역에서 빠르게 한 문제를 풀었습니다. 사실 각자 영역에서 처리한 문제는 저는 무슨 문제인지도 잘 모릅니다..

 

L - 신촌 도로망 관리와 쿼리 (00:32) - ystaeyoon113

제가 IJKL을 모두 읽고 생각해보다가 L번이 먼저 풀렸길래 가서 풀었습니다. 어려운 문제는 아닌데, 구현을 절기 좋은 문제인 것 같습니다.

 

F - 호떡 뒤집기 (00:39, First solved) (+1) - coconut99

건우가 아..한번 틀렸다 하고 아쉬워했지만 그래도 빨리 고쳐왔습니다. 사실 그때까지 페널티가 매우 좋았기 때문에 별로 지장은 없었습니다.

 

E - 문자열-그래프 매칭 (00:52) - ystaeyoon113

투포인터 문제인데, 오른쪽 포인터 2개를 관리해야 하는 문제라서 좀 신선했습니다. 나중에 누가 출제했는지 봤는데 아는 분이였고 이분이 내신 문제들을 제가 좋은 문제라고 생각하는 것 같습니다.

 

G - AND,OR,XOR 2 (01:08) - coconut99

그냥 수학틱한 문제인 것 같고 건우 영역에 있는 문제라서 건우가 풀었습니다. 까다로운 내용이 살짝 있는 것 같습니다.

 

 

여기까지가 8솔인데, 여기서 많은 팀들이 꽤 오랜 시간을 끌었던 걸로 알고 있습니다. 그리고 저희팀도 여기서 어떤 문제를 잡아야 하는지가 꽤 어려웠고 프리즈 이전에 8솔을 한 다른팀들도 저희랑 비슷한 생각을 했을거라고 생각합니다. 다만 coconut99가 B번을 너무 스무스하게 뚫어줬기 때문에 저희는 프리즈 이전에 마음 놓고 한문제를 앞서 있을수 있었습니다.

 

 

B - 가장 짧은 높이 (02:46, First solved) - coconut99

이 대회의 조커문제입니다.

저도 남은 5문제 중에서 긁어보다가 보자마자 불도저 생각을 했고 한 직선 조건이 없어서 그냥 짜증나지만 나중에는 풀어야 되는 문제.. 정도로 생각했고, 안 풀리니까 B번을 들어가려고 했는데 메모리 제한이 매우 작습니다.

불도저는 O(n^2)정도의 공간복잡도를 필요로 하기 때문에 이쪽으로 풀지 말라는 말과 같습니다.

그래서 360정렬을 해야 하나.. 했는데 이것도 쉽지 않고 유기하고 있었는데 coconut99가 그냥 이거 최소값의 최소값이라서 그리디하게 고르면 하나는 걸린다.. 라고 했고 사실 저는 잘 납득은 안됐지만 coconut99가 확신이 있어 보이길래 한번 짜보라고 했습니다. 그리고 한번에 맞아왔습니다.

기하 문제가 한번에 뚫리면 그만큼 좋은 일도 없습니다. 수상권에 있는 다른 팀들도 여기서 많게는 60틀까지도 박은 걸 생각하면 진짜 이 문제가 조커였던 것 같습니다. 그리고 프리즈 이전에 풀어놨기 때문에 아마 다른 팀들이 여기서 많이 무덤을 세운 것 같습니다.

 

J - 토지 판매 (03:34, First solved) (+1) - ystaeyoon113

저도 여러 문제에서 헤매고 있다가 이거나 보자 했습니다. 사실 다들 잡고 있는 문제가 하나씩 있었고 서로 의견같은걸 계속 주고받으면서 문제를 돌아가면서 보고 있었고, 저는 다른 문제들에 답이 없어보여서 일단 이걸로 갔습니다.

문제의 수식을 처리할 때 어떤 것들을 독립적으로 처리할 수 있는지를 계속 파다 보면 식을 꽤 좋은 형태로 변형할 수 있습니다. 그리고 가장 핵심적인 아이디어는 다음과 같습니다. 가령 1234 + 5678 + 959824의 백의 자리 숫자는 어떻게 구할 수 있을까요? (덧셈에 받아올림이 없다고 가정했을 때) 이는 (1234//100 + 5678//100 + 959824//100)의 결과에 modulo 10을 취한 것과 같습니다. 이 아이디어가 있다면 floor sum으로 마지막 과정을 처리할 수 있습니다.

틀렸습니다가 한번 나왔는데 범위가 굉장히 애매해서 overflow만 잘 잡으면 된다고 생각했고 생각하기 싫어서 싹다 int128을 썼는데 덕분에 4908/5000ms로 아슬아슬하게 통과했습니다.

 

D - 배열 제작의 달인 (04:31, First solved) (+1) - ystaeyoon113, coconut99

사실 제가 한 2시간쯤부터 오랜 시간동안 잡고 있던 문제입니다. 보다가 버리고 보다가 버리고...

이 문제를 multinomial로 바라봤을 때 여기서 dp.. 혹은 생성함수.. 등을 계속 생각하다가 잘 안돼서 버렸는데

coconut99가 중간에 문제를 계속 긁더니 egf... 얘기를 하자마자 문제의 실마리가 해결됐습니다

저도 중간중간 계속 조합론 수업에서 들었던 형태가 보여가지고 gf쪽으로는 생각하고 있었는데 egf 얘기를 듣자마자 놓치고 있던 퍼즐조각이 맞춰졌다고 생각했습니다.

구현은 제가 하기로 했고 디버깅 잠깐 이후에 맞았습니다. 한번은 TLE가 났는데 coconut99가 FFT한 결과를 사이즈 최대를 조절해줘야 된다는 얘기를 듣고 바로 고쳐서 맞았습니다.

 

 

I - 최대공약수 게임 (Not Solved)

게임이라서 제가 시작하자마자 playsworld16한테 넘겨줬는데, 중간중간 제가 자꾸 그래프 + matching얘기를 섞어가지고 문제 풀이가 산으로 가버린 것 같습니다. 숫자를 한번 이상 쓸수 없다는 조건을 보고 저는 matching에 완전히 꽂혀있었고 사실 이 문제를 dp로 끌고가는 아이디어가 정말 놀라운 것 같습니다. 정말 좋은 문제인 것 같습니다.

 

K - 신촌방위본부: 지하 벙커의 비밀 (Not Solved)
투 스텝 문제입니다. 투스텝은 대회 전날 예비소집에 투스텝이 나온대서 처음 풀어봤습니다. 거기에는 투스텝 A+B가 있었는데, 여기에는 투스텝 + 센트로이드가 있네요 ................................

playsworld16가 정말 오랜시간동안 잡고 있었던 문제고 센트로이드로 반복적으로 찾아나간다 라는 아이디어와 색칠하는 좋은 방법은 떠올렸지만 구현을 계속 하다가 마지막에 방법에 사소한 문제가 있을 수 있는데 그 처리가 꽤 까다롭다는 것을 발견했을 때 시간이 얼마 남지 않았기 때문에 해결하기가 어려웠던 것 같습니다.

 

 

결과는 11솔이고 안정적으로 1등했습니다.

2023 summer때 프리즈 이전까지 좋은 퍼포먼스를 내다가 프리즈 이후에 어려운 문제들을 하나도 못풀어서 1등을 못했던 기억이 있는데, 이번에는 프리즈 이후에도 어려운 문제들을 꽤 풀었다는 게 좋은 신호입니다. 사실 이 문제는 저희 팀이 꾸준하게 가져왔던 문제이고 앞으로도 계속 해결해 나가야 될 문제인 것 같습니다.

 

베트남 가서도 그냥 욕심내지 말고 재밌게 하고 오자고 팀원들이랑 얘기했습니다. 그치만 결과도 좋으면 더 좋겠죠?

 

 

다른 연대팀들도 스코어보드에 많이 올라와있습니다.

 

4위의 입대 전 라스트댄스 (dlguq0107, dhlee1031, starwh03) 팀은 22학번 팀으로, 영재고 출신들이라서 그런지 22학번인데도 실력이 정말 좋습니다. 이번에도 좋은 결과를 냈고 아마 군대 다녀오면 이 팀이 연대의 다음 세대가 아닐까라고 생각합니다.

 

5위의 진짜1등하러왔습니다 (plast, sk091204091204, dreami63)팀은 cookie팀으로, 저희보다 높은 등수로 아시아 슈퍼리저널에 가는 팀입니다. 진짜 잘하는 팀인데 이번에는 뭔가 사정이 있어서 대회 참여도 정상적으로 못했던 것 같고 하지만 ICPC와 CF에서는 굉장히 무서운 팀입니다. 

 

6위의 돈비고고 (changhw, wlgh7407, matthew16) 팀은 첫 팀 결성이고 그냥 경험을 위해서 나온 팀인데도 불구하고 굉장히 훌륭한 퍼포먼스를 보여줬습니다. 그리고 wlgh7407과 matthew16은 시작한지 정말 얼마 안됐는데도 잠재력이 엄청난 것 같습니다. 뉴페이스 잘하는 팀이 하나 생긴 것 같습니다.

 

7위의 가지오이당근 (kiwiyou, yup0927, ez_code) 팀은 꾸준히 잘해왔던 팀이고, 역시 센트로이드에서 폭사했다고 합니다. 하지만 꾸준히 잘하는 팀이고 역시 준수한 성적으로 마무리했습니다.

 

14위의 아무생각이안들음 (nflight11, blackstar0223, tngtied) 팀은 nflight11님이 대회 찍먹해보고 싶은 분들을 모아서 팀을 결성했고, 그럼에도 불구하고 좋은 성적을 거둬 학교별 특별상을 수상하고 마무리했습니다.

 

 

수상하신 분들 모두 축하드립니다. 그리고 신촌 운영진 분들도 모두 고생 많으셨습니다~~