UCPC 2022 본선 후기

24 Jul 2022

UCPC 2022

원래는 알로하 부회장님, 다른 학술부원님이랑 같이 나가기로 했는데, 부회장님이 몰입캠프를 가버리시는 바람에 팀이 분해됐다. 그 뒤로 그냥 가만히 있다가 UCPC 팀 어떡하지?? 이런 생각이 들 때, 연진이 누나(yjinpark)가 같이 팀하자고 연락을 해줬다. 두명이서 다른 한명을 더 찾으려고 했는데, 둘 다 못구해서 내가 그냥 친구인 서진이(sj1226m)한테 같이 나가자고 했다. 너무 고맙게도 무슨 대회인지 잘 모르는데도 불구하구 같이 나가준다고 해서 그렇게 UCPC팀이 꾸려졌다.

어찌저찌 예선을 마무리하고 운이 좋게도 본선에 진출하게 됐다. 난 오프라인 대회가 그냥 처음이었던지라 너무 설렜다. 본선에서 뭐라도 풀어보겠다고 급하게 Mo’s랑 FFT같은거 열심히 풀어봤고(사실 의미는 없었..다..ㅋㅋ) 요상한 2차원 짜리 FFT도 풀었다. FFT가 자주 나왔길래 그걸 열심히 팠는데 본선엔 내가 못 풀 난이도로 나와서 의미가 없었던..ㅎ (심지어 본선 문제 하나 보자마자 NTT 쓰는거인걸 알았는데 알아도 못풀 난이도였음)

근데 왜 노란색 옷….??

본선 대회 장소에 도착하니까 노란색 옷을 입고 있는 사람들이 한가득 있었다. 저게 본선 티셔츠인걸 부정하고 싶었지만, 어림없지 ㅋㅋ 그게 우리가 입어야할 티셔츠였다. 사이즈가 좀 작게 나와서 끼는 느낌이 있었지만 뭐 그래도 대회 온 느낌도 나고 좋았다. 책상 위에 놓인 봉투 뜯어보니까 solved.ac 별조각 쿠폰이랑 한별이 스티커가 있었다(둘 다 랜덤).

생각치도 못한 게 들어있으니까 좀 웃기고 어이없긴 했다. 등록하고 좀 앉아 있으니까 갑자기 11시 5분에 대회가 시작된다고 했다. 사전 유의사항 그런거 알려주고 시작할 줄 알았는데 그런거 없이 그냥 자연스럽게 진행하라고 해서 좀 당황스러웠다. 11시 ~ 16시가 진짜 대회 시간인줄은 상상도 못하고 있었는데, 그렇게 5시간동안의 대회가 시작됐다.

왜 쉽지?

누나가 문제 읽으면서 이거 쉬운데? 하면서 막 풀어냈다. 작년 본선 난이도를 생각하고 와서.. 3문제 푸는게 사실 목표였는데 의외로 한문제가 빨리 풀려서 신기했다. 그러다가 누나가 또 이거 그냥 그리디인데? 하더니 막 풀어와줬다. 갑자기 2솔브가 되더니 20등대가 되서 “오 이게 뭐지? 이게 선배미..?” 이러고 있었다. 나는 J번 보고 풀이 한 번 잘못 구상해서 코드 한 번 갈아엎고 제대로 풀이 짜와서 AC 받았다. 그때가 대회 시작 1시간정도 되는 시점이었다. 한 시간만에 목표 달성하고 재밌다~~ 이러고 그 뒤로 뭔가 쭉 막혔다.

어림없지 바로 하드모드

서진이가 K번을 읽고 이거 풀만해보인다면서 나한테 문제지를 넘겨줬다. 엄청 열심히 써놓구 설명도 해주길래 할만해보이네~ 싶어서 조금 읽다가 감이 안잡혀서 난 다른 문제를 잡았다. 그리구 K번은 연진이 누나가 보고 나는 F번을 봤다. K번을 본 누나가 뭔가 복잡해보이는 풀이를 보여주더니 그걸 계속 풀고 보여주고 반복했다 ㅋㅋㅋ. F번을 읽는데 N도 의미심장하게 500,000으로 엄청 크고 약간 그리디스럽게 풀리지 않을까 싶어서 서진이랑 같이 문제를 봤다. 어쩌다 보니 문제지 자체를 넘겨주고 나는 D번을 풀려고 봤다. 누가봐도 레이지 세그 문제라서 어떻게 잘 하면 풀리지 않을까 하고 수식 정리를 시도했다. 잘 줄여봐도 뭔가 가중치가 앞에 붙는채로 레이지하게 업데이트해야하는 풀이밖에 안 떠올랐다. 가중치가 앞에 붙어서 lazy prop 자체가 그냥 안되서 멍 때리고 있었더니, 서진이가 엄청 그럴듯한 F번 풀이를 가져와서 설명해줬다.

앞에서부터 보면서 카드를 매칭시키는데, 이미 쓴 카드가 나오면 현재까지 진행한 카운트와 \(\scriptsize \lceil \frac{K}{2} \rceil\)을 비교해서, 카운트가 크거나 같으면 지금 들고 있는 카드를 모두 버리고 가져온 셈 치는 풀이였다. 두 장씩 다 버린다고 치면, \(\scriptsize \lceil \frac{K}{2} \rceil\)번 버리면 카드가 다 비니까, 중복된 카드를 먹기 위해서 그냥 버린걸로 생각하는 풀이였다.

엄청 그럴듯 해 보이지 않나요? 난 진짜 맞는 풀이 같아서 조금 더 나은 풀이를 만들어 냈구 (실제로 카드를 버리는게 아니라 set을 활용해서 set에 넣는 걸로 중복 체크) 시간 복잡도도 \(\scriptsize O(NlogK)\)로 진짜 될 것만 같았다.

배고프길래 서브웨이 준거 먹고 코드 짜기로 했다. 그 와중에 누나가 진짜 세상 열심히 K번 코드를 짜고 고치고 하길래 구경했는데, 뭔가 잘 안되는 것 같았다. 밥 다먹구 노트북 가져가서 서진이가 내 코드 훈수두는 식으로 코드를 같이 짰다 ㅋㅋㅋㅋ. 이런 저런 구현 실수 때문에 조금 오래 걸려서 코드가 만들어졌는데, 예제도 잘 나오고 뭔가 될 것만 같은 기분이 들어서 떨리는 마음으로 제출했다.

1퍼 돌아가자마자 터졌다. 이때가 제일 아쉬웠다 ㅠㅜ. 잘 생각해보니 몬스터가 안나오는 턴이 좀 문제가 될 수 있었고, 그걸 살짝 억지로 고쳐보는 로직을 추가해서 제출해도 역시나 WA를 받았다. 이때가 거의 3~4시간이 흐른 시점이었고, 나는 다시 D번을 보고 누나는 여전히 K번과의 사투를 하고 있었다.

K번 풀이는 뭘까?

D번을 보다가 도저히 식 정리가 안되서 포기하니, 서진이가 G번을 들고와서 이거 쉬워보인다구 했다. 뭔가 나름대로 식도 적혀있길래 문제를 읽고 들어줬다. 그때까지만 해도 G번 푼 팀이 거의 없어서 나는 어려운 문제인게 딱 감이 왔는데.. 혹시? 하는 생각으로 풀이를 들었다. 둘이서 보다가 순서가 있다는 사실을 놓쳐서 쉬운 문제인것처럼 보였을 뿐 아쉽게도 ㅠㅠㅠ 어려운 문제가 맞았다. 그래서, 그냥 K번을 보기로 했다. 이왕 본선왔는데 4솔은 해야할 거 같아서… 여튼 누나가 풀이를 설명해주는걸 딱 듣고 있었는데 언젠가부터 살짝 흐름도 놓치고 약간 풀이가 장황해지길래 뭔가 정해가 아닌 것 같다는 생각을 했다.

그래서, 나도 문제를 보고 다른 풀이를 떠올려봤다. 나는 a가 b를 이기는 걸 방향 그래프로 만들어서 트리 2개를 만들고 그걸 잘 보고.. 어떻게하면 원래 트리 모양이 나올 지를 생각했다. 왠지 그냥 트리 높이랑 자식 개수로 잘 합치면 답이 나올 것 같아서 누나한테 이걸로 풀어보는거 어떰? 하고 제안을 했는데 누나가 “나 못믿음?” 시전하길래 10분 정도 더 기다려줬다. 누나가 열심히 완성한 코드가 WA를 받길래 얼른 내 풀이를 실행으로 옮겼다. 대회 종료 30분 남은 시점이라서 엄청 급하게 짰는데, 어떻게 예제 답을 낼 수 있었고 제출을 하기 전에 누나가 만든 테케를 넣어보니 답이 안나왔다. 너무 아쉬웠다. 끝나기 전까지 고쳤지만 결국엔 WA만 더 쌓고 끝났다. 아래는 대회 종료 직후 슬픈 내 WA코드..

나중에 해설 들어보니 누나 풀이가 정해였고.. 내가 짠 풀이는 소개해주지도 않았다. 누나 약간 옆에서 억울해했음ㅋㅋㅋㅋ 쏘리.. 다른 팀 얘기 들어보니까 나랑 비슷하게 트리 어찌저찌 잘 합치는 풀이로 AC받았다는 거 같은데 왜 나는 안됨 ㅋㅋ

끝나버린 첫 본선

그렇게 본선이 끝났다. 그 이후로 후원사 홍보 세션, 수상 세션이 있었고.. 피곤했던 우리팀은 엎드려서 자다가 박수치고 자다가 박수치고 ㅋㅋㅋㅋㅋ 그러다가 사진 찍으려고 앞에 나갔다가 사람이 너무 많아서 뒤로 잠시 갔는데 그 사이에 벌써 사진을 찍었길래 그대로 퇴장했다. 티셔츠가 볼만했으면 같이 사진이라도 찍을 걸 그랬는데.. 티셔츠가 너무 노란색에 안 이뻐서 그냥 벗고 그대로 집으로 갔다.

본선에서 얻은건.. 본선 티셔츠, 후원사 티셔츠 (좋은 잠옷)랑 몰로코 굿즈였다. 개인적으로 몰로코 굿즈가 좀 이쁜 것 같다. 파란색 노트 좀 힙해서 좋은듯. 여튼, 5시간 동안 대회해본 것도 처음이고 오프라인 대회도 처음이라 재밌었다. 비록 3솔로 끝났지만, 다음번엔 더 나은 결과를 기대해볼 수 있지 않을까..ㅎ?

연습이랑 예선, 본선까지 멀리서부터 계속 와준 문서진씨 너무 고마웠고 덕분에 좋은 추억 쌓은 듯! 같이 팀하자고 해준 연진 누나도 짱 고맙고 사실 우리팀 버스기사였기에 너무 멋있었다 선배미 폭발 ㄹㅇ 두 사람 다 엄청 수고많았음!

재밌는 대회 운영해주신 UCPC 운영진분들 감사합니다!