대회 일주일이나 지나서 쓰는 후기. 후기 맛집 dong_gas 형처럼 맛있게 쓰려고 노력했지만 역시나 실패한듯하다?
작년에는 PS를 안해서 참가하지 않았는데 올해는 했기 때문에 참가했다. 근데 3,4,5월 깔짝 한걸 했다고 할 수 있나?
난 도대체 뭘 했는가
방학때 신촌 캠프를 자체드랍해서 6만원을 날려먹었다ㅋ 신촌에 갖다바친 돈이 15만원이 된 모습. 그 이후로 방학에는 PS를 거의 안 했다. 정수론에서 벽느끼고 중급 알고를 포기해버림
그리고 정수론을 날먹하려고 이번 학기에 정수론을 듣고 있는데 PS에 쓰이는 정수론은 고작 세번인가 네번의 수업만에 끝나버렸고 나는 아직도 확장 유클리드를 구현할 줄 모른다. 절대 듣지 마세요
그리고 이번 학기에는 PS를 방학 때보다 더 안 했다.
변명하자면 전공 수업과 과제가 빡세서 알고리즘 공부를 할 시간이 없었다. 물론 피파 할 시간에 백준을 풀었다면 퍼플을 찍고도 남았을거다. 아마 이번 학기에 랩실에 와본 사람 중 스쿼드메이커에 열중하고 있는 나를 본 적 없는 사람은 없을 것이다? 그럼 변명이 맞지. 그냥 내가 게을러서 공부를 안했다. 사실 SUAPC 전부터 PS 뽕이 빠져버려서 거의 PS는 접은거나 마찬가지였다.
중간고사 기간 전에는 백준에 있는 '단기간 성장' 문제집을 풀려고 했는데 구현 문제가 너무 많아서 포기해버렸고, 중간고사 기간 이후에는 실력을 올리는 데 유사코만한 게 없다고 해서 유사코 문제를 밀려고 문제집까지 만들었지만 영어 해석하기가 귀찮아서 포기해버렸다. 아니 정말 런 원툴이네;
하지만 이번 학기에는 백준 대신 코포를 좀 열심히? 잘? 해서 블루를 찍었다! 본대회랑 업솔빙을 꼬박꼬박 해서 그나마 감은 어느 정도 유지했다고 생각한다.
안진마
대회 신청을 깜빡하고 있다가 랩실에서 p_jun이 참가자 명단 확인하고 있길래 신청했다.
참가자를 얼추 생각했을 때 전체적으로 수준이 높다고 생각했다. 당연히 Champion 부문에는 훨씬 고수분들이 계시지만 작년 Master 부문 수상자 분들의 당시 코드포스 레이팅에 비해 올해가 비교적 높아서 빡센 것 같았다. 블루가 나 포함 두명, 민트는 더 많았고.
대회 전의 예측으로는 딱 3등 정도 할 것 같았다. 항상 랩실에서 열심히 중급 알고를 밀고 있는 lem0nad3와 yunny_world가 1,2등을 나눠 먹고 그래도 코포는 열심히 한 내가 3등 정도 하지 않을까 하는 생각? 방학 이후에 알고리즘 공부를 게을리하긴 했지만 코드포스는 그래도 열심히 했어서 CP는 좀 자신 있었다. 아무튼 수상은 무조건 한다는 마인드였다!
뭔 팀노트여~
대회 당일에는 ksm010825 형, qu_b_eenyoung 누나와 서강식객 제육을 먹었다. 펜을 안 가져온 줄 알고 랩실 볼펜을 훔쳐왔는데 알고보니 가방에 필통이 있었다? 아침에 검색해봤는데 기온이 심상치 않아서 이번 겨울 처음 패딩을 입었는데 미친 추위였다 정말 다행
대회장 도착해서 자리를 보는데 한사람당 빅파이가 무려 3개씩이나 준비되어 있었다...? 알고보니 빅파이 12^2개를 사려고 했는데 학교에서 잘못 주문해서 12^3개를 사버렸다고 한다. 지금도 랩실에 빅파이가 아주 많이 남아 있으니 많이들 와서 먹어주세요^^
lem0nad3와 yunny_world 자리에 놀러갔는데 둘다 팀노트를 만땅으로 가져왔더라. 나도 다익스트라가 가물가물ㅋㅋ해서 팀노트에 적어갈까... 싶었는데 그냥 대회 전에 코드 한번 보면 되겠지 하는 안일한 생각으로 안 챙겼다. 랩실 멤버들이 잘했으면 하는 마음으로 자리 세팅을 했다.
input.txt 세팅을 하는데 세팅 다 하고 보니까 깔려있는 비주얼 스튜디오가 2022였다. 비주얼 스튜디오 2022는 명령 인수로 input.txt를 넣으면 콘솔 창이 뜨지 않는다... 링커-시스템이나 디버그-속성을 고쳐도 안되더라. 내가 어떻게 하는건지 모르는 거라면 알려주세요ㅠ 그래서 2019 버전을 새로 깔고 세팅했다. 1시에 오길 잘했다.
경건한 마음으로 양치를 하고 대회를 시작했다.
대회 타임라인
0:01 A AC
0솔 방지 후원사 문제. 3배라는 정보를 한번에 못찾아서 0분에 풀지는 못했다.
0:16 B AC
구현 문제... 날짜 유효성 체크 해주는 함수 짜기가 귀찮았다. 대회 때는 코드 더러워도 일단 타이핑부터 해야 하는데 굳이 함수 간단하게 짜려고 하다가 퍼솔을 뺏겼다.
B를 원트에 맞힌 사람이 나밖에 없어서 좀 뿌듯했다ㅋㅋ
0:22 C AC (first solve)
수학(하)에서 배우는 조합론 문제. 본대회 때는 2!이나 3!으로 나누지 않은 사람이 꽤 있었던 것 같다. 예제 2에 duram이 나와서 내가 안나오면 서운할뻔했는데 예제 3에 내가 나와서 기분이 좋았다.
0:29 D AC (first solve)
뭔가 한 쌍만 지울 수 있다면 나머지는 어떻게든 지울 수 있어 보여서 6분동안 코드를 짜고, 이게 아닌가? 싶은 고민을 1분 했다. 틀리면 그때 고치지 뭐 하는 생각으로 내봤는데 맞았다. 증명은 비둘기집의 원리로 할 수 있다.
djs100201 형이 쉔디같은 애들은 이런 문제 10분컷할거라고 했다고 한다. 코포 하는 사람들은 prove by ac에 익숙해서 그런듯?
1:02 E 3WA. AC
k번째가 아니라 마지막에 처리할 일을 출력하는줄 알고 12분만에 구현해서 싱글벙글하면서 냈다가 WA를 한 번 받았다. 이후 마지막 1번 쿼리 전까지의 2번 쿼리는 의미가 없다는 관찰을 하고, 미친 관찰을 한 나 자신을 칭찬하고, 오프라인 쿼리와 deque로 처리하는 코드를 한 번 내서 WA를 받고, 이상한 데를 괜히 고쳤다가 또 WA를 받고, segfault가 나는 반례를 찾고서 AC를 받았다.
여름방학 언젠가 오프라인 쿼리를 공부해서 몇 문제 풀었던 게 도움이 됐다. 난 오프라인 쿼리가 좋아
E까지 풀었을 때 나한테 풍선이 4개밖에 없었다! 내가 잘못 봤나 싶어서 풍선 개수를 계속 힐끗힐끗 봤다. dart님이 내 마음을 눈치채셨는지 하나를 더 달아 주셨다. 편-안
1:57 F 1WA. 1TLE. AC (first solve)
E를 풀고 F로 넘어갔는데 이미 lem0nad3가 2틀을 해놨길래 50분 벌었다 생각하고 문제를 읽었다.
읽자마자 아 이거 하늘에서 떨어지는 1, 2, 3, ... , R-L+1 개의 별인데! 싶었지만 난 그 문제를 신촌 중급반에서 해설 보고 레이지 없이 풀었기 때문에 당연히 기억나지 않았다... 이래서 문제 안 풀릴 때 구글에 찾아보면 안된다.
어떻게든 다른 nlogn으로 비벼야겠다고 생각했고, 쿼리를 저장해 둔 다음에 스위핑하면서 현재 인덱스가 어떤 쿼리 구간에 포함돼있는지 알 수 있도록 스택에 쿼리 번호를 넣고 빼는 식으로 짜서 WA를 받았다.
이후 그냥 스택이 아니라 pq를 써서 현재 인덱스가 여러 쿼리 구간에 포함돼있다면 가장 나중에 들어온 쿼리를 처리하도록 해서 TLE를 받고, 쓸데없는 map을 쓰고 있음을 깨닫고 배열로 바꿔서 AC를 받았다.
F를 풀고 raararaara 선배님께서 풍선을 달아 주셨는데, 그 순간 lem0nad3가 제출을 해서 내 모니터로 채점 결과 보고 가셨다ㅋㅋㅋ
이 문제의 비하인드로, 원래 이 문제는 nlogn 풀이를 아예 막을 생각이었다고 한다. set이나 레이지 세그를 다 막고, nlogn 중 그나마 빠른 pq만 뚫리는 상황이었는데, gumgood 선배님께서 nlogn을 막을거면 pq도 막아야한다! 라고 주장하셨다고 한다. 하지만 기각되어서 pq는 뚫리는 채로 남았는데? 마침 내가 pq로 뚫었다ㅋㅋㅋㅋ
운이 좋았다고 생각한다. 이 문제 제한시간이 1.2초인데 내가 1156ms에 돌아가는 코드를 제출했으니 정말 아슬아슬했다.
2:51 ~ 2:55 G 3WA
트리의 지름을 찾고, 지름을 제외한 subtree들의 지름을 찾고, pq에 넣고, pq에서 하나씩 빼고, pq에서 뺀 subtree의 subtree의 지름을 찾고, 그걸 다시 pq에 넣고, ... 하는 코드를 짜서 3번 WA를 받았다.
WA를 받는 동안 lem0nad3가 F를 더 제출하고, H까지 제출하길래 이거 못 풀면 지나...? 싶어서 정신없이 구현했는데 결국 못 풀고 대회 끝나고 업솔빙했다ㅠ
노드가 N개일 때 지름을 제외한 모든 subtree의 지름과 subtree의 subtree의 지름과 ... 를 O(N)에 구할 수 있다. 구현이 생각보다 쉽지 않았다.
이 문제가 koosaga님의 추천+기발함+교육적임 3단콤보를 받아서 출제자 dong_gas 형이 좋아했다.
풍선을 6개나 받아서 기분이 좋았다.
에어팟 까비
Master 부문 1등을 해서 금상을 받았다! 이번에도 스코어보드 공개는 dong_gas 형이 진행했다. 청정수컵 때도 느꼈지만 말을 정말 잘하는 것 같다. lem0nad3가 F를 못 푼 걸 미리 들어서 당연히 1등일 줄 알았는데, F를 푸신 분이 두 분이나 더 계셔서 하마터면 1등을 놓칠 뻔 했다.
스코어보드를 공개하는 중간에 특별상 에어팟 프로의 주인을 추첨으로 뽑는 시간이 있었는데, Picasso 선배님과 ksm010825 형이 가져가게 되었다. 사실상 진정한 우승자는 이 두 분이 아닐까ㅋㅋㅋ
청정수 컵 때 들었던 "그저 남들보다 빨리 풀어서 1등을 했을지"를 이번에도 들었다ㅋㅋㅋㅋ dong_gas 형의 센스
이번에는 정말로 그저 남들보다 빨리 풀어서 1등을 했다. D까지 원트로 밀기도 했고 퍼솔이 많아서 페널티 관리가 잘 됐다.
마무리
어쩌다 보니 올해 참가한 개인전 두 번을 모두 우승하게 되었다...? 내가 개인전에서 멘탈을 잘 잡는 것도 맞지만 우승을 한 것은 운이 좋았다고 생각한다. 내가 dp를 진짜 정말 너무 못하는데, 두 번 다 dp가 뒷 번호에 플래 정도 난이도로 나와서 못 풀어도 우승할 수 있었다. 그리고 이번에는 F를 마침 pq로 뚫었으니 풀이를 갈아엎은 적도 없었고.
대회가 끝나고 raararaara 선배님, gumgood 선배님, weasel 선배님과 술자리를 가졌는데, 정말 좋은 말씀을 많이 해 주셨다. 특히 gumgood 선배님께 PS 가스라이팅을 부탁드렸는데 야무지게 해주셔서 당분간은 PS를 놓지 않을 것 같다. 감사합니다 선배님ㅋㅋ!
역시 PS 뽕을 채우려면 대회를 쳐야 한다. 확실히 나는 PS보다 CP를 좋아한다. 알고리즘 공부는 싫어. 하지만 ICPC나 SCPC에서 퍼포먼스를 내려면 중급 알고는 자유자재로 쓸 줄 알아야 할 것 같아서 공부를 해 보려고 한다... 일단 dp부터.
좋은 대회 열어 주신 Sogang ICPC Team 운영진 분들, 출제진 분들, 검수진 분들께 감사합니다.
'PS > 대회 후기' 카테고리의 다른 글
| SUAPC 2022 Summer 후기 (7) | 2022.09.11 |
|---|---|
| 2022 서강대학교 청정수컵 - 청정수 Round 후기 (7) | 2022.05.16 |