SUAPC 2021 Summer 후기
SUAPC
신촌지역 대학교 프로그래밍 동아리 연합 대회인 SUAPC에 처음으로 참여해봤다.
한 주 전에 했던 Camp Contest에서 2등을 했기 때문에, SUAPC에서도 좋은 결과를 얻을 수 있지 않을까 기대했다.
그런데 팀원을 모으는 것부터가 난관이었다.
컴과에 아는 사람은 하나도 없었고, 동아리 톡방이나 슬랙 등에 활발하게 팀원을 모집하는 사람도 없었기 때문이다.
다행히 동아리 회장님께서 올려주신 구글 시트를 통해 surface_03님과 컨택을 했고, 이후 portal3046님까지 섭외해 팀을 이루게 되었다.
팀명은 portal3046님의 아이디어로 “Order of One“으로 지었다.
나는 프로젝트 준비 때문에 너무 바빴고, 다른 분들도 별말씀 없으셔서 팀연습은 한 번도 하지 않고 대회 당일에 처음 만났다.
SUAPC에 참여하는 팀명단이 올라왔을 때, 너무 쟁쟁한 분들이 많으셔서 살짝 위축됐다.
이래저래 닉네임을 많이 봤던 분들도 계셨고, 코포 오렌지분들도 계셨다.
대회 당시, 나는 다이아5 / 회색, surface_03님은 플레2 / 블루, portal3046님은 골드2 / 블루였다.
그래서 5등 안에만 들면 좋겠다 생각하면서도, Camp Contest에서 우리 팀 세명 모두 성적이 우수했기 때문에 더 좋은 결과를 얻을거란 희망을 버리지 못했다.
토요일 11시쯤 신촌에서 만나 점심을 먹고, 대관한 스터디룸에서 문제를 풀기 시작했다.
타임라인
portal3046님이 A, D, G, J를, surface_03님이 B, E, H, K를, 나머지를 내가 보기로 했다.
00:07 D (반짝반짝 2) : AC
무슨 일이 있던 건진 모르겠지만 surface_03님께서 D를 잡았고, 바로 AC를 받으며 퍼솔을 기록했다.
00:09 F (Flat Earth) : 1WA
너무 조급했던 탓인지 문제도 제대로 안읽고 제출을 해버렸다.
외곽으로부터 Manhattan 거리가 K 이하인 점들의 개수를 세서 제출했고, 당연히 틀렸다.
00:18 A (휴먼 파이프라인) : AC
portal3046님께서 제출을 했고, 바로 AC를 받았다.
00:18 F (Flat Earth) : AC
A번 제출과 거의 동시에, 내가 아까 틀린 부분을 고쳐 제출했다.
3솔을 하며 3등 이내로 랭크인 됐던 것으로 기억한다.
00:40 C (조각 체스판) : AC
‘각 칸을 0과 1로 변환 후 같은 숫자로 이뤄진 정사각형 개수만 세면 되겠다~’고 생각하던 차에 surface_03님께서 풀 수 있을 것 같다 하고 한 번에 AC를 받으셨다.
01:13 E (문자열 조작의 달인) : 1WA
portal3046님께서 풀고 제출했는데 아쉽게 틀렸다.
01:28 H (재활용 캠페인) : 1WA $ \rightarrow $ AC
나랑 surface_03님이랑 같이 잡았던 문제이다.
$ x $는 모두 카운트해 주고, $ \frac{x}{2} $ 이상인 것들은 제일 작은 것들과 매칭 시켜 카운트해 준다는 전략까진 동일했다.
surface_03님께서 $ \frac{x}{2} $ 이하인 것들도 동일하게 하면 되지 않냐고 했는데, 그렇게 하면 틀릴 것 같아서 반례를 쥐어 짜냈다.
$ x = 100 $, [3, 5, 10, 20, 30] 같은 반례가 존재했기 때문에, 나는 제일 작은 것을 제일 큰 것이랑 더했을 때 $ \frac{x}{2} $ 미만이면 제일 작은 두 개를 매칭 시키는 전략을 구상했다.
두 방법을 살짝 절충해, lower_bound를 이용해 합해서 $ \frac{x}{2} $ 이상인 것들을 모두 뽑아내고, 남은 것들의 개수를 3으로 나눈 몫을 더해주는 방식으로 결론지었다.
내가 이분 탐색을 혐오하기 때문에, 구현을 부탁했는데 한 번 실수했다가 고치고 바로 AC를 받아냈다.
02:05 E (문자열 조작의 달인) : 1WA
세 명 모두 이 문제에 달라붙었는데, 유일하게 나 혼자 파이썬을 쓰고 있어서 overflow가 나지 않는 이점을 활용해 문제를 쉽게 풀어보려 했다.
무식하게 dp table에 26 ** 300까지 때려 박았는데, 애초에 로직이 잘못돼서 틀렸다.
02:22 E (문자열 조작의 달인) : AC
두 분께서 솔루션을 냈고, surface_03님이 구현해 AC를 받았다.
03:10 G (기지국 업그레이드) : AC
이 문제 저 문제 보며 방황하다가 G를 잡았다.
맨 처음엔 2-sat인 줄 알고, 업그레이드하는 것을 True, 제거하는 것을 False로 생각하며 접근했다.
기존에 커버된 부분들을 모두 커버해야 하므로 일단 모든 기지국을 업그레이드하고 하나씩 제거하는 식으로 접근했다.
전파 간섭이 일어나는 경우 둘 중 하나를 무조건 제거해야 하는데, H가 더 작은 것을 제거하는 게 좋을 것 같았다.
간단한 증명을 통해 제거되지 않은 기지국이 제거된 기지국의 통신 범위를 모두 커버한다는 것을 알 수 있었다.
결국 그리디하게 H가 큰 것부터 업그레이드해가면서, 전파 간섭이 일어나는 범위를 저장하고, 다음 기지국이 그 범위 내에 존재하는지만 확인하면 된다.
그런데 이 풀이의 구현이 내가 굉장히 싫어하는 종류일 것 같아서 또 surface_03님께 구현을 부탁드렸고, 한 번에 맞으셨다.
03:51 K (수요응답형 버스) : 1WA $ \rightarrow $ AC
스코어보드를 보니 다들 K를 풀었길래 모두 머리를 맞대고 꼭 풀자고 결심했다.
나는 계속 북서풍 문제가 떠올라 스위핑 + 세그트리로 접근했고, 다른 분들은 위상 정렬, 플로우 등 다양하게 접근했다.
그러다가 내가 그리디한 솔루션을 생각해냈는데, 이 풀이 또한 G의 풀이랑 되게 비슷한 게 내가 아주 싫어하는 종류였다.
그래서 surface_03님께 또 구현을 부탁했고, 한 번 틀린 후 AC를 받으셨다.
8솔로 패널티가 더 적었던 1, 2위와 동률이었고, 곧 스코어보드가 프리징 됐다.
1등을 하려면 한 문제 이상 더 풀어야 하는 상황이었기 때문에, portal3046님께선 I (브런치북), surface_03님께선 L (다꾸), 나는 J (사이클)을 맡았다.
나는 J를 풀며, 속으로 ‘아 왜 플로우 문제 안 나와’ 이랬는데 알고 보니 이 문제가 플로우 문제였다. ㅋㅋㅋㅋㅋ
그런데 min-cost max-flow 문제는 한 번도 풀어본 적 없어서, 그나마 덜 아쉬웠다.
surface_03님께선 L이 금광 세그트리를 이용해, 꼭짓점을 기준으로 여러 케이스를 나눠 푸는 것까진 알아챘지만 아쉽게도 시간이 충분치 못했다.
portal3046님께선 얼추 문제를 푸시는 듯했지만, 아쉽게도 다 푸시진 못했다.
8 AC, 5 WA. 엄청나게 높은 정답률을 보였다.
이 중에 내가 제출한 게 1 AC, 2 WA라니 엄청나게 창피하다.
그것도 제일 쉬운 문제였다.
핑계긴 하지만 뭔가 이날 코딩이 잘 안됐다.
다른 문제들을 푸는 데 기여했다지만, 입으로만 나불거리고 구현은 맡겨서 죄송한 마음뿐이다.
두 번째 핑계긴 한데 이번 대회 문제 스타일들이 내가 약한 부분이었다.
배운 범위 내의 2-sat, flow 문제가 나오길 내심 기대했는데 하필 모르는 MCMF가 나와버렸다.
그리고 전체적으로 greedy랑 dp가 많이 나온 것 같다.
다음 SUAPC 땐 이런 부족한 부분들을 보완해야 할 것 같다.
결과
그렇게 8솔을 하고, 스코어보드 오픈 때 큰 변화 없이 그대로 3등을 기록했다.
Camp Contest의 내 스코어보드처럼 빨간 칸이 없는 게 아주 인상적이다.
8솔 동률이라 살짝 아쉽기도 하지만, 1, 2등 팀을 이길 엄두도 나지 않고, 4등도 8솔이라 3등에 아주 만족한다.
별일 없으면 이 팀 그대로 다음 SUAPC도 나가기로 했고, 그 땐 팀연습도 왕창해서 더 높은 성적을 노려볼 예정이다.
7, 8월 동안 엄청 많은 시간을 투자했던 ICPC Sinchon이 이렇게 마무리되어 되게 시원섭섭했다.
두 달간 정말 많은 것을 배웠고, 이렇게 팀으로 대회에 나가는 것도 진귀한 경험이었다.
이 캠프를 기획하고 운영하는 데 고생하신 모든 분들께 감사하다.
Leave a comment