2024 신촌지역 대학생 프로그래밍 동아리 연합 여름 대회에 참여했습니다.
팀 구성은 coconut99, changhw, wlgh7407 으로, 올해 ICPC까지 함께할 팀입니다.
wlgh7407과는 겨울 SUAPC에서 처음 팀을 꾸렸고, coconut99 형은 작년 연대 1/2위(SCC / Cookie) 팀에서 납치해왔습니다.
이번 SUAPC는 일본 여행 일정과 겹쳤기 때문에 나갈 생각이 없었습니다. 그래서 다른 두 팀원한테 아무나 한명 끼워서 나가라고 했는데, 마감 직전 마지막 팀연습날까지도 팀원을 못구하고 있길래 그냥 제 이름만 넣고 2인팀으로 나가기로 했습니다.
지금까지 팀 중에 팀명은 가장 빠르게 정했습니다.
제가 0인분을 담당하는 대신 대회 리뷰를 쓰기로 했습니다ㅋㅋ 본격 대회 참여 안하고 리뷰 쓰기,,
연대 1등 팀 (playsworld16, plast, ystaeyoon113) 은 세명 모여서 빡겜해도 이기기 힘들거라고 생각했고, 세명중에 아무나 한명만 풀어도 수상 커트라인인 10등 안에는 들거라고 생각했기 때문에 아무 부담 없이 보기로 했습니다.
대회 당일에는 coconut99와 wlgh7407 둘 다 집에서 비대면으로 진행했습니다.
당일에 오사카에서 나라로 가서 사슴과 놀다가 저녁 비행기로 돌아오는 일정이였어서 저는 아예 참여하지 않으려고 했는데, 당일 아침에 오사카에 호우특보가 와서(...) 그냥 라멘이나 먹고 역 앞에 카페에서 놀았습니다.
대회가 12시 시작이였는데 11시 반에 카페에 도착했길래, 다른 두명한테 suapc 아이디좀 달라고 하고 저는 입코딩만 하기로 했습니다.
coconut99 형이 A~F, wlgh7407이 M~G (역순) 을 보고 저는 G F H E ... 순서대로 읽으면서 생각하는거 있으면 던져주기로 했습니다.
대회 타임라인
~0:05 A AC (+1)
그냥 브론즈 문제라던데 coconut99가 1틀하고 맞아왔습니다.
그사이에 저는 G를 읽고 "mod 998244353 박혀있는 씹덕 트리 조합론" 하고 넘기고, H를 열었다가 잊어버리기로 했습니다. 그리고 I를 열었더니 후원사 문제길래 열심히 설명해서 wlgh7407한테 구현하라고 시켰습니다.
실수오차 + 케이스워크 문제여서 직접 짜기는 정말 싫은 문제였는데 풀이만 던져주고 시키니까 너무 재밌었습니다.ㅋㅋ
wlgh7407이 M 풀이가 있다길래 풀고 오라고 했는데, 좀 더 다듬어야 된다고 해서 그럼 I 구현부터 하라고 했습니다.
~0:45 C AC (+1)
F를 열었더니 이상한 NP문제를 풀라길래 스킵하고, E, D, C를 읽었습니다.
E는 그냥 50만까지만 체크하면 될 것처럼 생겼는데 15분 시점에 이미 불기둥이 박혀있었기 때문에 넘겼습니다. 빨간색이 20팀 넘게 있었던 것 같은데 실제로 대회 끝날 때까지 6팀밖에 못풀었네요.
D는 1e9개의 정점과 2000개의 간선이 주어지는 흥미로운 조건입니다. 연결 요소만 체크하고, 다른 연결요소면 워프 박으면 cost 1로 이동 가능합니다. 연결 요소가 2개 이상이면 같은 연결 요소에 있어도 cost 2 이내로 이동 가능한데, 거기까진 생각 못하고 "대충 다익스트라 박아서 해줘" 하고 넘겼습니다.
C는 그리디하게 해구성하는 문제입니다. 풀이가 2분만에 나왔는데, 직접 구현하는 것보다 풀이 설명하는게 더 어려워서 3~6까지 핸드폰 노트에 하는 방법 적어서 보여주고 아무튼 다 되니까 짜달라고 했습니다.
coconut99 형이 "너가 말한대로 했는데 왜 틀림?" 했다가 1ㄱㄷ 치더니 맞아왔습니다.
~0:55 I AC
wlgh7407이 열심히 구현하더니 한번에 맞아왔습니다. 구현하는데 오래 걸리긴 했지만 아무튼 한번에 맞은 팀 중에서는 퍼솔임(1)
그사이에 저는 L번 컨스트럭티브 아이디어를 냈고, 나중에 알았지만 틀린 아이디어였습니다.
~1:17 D AC (+2)
코드를 안읽어봐서 잘 모르지만, 제 사풀이 절반만 맞았기 때문에 구현하고 -> 틀리고 -> 문제 읽고 -> 고치지 않았을까 싶네요.
J번을 읽고 사풀을 하나 냈다가 틀렸다는걸 깨닫고 wlgh7407과 같이 잠시 고민했습니다.
wlgh7407이 J번을 읽더니 "LCP + 이분탐색" 이라는 무시무시한 소리를 하길래, 그게 정해면 20분대에 퍼솔이 뜰리가 없다고 확신하고 일단 넘기기로 했습니다.
그 사이에 저는 2번째 L번 아이디어를 냈고, (여전히) 틀린 아이디어였습니다.
E는 여전히 불기둥이 세워져 있었고 이 시점에서 4등이길래 패널티는 좀 먹었어도 나쁘지 않은 출발이라고 생각했습니다.
~2:03 B AC (+3)
coconut99 형이 B에 389B짜리 코드를 내길래 쉬운 문제인줄 알았는데, 그러고 나서 심연으로 사라졌습니다.
E는 한팀 풀릴때까지는 건드리면 안될 것 같아서 wlgh7407과 함께 L을 건드렸습니다.
구현에서 한번 틀리고, 고쳤는데 또 틀리길래 나이브 검증 코드를 짜러 갔고 그 사이에 B번을 맞아왔습니다.
저는 난바역 앞 카페에서 나와서 공항으로 가는 기차를 타러 갔습니다.
~3:14 M AC (+1)
검증 코드를 완성한 wlgh7407이 L번에서 반례를 찾아왔고, 저는 세 번째 (또 틀린ㅋㅋ;) 풀이를 냈습니다.
그 사이에 차라리 풀이가 확실했던 M번을 먼저 미는게 나을 것 같아서 wlgh7407은 M번으로 넘어갔고, pbds로 비비려다가 1TLE 받고 펜윅으로 고쳐서 맞았습니다.
여담으로 M번은 비슷한 세팅과 아이디어가 올해 SCPC 2차 2번에 나왔었습니다. 그땐 pbds로 뚫었어서 이번에도 될줄~
1TLE를 받았을 떄 프리즈가 되었는데 프리즈 시점에서 Endgame 팀은 이미 11솔이길래 "저 팀은 미친 팀이다" 라는 결론을 내렸습니다.
3연10등은 안된다 팀이 프리즈 시점에서 10등이길래 상당히 흥미로웠습니다.
저는 공항에 도착했고, 프리즈까지 5솔밖에 못해서 슬슬 쫄리기 시작했습니다. 사실 이때도 10등은 넉넉할거라고 생각했고 그냥 생각보다 우리팀 퍼포가 잘 안나오고 있다는 생각이 강했네요.
~3:42 E AC
이제 슬슬 E번을 잡아야 될 것 같아서 coconut99와 함께 의견을 냈고, 단순 나이브로는 안되고 컨스트럭티브하는 방법이 몇개 없을것이다라는 가정 + 예제에서 1이 포함된 답이 있다는 것을 줬기 때문에 몇가지 끄적거려 보다가 1, 15, 15^2, 15^3, ... 이렇게 고르고 앞에 (3, 5와 서로소인 자연수) 를 곱한 것들을 다 곱하면 얼추 될 것 같다는 결론이 나왔습니다. 좀더 깔끔하게 만들려고 정리하고 있었는데 coconut99형이 저기까지만 듣고 잘 구현해서 한번에(!) 맞았습니다.
오픈에서 한번에 맞춘 팀은 우리밖에 없으니까 아무튼 우리가 퍼솔임(2)
저는 수화물을 맡기려고 기다리고 있었고, 7솔부터는 확실히 수상권일거라고 생각했기 때문에 안심하고 아직도 못푼 L을 마저 고민하러 갔습니다.
~4:08 J AC
L번에 4번째 사풀을 냈고, 저는 이 풀이는 진짜진짜무조건맞는풀이 라고 생각하지만 wlgh7407이 "그냥 이분매칭 딸깍 하고 올게" 하고 들고갔습니다. 컨스트럭티브 구현 계속 시켰더니 싫었나봐요ㅋㅋㅋ
최근에 팀연습에 이분매칭 문제가 거의 매 연습마다 1번씩 나왔고 그때마다 wlgh7407이 다 풀어오길래 이번에도 알아서 풀겠지 하고 넘겨줬습니다.
그 사이에 coconut99형이 J에 bitset으로 비빌 수 있을 것 같다는 풀이를 냈고, 한번에 맞았습니다.
LCP 이분매칭 같은 짓을 하고 있었으면 진짜 많이 말릴뻔
~4:11 L AC (+3)
그리고 이분매칭을 겨우 15분만에 완성한 wlgh7407이 맞아왔습니다. 매칭천재
남은건 F, G, H, K였는데 H는 대회 시간 내에 아무도 못풀거라고 확신했고 F는 어떻게 푸는지 모르겠어서 G랑 K에 집중하기로 했습니다.
wlgh7407이 K에 스플레이트리 같은 미친 소리를 하길래 G로 던져버리고, coconut99형이랑 동시에 LCA로 잘 비비면 될 것 같다는 얘기를 했습니다. 형이 K를 짜러 간 것 같아서 나머지 둘이서 G를 보기로 했습니다.
~4:55 K AC (+3)
G번이 올바른 괄호 문자열 구하는 문제와 동치이고, 이건 카탈란스럽게 될거라는건 알고 있었는데 문제는 이걸 dp로 어떻게 구하는지 몰랐습니다. 그리고 문제를 제대로 안읽은 저는 이 문제 제한이 10만인 줄 알고 O(nlogn) 풀이를 고민하다가 폭사했습니다ㅋㅋ
G는 5시간 안에는 못풀 것 같아서, 저는 가방 검사와 출국 수속을 하러 갔습니다.
그리고 출국 수속을 끝내고 나왔더니 그 사이에 K가 풀려 있었습니다. 그저 coconut99..
후기
프리즈 이후에 무려 5문제를 추가로 푸는 기행을 벌여서 스코어보드에 교란을 줄 수 있지 않을까 했는데, 최종 순위는 중간 순위와 똑같은 4등으로 마무리했습니다.
팀연습 할때마다 느끼는건데 저희 팀이 아이디어를 내는 속도는 빠른데 그에 비해 구현이 상당히 약한 편입니다. 그래서 컴퓨터가 노는 상황은 거의 안생기고 항상 5시간 꽉꽉 채워서 구현을 하고 있네요. 보완해야 할 부분인 것 같습니다.
I번 같은 문제를 직접 구현 안하고 입코딩만 하니까 너무 재밌었습니다.
PS:Endgame과 Redshift 팀은 처음부터 2인팀으로는 이기지 못할 팀들이라고 생각했고, F번의 플로우 풀이를 몰랐기 때문에 셋이 같이 했어도 12솔을 따지는 못했을 것 같습니다. 이제 정말 플로우 공부할 때가 됐네요
2.1인분 팀으로 4등이면 충분히 잘했다고 생각했는데 3등팀은 완전 2인 팀이라고 해서 당황했습니다. 2인팀한테 지다니!
오픈콘에서는 ksun48님이 혼자 12솔을 달리셨던데 누텔라는 역시 이상한 사람들인 것 같습니다.
그리고 누텔라가 100분을 박아도 못푸는 H는 대체..
다른 팀의 후기
- PS:Endgame 팀의 후기 (https://ktypsblog.tistory.com/21)
- Redshift 팀의 후기 (https://blog.naver.com/vermeil_/223568417158)
- 탈PS는 지능순 팀의 후기 (https://yabitemporary.tistory.com/entry/SUAPC-2024-summer-3등-후기-탈PS는지능순)
1~3등 팀원분들이 후기를 하나씩 쓰길래 코딩은 한글자도 안했지만 저도 뭔가 써야할 것 같아서 써봤습니다. 이거 쓰려고 티스토리 블로그 만들었습니다 ㅋㅌㅋㅋ
블로그 글 처음 써봤는데, 글자 색 자동으로 넣는 방법 구합니다. 하나씩 넣으려니까 너무 귀찮네요
'알고리즘' 카테고리의 다른 글
| 월간 향유회 8월 오프라인 대회 후기 (2) | 2024.09.03 |
|---|