[대회] 2022 SUAPC Winter 후기

지난 2월 26일에 2022 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2022 Winter)에 참가하였다. 

문제 및 해설은 아래 링크에서 확인할 수 있다.

https://www.acmicpc.net/board/view/85025

 

팀 명은 "서강베스트"이다.

우리 팀은 wbcho0504(원빈이), duram21(재혁이), dong_gas(나)로 이루어져 있다. 지금 보니 셋 다 나이가 다 다르다. 00(나), 01(원빈), 02(재혁)년생으로 이루어진 팀이다.

 

우리는 2위(Kakao Tech상)로 대회를 마무리했다. 상금 30만 원을 받았다!

스코어보드를 보면 특이한데, 1등과 15등의 솔브 수가 같다ㅋㅋ

그래서 패널티로 등수가 결정되었다..

 

대회가 끝나기 2시간 전에 프리즈가 되는데, 그때 이미 6팀이 7솔을 달성했었다.

근데 결국 끝날 때까지 8솔이 나오지 않은 걸 보면 8솔의 벽이 매우 높았던 것 같다.

반면 7솔까지는 꽤나 평이한 난이도였던 듯..? 아님 말고..

 

우리팀은 wbcho0504가 H를 4시간 넘게 붙잡고 있었는데, 아쉽게 풀어내지 못했다. 자책을 많이 하던데, 충분히 잘했다고 생각한다! 그리고 이 문제를 풀 수 없었던 사연이 좀 있다. 타임라인에서 확인하세요!

 

난이도를 보면 확실히 8솔을 하기는 쉽지 않아 보인다. open contest에서도 7솔에 큰 벽이 세워져 있더라.

22 SUAPC Winter open contest 스코어보드

혼자서 11솔, 9솔 하시는 분들 정말 대단한 것 같다...

 

 

---

서강베스트 이모저모

(1) 팀 이름

팀 명은 "서강베스트"이다. raararaara선배가 지어주었다. 아직도 유래에 대해서는 잘 모르지만 우리 팀원 모두가 존경하는 선배이기 때문에 하라는 대로 했다! 팀 명에 대한 설명은 raararaara선배의 블로그에 올라온다고 하네요... 궁금하다!

 

 

(2) 팀 결성

지난여름에는 "협곡에서는 플래티넘인 내가 코딩 실력은 실버!?"라는 팀으로 SUAPC에 참가했었다. 학교에 아는 사람이 딱히 없어서 학회에 팀빌딩을 신청했고, 학회에서 만들어준 팀이다. 당시에는 셋 다 그리 열심히 하는 팀이 아니었고, 좋은 경험을 하자는 의미에서 나갔었다. 대회 후에는 팀원들이 PS를 많이 하지 않아서 자연스레 팀이 해체되었다.

 

그러던 와중에 "서강베스트"팀이 만들어졌다. 

작년 2학기에 랩실에 있었는데, 원빈이랑 재혁이가 SUAPC 같은 팀으로 나간다고 하더라. 그래서 껴달라 했더니 바로 껴줬다 ㄷㄷ. 그렇게 팀이 만들어졌다. 

 

21 SUAPC Summer 우승자이자 코드포스 오렌지에 빛나는 wbcho0504가 있어서 매우 든든했고, 나와 동등하거나 그 이상의 실력을 가진 친한 동생인 두람이가 있어서 구성이 마음에 들었다. 셋이 꽤나 친분이 있어서 분위기가 좋았다.

 

 

(3) 팀 전략

초반에는 나랑 두람이가 4문제씩 보고, wbcho0504가 5문제를 보는 식으로 하기로 했다.

그렇게 각자 풀 수 있는 문제들(브실골)은 각자 풀기로 했다.

그 후에는 wbcho0504가 어려운 문제를 잡고, 나랑 두람이는 골, 플난이도의 문제를 같이 풀기로 했다.

대회 때도 딱 이렇게 진행된 것 같다.

 

 

(4) 팀 연습

팀 연습은 2월부터 했다.

학회에서 매주 수요일 진행되는 연습셋을 이용했다. (내가 셋을 고르고 진행하는 연습셋이다.)

팀 연습은 3번 했고 학교에서 대면으로 진행했다.

 

 

(5) 코로나

대회 전날 두람이가 자가격리를 해야 한다더라. 결국 나랑 원빈이는 K512에서 보고, 재혁이는 집에서 봤다.

ㅠㅠㅠㅠㅠ

아무래도 두람이는 비대면으로 하니까 소통하는 게 쉽지 않았다. 아쉬웠다. ㅠㅠ

 

 

---

타임라인

재혁이가 A, B, C, D

내가 E, F, G, H

원빈이가 I, J, K, L, M

을 보면서 대회를 시작하였다.

 

[0:05] C AC

브론즈2티어의 0솔 방지 문제였다.

재혁이가 바로 풀어주었다.

 

 

[0:15] K AC

골드5문제였다.

원빈이가 바로 풀었다. 굿굿.

 

 

[0:19] G AC

내가 E, F, G, H를 읽은 상태였다.

팀원들이 한 문제씩 해결한 상태인데, 나는 하나도 못 풀고 있어서 조금 마음이 급해졌다.

근데 E, F가 다이아, H가 플레티넘1 문제이니 그럴 만도 했다 ㅋㅋㅋ

암튼 네 개를 한 번씩 다 읽어보니 그나마 G가 풀만하다고 생각했고, 스코어보드에 G를 푼 팀이 조금 보여서 G를 고민하기 시작했다. 그런데 생각보다 잘 보이지 않더라 ㅠㅠ 그때 딱 원빈이가 K번을 맞춘 상태여서 내가 붙잡았다. 문제를 빠르게 요약해줬고, 원빈이가 바로 알겠다며 나보고 다른 거 보라고 했다. 역시 워버쵸! 4분 만에 맞춰주었다!

 

근데 다른 거 보면서 생각난 게, 중급반에서 다룬 counting 하는 테크닉을 사용하면 되는 문제였다. 당시에 마음이 급해서 잘 보이지 않았던 것 같다.

 

- 원빈이는 이 문제를 풀고 H로 넘어갔다.

- 나는 세그문제로 보이는 F로 넘어갔다.

 

 

[0:25] A AC

재혁이가 맞춰주었다.

재혁이가 초반에 되게 빨리빨리 잘 풀더라. 고수다.

실버1 정도의 그래프 탐색 문제였나 보다.

 

- 재혁이는 이 문제를 풀고 푼 팀이 조금 있는 J번으로 넘어간 듯하다.

 

 

[0:36] L AC

원빈이에게 G를 맡기고, F를 조금 다시 봤는데 여전히 어려웠다. 그 와중에 원빈이가 G를 4분 컷 내고 다른 거 보라고 하더라. 그래서 그때부터 푼 팀이 조금 있는 L번을 보기 시작했다.

조금 보다 보니까 10의 배수만 아니면 무조건 이길 것 같다는 생각이 들었다. 그래서 원빈이한테 맞는 것 같은데 증명은 잘 못하겠다고 했더니 걍 내보라고 하더라. 근데 불안해서 혼자 조금 더 고민해보았다. 그러다가 무조건 맞을 것 같다는 생각이 들어서 제출했더니 맞았다. 

 

골드 하위 애드 혹 문제였다. 그래도 나는 대회 때 골드 상위는 될 줄 알았다. 찾기는 쉬워도 증명(?)하기가 쉽지 않다고 생각했는데... 암튼 풀었다.

 

- 나는 트리문제로 보이는 D로 넘어갔다. 이때, 상위 팀들이 푼 문제 중 재혁이가 잡고 있는 J 외에는 푼 팀이 없어서 어떤 걸 풀지 골라야 했다.

 

 

[1:19] D WA

트리에서 가장 큰 Y모양의 그래프를 찾아야 한다. 그래서 문제 제목도 Y였다 ㅋㅋ

일단 보자마자 트리의 지름은 무조건 포함되어야 한다는 것을 알았다.

그 이후에는 트리의 지름에서 뻗어나가는 가지(?) 중 가장 긴 가지를 찾으면 답이 된다는 사실을 알게 되었고 구현에 들어갔다.

DFS 2번을 통해 트리의 지름을 구하였고, set에 트리의 지름에 속하는 노드들을 넣어주었다.

그 후에 트리의 지름에 속해있는 노드들에서 뻗어나가는 가지(?)의 길이를 dfs로 각각 탐색해주었다.

최악의 경우에도 DFS를 3번만 돌기 때문에 충분히 통과할 것 같았고 제출하였는데 틀렸다.

 

역시 아직 안 풀린 문제는 어려운 건가? 라는 생각을 하였고, 반례를 찾기 시작했다.

 

 

[1:36] H WA

원빈이가 한 번 내봐도 되냐고 해서 당연히 된다고 했다. 아쉽게 WA

그래도 이때 1등 그룹인 상태였고, 나와 원빈이 재혁이 모두 각자 잡고 있는 문제의 풀이가 나와서 예감이 좋았다.

이때, 재혁이가 이런 카톡을 보냈었다. 

 

 

[1:37] J AC

이상한 걸 찾은 재혁이가 바로 J를 맞춰주었다!!

후기 쓰면서 느끼는 건데 재혁이가 이날 진짜 잘 풀었다.

꽤나 까다로운 골드3 포함배제 문제이다.

 

 

[1:38] D AC (First Solve)

아까 내가 틀린 이후로 반례를 찾다가 그냥 구현 실수였던 것을 발견했고 바로 고쳐서 냈더니 맞았다.

이때, 잠깐이지만 우리 팀만 7솔로 단독 1위였던 걸로 기억한다. 막 신나서 좋아했다. 심지어 내가 퍼솔을 하다니! 정말 행복했다. 몇 분 뒤, 1등은 뺏겼다 ㅠㅠ

 

당시에 풀고 나서 팀원들한테 빈집털이라고 했던 기억이 있다. 이 문제 쉬운데 안 풀려있어서 다들 못 푼 것 같다고 했었는데 그게 아니었다. 골드 정도의 난이도라 생각했는데, 대회 후에 플래티넘V로 난이도가 매겨졌더라.

 

- 나와 재혁이는 원빈이가 풀고 있는 H를 제외하면 F와 I가 그나마 풀만하다고 느껴서 그 두 문제로 넘어갔다.

 

 

[~ 5:00] H 6WA 8TLE, I 5WA

여기서부터는 AC가 없기 때문에 문제별로 쓰겠습니다.

 

H.

1:56에 원빈이가 이제 맞은 것 같다면서 제출했는데 43%에서 TLE가 났다.

그리고 끝날 때까지 43%의 벽은 결국 넘지 못했다.ㅠㅠ

 

F & I.

F는 세그인 것 같은데 나랑 두람이가 결국 풀지 못했다.

I는 뭔가 풀 수 있을 것 같았다. 뭔가 풀이를 찾은 것 같아서 원빈이한테 피보나치를 nlogn에 구해줄 수 있냐고 물어보기도 했었는데, 그냥 풀이 자체를 찾지 못했다.

 

사실 나랑 두람이는 2시간 반 정도 남았을 때, 더 이상 풀 수 있는 문제가 없음을 직감했다.

다른 팀들도 그랬다고 카더라...

 

 

 

 

 

 

 

멘탈이 나간 우리는 몇 번의 개그 제출을 하며 대회를 마무리했다.

스코어보드 스트리밍에서 lky님이 막 언급해주셔서 부끄러웠다 ㅋㅋ

외않되!!!!!!!!!!!!

H에 대한 얘기를 조금 하자면 원빈이는 호프크로프트 이분매칭 알고리즘을 이용하여 풀었다고 한다.

원빈이가 사용하던 호프크로프트 코드는 유명한 블로그의 코드였는데, 그 블로그의 코드가 잘못되어 있었다..... 근데 또 다른 제한이 비슷한 호프크로프트 문제는 그 이상한 코드로 뚫려서 코드가 이상하다고는 절대 생각을 하지 못했던 것이다. ㅠㅠ

 

---

 

마무리

PS를 시작하고 처음으로 수상을 했다. 원빈이와 두람이에게 매우 고맙다. 

원빈이는 역시나 잘했고, 두람이는 내 생각보다 훨 잘 풀어서 되게 놀랐다. 역시 고수들이다.

아 그리고 스코어보드 이끌어간 건 처음이라 뭔가 신기했다. 맨날 따라 풀기만 하다가..

 

 

그리고 요즘 Sogang ICPC Team 학회 일로 바쁜데, 서강대학교의 성적이 매우 좋아서 정말 행복했다. 1, 2, 4, 5, 6, 9, 11, 12, 13, 14등이 모두 서강대다!

우승은 rebro님이 계신 서강대학교 "5시간 집중하기 힘든 나이"팀이 했다. 역시 잘하시더라! 축하드립니다!

 

 

학회의 겨울방학 연습셋을 준비하고 진행하는 것이 힘들었는데, 우리 학회 사람들이 좋은 성적을 얻어서 뿌듯했다. 특히, 꾸준히 참여해주신 팀들은 모두 7솔을 하셔서 괜히 뿌듯했다 ㅎㅎ 물론 그분들이 잘한 거지만!

 

 

원빈이가 곧 군대를 가기 때문에 "서강베스트"팀의 마지막 대회였다.

열심히 문제를 풀어서 다음 대회들에서도 좋은 성적을 얻고 싶다.

 

 

좋은 경험 하게 해주신 운영진, 출제진, 검수진분들 모두 감사합니다!

저희 팀 응원해주신 분들도 모두 감사합니다 :)