SCSC Computer Programming Contest 후기

대회 전

2023년도 ICPC 서울 리저널 이후로 PS를 막 그렇게 하진 않았는데(24년도가 좀 많이 바빴던 것도 있음…), 소프트웨어 마에스트로에 합류하게 된 이후 많은 고수분들을 뵙게 되었고, 의욕이 조금 생겨 천천히 코드포스나 앳코더를 다시 잡게 되었다. 사실 업솔빙도 잘 안한다 그냥 레이팅이 바뀌는 절망과 쾌감의 도파민에 절여진건지… 이러니 실력이 오를리가 있나
SCSC는 소마 16기 동기 중에 운영진분이 계셔서, 홍보에 낚여 들어가 신청하게 되었다. 주변사람들에게 홍보도 할게요 했는데
안타깝게도 교내대회랑 일정이 겹치는 바람에… 학교에선 나 혼자 출전했던 것 같다. 교내대회는 출전도 해보고 수상도 해보고 출제도 해보고 씹고 뜯고 맛보고 다 했기도 하고, shake!도 몇 번 나가보기도 하고 그래서 그대로 SCSC에 나가기로 했다. 살면서 타 대학 갈 일이 얼마나 있겠는가? 그것도 서울대를
대회 전에 단체 메일을 받았는데 숨은 참조가 아니라서 출전자들을 볼 수 있다던가 작은 이슈들이 있던 것 같은데, 크게 신경은 안썼고 많은 고수들이 나오시는구나 하고 넘긴 것 같다.

대회 당일

요즘 수면 패턴이 망가져서 4-5시에 잠들고 12시에 일어나는 삶을 살고 있는데, 오프라인 대회니까 일찍 자야지 해놓고 또 4시에 잠들었다. 다행인건 전날엔 오후 4시에 일어났기 때문에 수면 시간 자체는 준수?했다.
8시 기상 후 10시 출발, 11시 좀 넘어서 서울대입구역에 도착했는데, 처음와본다고 들떴는지 캠퍼스까지 걸어가보겠다는 레전드 판단을 하게 된다… ㅋㅋ
많이 걸었다고 생각했는데 절반도 못왔고, 후회와 피로에 몸부림쳤다. 그냥 버스타고 갈걸… 대회 시작도 안했는데 벌써 체력 다 빠지고 졸리고 바람이 시원해서 망정이지 진짜 여름날씨였으면 그냥 바닥에 누웠을듯
캬 이걸 실제로 보는 날이 오다니
점심을 안 먹고 와서, 캠퍼스 내에 있는 버거운 버거를 갔다. 살면서 처음 들어보는 체인점이었는데 맘스터치 느낌 나서 괜찮게 먹었던 것 같다. 버거버거집에서 toycartoon님 파티랑 합류했는데, 아레나 파티라던가 그런 곳에서 몇 번 뵈었던 분이라 자연스럽게 합류할 수 있었다. 말 걸었는데 PS 하시는 분이 아니었다면? 정말 상상만 해도 너무 무섭다…
단체로 28동 건물까지 이동, 접수를 빠르게 하고 갤럭시 캠퍼스 이벤트에 참여하였다. 타로카드를 AI가 해석해주는 이벤트를 하길래 취업운을 좀 봐달라고 했는데, 사람들과 소통을 많이하는 직업이 좋을거라고… 간식이랑 부채를 받은 후 Div 2 강의실에 들어갔다.
근본 넘치는 2단 칠판, 우리 학교에선 수학과 강의실에서만 본 것 같은데… 칠판 옆에 와이파이 정보가 있어서 폰이랑 노트북 두개 다 접속시켜놨다.
근데 막 여러 문제가 있었는지, 대회가 10분 또 10분 연장되어서 2시 20분에 시작한다고 하더라. 등록 줄도 꽤나 길었었고, 계정 정보가 명찰 뒷면에 있었는데 종이가 빠져버리거나 하신 분들도 있었고, 늦으시는 분들도 있었고 해서 나름 괜찮았을지도 모르겠다. 로그인할 때는 좀 번거로웠다. 내가 대회 열었을 땐 이메일로 계정 정보를 보내서 그냥 복사하면 되었는데, 종이로 뽑는 대회는 비밀번호 치는게 좀 번거롭다…

대회 중

A. 주사위 피라미드

• 0:21 -1
  각 면이 보일 때의 최소/최댓값을 미리 계산해놓고, 각 층의 주사위가 몇 개의 면이 보이는지 계산하였다.
  바닥면까지 볼 수 있는 줄 알고 맨 밑면까지 예외처리하는 풀이를 짰다. 지문을 잘 읽어주세요…
  바닥면을 볼 수 없음을 깨닫고 빠르게 수정했는데, $N=1$을 $42$로 예외처리 해놓고 $35$로 수정하지 않아서 1틀… 진짜 뭐하는거지
• 0:23 AC
  개허접 모먼트 좀 아쉬웠다.

B. 물과 응애

• 0:37 -1
  지문이 너무 웃겼다. 문제를 슥 보고 스택이 먼저 떠올랐는데, 6짜리 예제만 봐도 아닌 것 같았고, 각 O 문자에 대해서 H의 $\{$왼쪽 개수, 오른쪽 개수$\}$ 가 달라야 하나? 라는 풀이로 접근해서 틀렸다.
• 0:39 -2
  예제는 나오는데… 위의 접근방법에서 조금 수정했고, 당연히 정해가 아니니 틀린다.
  -2를 받은 이후, 대충 9짜리와 12짜리 문자열을 계속 만들면서 반례가 있는지 찾아보았다. 6짜리를 기준으로 재귀적으로 감싸야 하나? 뭐 그런 생각을 했던 것 같다.
• 0:50 -3
  무지성 제출 멈춰
  여기서 좀 막혀서, 사람들이 그 다음으로 많이 푼 I. $K$-POP을 보고 오기로 했다.

I. $K$-POP

• 1:00 AC
  합이 가장 적은 두 곱은 $\sqrt{K}$에 가장 가까운 두 수니까, 그 두 수를 먼저 구했다. 이후 이진 트리를 만드는 것은 노드를 일렬로 내려가면서 배치한 다음 다시 올라오면서 적당히 붙여주면 끝. 솔직히 이게 B에 와야했다고 생각해요…

B. 물과 응애

• 1:03 -4
  이전 풀이에 미련을 버리지 못하고 한번 더 수정해서 틀렸다. 이렇게 해서 틀린 이후로 아예 풀이를 다시 생각하기로 했다.
• 1:15 AC
  O를 기준으로 보는 건 맞는데, 양 옆의 H의 개수만 보는게 아니라 O의 개수도 보는 것으로 풀이 방향을 틀었다. 내 왼쪽에 O가 한개도 없다면 내 왼쪽에 H는 적어도 하나 있어야 하고, 내 오른쪽에 O가 2개 있다면 내 오른쪽에 H가 적어도 3개 있어야 한다 뭐 이런 느낌으로, 모든 O에 대해 만족하면 되지 않을까? 라는 생각을 했다. 사실 증명은 잘 모르겠다; 맞았으니 잘 되나보죠 뭐
  이 풀이로 미스 없이 한번에 맞추고 기뻐서 감탄이 나올 뻔 했다.

F. Sorting Replay at Jane Street

• 2:06 -1
  문제를 읽고 이게 뭔 소린지 한참을 생각했다. 무슨 정렬이요?
  이해한 바로는 일단 $1$번 쿼리를 사용하면 이전까지의 정렬 시퀀스가 초기화된다. 어 그럼 마지막 $1$번 쿼리부터 보면 되겠네? 를 떠올렸고, 그럼 $1$번 쿼리가 없으면? 항상 한 개의 정렬 결과만 나오겠네?? 가 자동으로 떠올랐다.
  그럼 이제 $1$번 쿼리를 사용한 이후 나오는 $2$번 쿼리를 어떻게 처리할까 생각해야 했다. 어쨌든 구현이죠…
  우선, $1$번 쿼리를 사용하면 해당 열에 있는 $N$개의 수 중, 같은 수를 가진 배열들이 같은 그룹이 된다. 같은 그룹이 된다는 의미는, 그룹 내에서 순서가 지 맘대로 될 수 있다는 것이다.
  이후에 들어오는 $2$번 쿼리에 대해서, 해당 열에 있는 같은 수를 가진 배열들을 또 하위 그룹으로 나눈다. 마지막 $1$번 쿼리 이후는 전부 $2$번 쿼리이므로 이를 반복한다.
  모든 쿼리를 수행한 후, 각 그룹 $G_i$ 에 대하여,$\prod_{i=1}^{|G|} |G_i|!$ 가 정답
  이라는 풀이를 떠올렸고, 정해라는 확신을 갖고 구현에 들어갔다.
  구현을 너무 더럽게 해서 간략하게 설명하면, 초기에 {정렬 기준 수} 를 key로 가지는 map을 만들어 $1$번 쿼리에 대한 그룹을 만들고, 이후 각 $2$번 쿼리에 대해서 {이전 그룹 번호$\times$정렬 기준 수}를 key로 가지는 새로운 map을 만들었다. 두개를 곱한 이유는 같은 수를 기준으로 정렬하더라도 이전 정렬 결과에 따라 다를 수 있어서… 오버플로우가 나더라도 어차피 key값이니 고려 안해도 될 것 같다고 생각했다.
  예제가 잘 나오기에 즉시 제출하고 틀렸다.
• 2:10 -2
  맞는거 같은데 왜 틀리지? 를 보니 그룹 번호가 0부터 시작하기에 잘못 곱하면 겹칠 수 있었던 것. 제출하고 또 틀렸다.
• 2:12 -3
  진짜 오버플로우 문젠가?? 해결하기 위해서 좌표압축 테크닉을 써보려고 했는데 구현이 더러웠기에 추가할 엄두가 안났고, 변수명을 잘못 쓴 곳이 몇 군데 보여서 고치고 제출했지만 당연히 틀렸다.
• 2:25 AC
  곱한 수를 key로 하겠다는 미친 짓 대신에, key를 {정렬 기준 수, 이전 그룹 번호}의 pair로 관리하도록 변경하였다. 제출하고 제발 맞게 해달라고 싹싹 빌었는데 진짜 맞아서… 기뻐서 소리치고 싶었는데 참았다.
  
  기억상 F를 맞춘 직후 20등 중반이 되었던 것 같다.

처음엔 3시간 셋인줄 알고 30등 이내 되는거 아니야? 생각했는데 아직도 스코어보드 프리즈가 안걸렸길래… 이젠 대회 설명도 제대로 못읽는구나
사실 6등상도 30등까지인줄 알았다. 그래서 풀어야 한다는 마음가짐으로 G. 현대모비스 V2X 자율주행 2와 E. SCSC 문자열 놀이를 동시에 봤다. E는 식을 좀 건드려보니$X={S, C}$에 대해 $2^nX + 2^{n-1}X + … + X$ 꼴로 나타낼 수 있길래 진법 문제인가? 넘겨야겠다 하고 크게 생각해보지 않았고, G를 오래 잡았다. 근데 뭐 아쉬운거죠 안풀리는데 어떡해

대회 후

대회 자체가 20분 지연되어서 시작했기 때문에, 이후 일정은 시간에 쫓겨 하셨던 것 같다. 오픈콘은 50분이 미뤄졌다고 했나?
끝나자마자 E 솔브 기록이 있던 nflight11님께 가서 풀이를 물어보고, toycartoon님이나 주변에 앉으셨던 다른 분들 반응도 보고… 진짜 어려웠던 것 같다.
10분정도 쉬는 시간을 가진 후 현대모비스 후원기업 세션을 진행했고, 모비스 세션은 3년동안 계속 들었기에 크게 집중하진 않았던 것 같다. 좀 어수선하긴 했는데 운영진분들이 불을 끄니 정상화되었다.
이후, 뒷풀이 일정을 맞추기 위한 운영진분들의 기행이 벌어졌다. Div 1, 2, 3 합쳐서 문제가 20문제정도 되었던 것 같은데, 모든 문제의 풀이를 하는데 20분도 걸리지 않았던 것 같다. 한번에 슬라이드 6개를 넘기고 그러시던데 모두가 재밌어했던 것 같다. 뒷풀이 장소도 예약했을텐데 그럴수있죠 ㅇㅇ
이후 스코어보드 까기와 시상이 진행되었는데, Div 3에 꽤나 많은 분들이 불참하셔서… 운영진분들이 안타까워하셨다. 근데 Div 2 첫 핸들이 toycartoon: 저, 디비전은 3로 해달라고 말했잖아요! 여서 ㅋㅋ 너무 웃겼다.
캬
프리즈 전을 기준으로, 20등 중반에서 쭉 밀려서 34등에 멈춰 있었고, 내가 느끼기에도 4솔 너무 힘들었고 5솔은 미친듯이 어려웠기 때문에 그렇게 밀릴 거라 생각을 하지 않았다. 결국 두 단계 밀려 36등으로 마무리했다. Div 2에도 재밌는 핸들이 많았는데 스코어보드 한번 구경하는 것을 추천한다.
Div 1에서는 SNUPS첩자랑 SNUPS접자가 박빙의 승부를 하시던데 두 분 다 프리즈 전 맨 위에 계셨기 때문에 핸들이 보이자 마자 모두들 웃었던 것 같다. 스코어보드 오픈과 동시에 시상을 해서, Div 1까지 오픈이 끝나고 바로 대회 끝! 이었던 것 같다. 뒷풀이도 좀 가고싶었는데, 비온다는 소식을 듣기도 했고 집가려면 한시간 좀 넘게 걸리기도 하고 해서 빠르게 귀가했다.
이렇게 멀리까지 나와서 하는 오프라인 대회는 진짜 오랜만인 것 같은데, 최근에는 느껴보지 못했던 AC받을때의 쾌감과 도파민이라던가 온라인으로만 보던 사람들을 만난다던가 하는 것들이 정말 좋았던 것 같다. 그냥 너무 재밌잖아
교내대회 하는거 안도와주고 다른학교 대회 나가는게 좀 미안했는데, 뭐라도 타서 다행인 것 같다. 그치만 최근은 집보다 서울에 더 자주있는걸… 소마 프로젝트가 더 바빠지기 전에 뭔가 하나 참여해서 정말 좋은 경험이었다. 이젠 진짜로 소마에 집중해야 한다… E랑 G만 업솔빙할게요 빨리 문제 올려주세요
마지막으로, 좋은 대회 열어주신 서울대 SCSC 분들 정말 감사합니다. 외부인까지 받는게 진짜 쉽지 않을텐데 덕분에 재밌게 즐기다 갑니다. 참여하신 모든 분들도 수고하셨습니다.