올해 처음으로 UCPC에 참가하면서, pentagon03, jjaewon9와 함께 "새내기 개노답 삼형제"라는 팀명으로 참가하였다.
셋 다 ps에서 손을 뗀지 거진 1년이 다 되어가는 시점이었고 손을 떼기 전에도 만족스러운 실력을 갖고 있진 않았기 때문에 재활부터 시작하는 과정이 조금 어려운 감이 있었다.
나는 constructive, 수열(segtree, splay, etc), 수학을 위주로 담당하기로 하여 이를 공부하였으나 예선에서는 큰 쓸모는 없었던 듯 하다. 예선에서는 총 8문제를 풀었고 나는 A, E, H를 풀었다.
대회 시작 전 몇차례의 팀 연습에서 우리는 출제 가능성이 높은 몇가지 분야를 나누어 재활 훈련을 하였으며, 대회에서 사용할 전략을 논의했다. 별다른 것은 없지만 요약하자면 문제를 분담해서 읽고 categorizing한 뒤 각자 문제를 맡아 푸는 전략이다. 실전에서도 이러한 전략을 사용했고 그 결과 대회 진행 중 문제 분담을 효율적으로 진행할 수 있었던 것 같다.
총 10문제가 출제되어 sean9892:A,B,C,D / jjaewon9: E,F,G / pentagon03: H,I,J로 분담하여 문제를 훑었다. 예비소집에서도 언급되었듯 A는 브론즈 수준의 쉬운 문제였으므로 내가 B를 읽기 전 빠르게 A를 솔브하였다.
04:19 A RTE
05:15 A AC(+1) by sean9892
이 과정에서 코드 복사 실수로 인한 한 번의 RTE가 발생했는데, 어차피 후에 패널티를 잔뜩 섭취했기 때문에 사소하다고 할 수 있다.
A AC와 B,C,D 지문 리딩을 하던 사이 jjaewon9는 대회 시작 10분 이내에 E,G에 각각 "단순 구현"이라는 코멘트와 F에 간략한 코멘트를 남긴 채 G를 풀기 시작했다. 풀이 발상에 소요한 시간에 비해 긴 시간동안 구현 미스로 인해 패널티를 적립했다고 한다.
44:37 G TLE
47:53 G TLE
62:55 G WA
pentagon03은 H,I,J의 지문 리딩 및 요약을 무려 5분 내로 마쳤다. 마음이 급했는지 H 지문 리딩에 실수가 있긴 했으나 놀라운 리딩 속도이다. H: DP / I: 그래프DP / J: 배열정렬 정도의 간단한 코멘트를 남긴 채 H의 풀이를 잠시 고민하다 J로 넘어갔다. 역시 풀이에 비해 여러 구현 미스로 괴로워하고 있었다.
41:10 J WA
조금은 위태로운 상황이었다. 대회 시작 한 시간이 머지 않은 시점이었으나 AC는 5분에 받은 A가 전부였다. 약간의 다급함을 머금은 채 D를 풀기 시작했으나, 풀이가 좀처럼 명확해지지 않았다. multiset에서
50:25 D WA
58:06 D WA
64:54 D WA
이 시점에서 사실 추가선발이 아닌 본선진출은 어렵지 않을까 생각하고 있었는데, 아마 팀원 모두가 그렇게 생각하고 있었을 듯하다. 모두가 맞왜틀만을 외치기를 약 한 시간, pentagon03이 다행스럽게 J AC를 받아왔다. 머지않아 jjaewon9도 G AC를 받아왔다. 심각할 정도로 망한건 아니지 싶었다.
58:22 J AC(+1) by pentagon03
68:12 G AC(+3) by jjaewon9
내가 D에 잔뜩 출력초과를 싸놨기에 더이상 내가 이 문제를 손대는건 아닌 것 같았다. 계속 잡아도 계속 뇌절할 것 같았기에 pentagon03이 D를 넘겨받고 나는 pentagon03이 제쳐둔 H를 풀기 시작했다. jjaewon9는 스코어보드에서 많이 풀려있던 F를 풀기 시작했다. 다시 등장한 구현 미스를 딛고 jjaewon9는 109분 무렵 F AC를 받아왔다.
89:07 F WA
97:55 F WA
99:36 F WA
105:03 F WA
108:51 F AC(+4) by jjaewon9
H를 넘겨받은 나는 어쩐지 DP스럽다는 생각에 점화식을 세워보다, 카탈란 수와 유사한 점화식을 발견하였다. 이 문제는 카탈란이구나 싶어 이를 구현했으나 놓친 것들이 몇 가지 있어 한 번의 WA를 받았다. 이후로 약 40분간 더 고민한 결과 정확한 풀이를 발견하여 AC를 받았다.
83:47 H WA
119:45 H AC(+1) by sean9892
얼마 지나지 않아 pentagon03은 __int128과 내가 쓰는 방법을 몰랐던 pbds를 박아서 어찌저찌 잘 하더니 D AC를 받아왔다. 내가 출력초과를 받아놓은 게 있기 때문에 D의 패널티는 +6이 되었다.
110:28 D WA
117:03 D WA
122:29 D WA
129:26 D AC(+6) by pentagon03
프리징이 시작되었을 당시 A,F,G,H,J의 5문제를 해결하여 50 중반의 등수를 기록하고 있었다. 뒤이어 pentagon03이 받아온 D AC 덕에 등수가 제법 올랐겠지만, 남은 한 시간 동안 몇 문제는 더 풀어야 함이 명백했다. 본선... 나가고 싶었다.
B,C,E,I가 남은 상황에서 C, I는 누가 봐도 어려워보였기 때문에 버려두고 python Decimal로 E나 비벼보자는 생각에 E를 풀러갔다. jjaewon9는 B를 풀고 있었고, pentagon03은 D를 구현한 후 곧바로 jjaewon9와 함께 B를 풀기 시작했다. 선분교차를 짜야 한다고 징징대는 jjaewon9에게 해당 코드를 넘겨준 후 jjaewon9는 proof by AC를 시도하다 1WA를 적립하고, 본인은 의논이라 주장하는 모종의 독백을 한 뒤(pentagon03은 이에 "ㅇㅇ", "ㅋㅋ" 등의 반응만을 내비쳤다) 어떻게 잘 짜서 B AC를 받아왔다.
133:53 B WA
143:25 B AC(+1) by jjaewon9
잠시 뒤 python Decimal을 집어던지고 python의 datetime 모듈과 소숫점 연산의 힘을 믿은 내가 E AC를 받아왔다. 정말 놀랍게도 유일하게 패널티 없이 AC받은 문제이다.
144:55 E AC(-) by sean9892
C, I만이 남은 상황에서 팀원 모두 더이상 풀 자신이 없다는 것에 동의했다. 이후로 오간 대화는 "C 상인임?" "몰?루" "C 이거랑 같은 문제 아님?" "몰?루" 등이 전부였으며 특별상을 노려보겠다는 pentagon03의 제출을 마지막으로 예선 대회를 마무리했다. 대체 뭘 제출했길래 CE를 받은건진 모르겠다.
177:40 C WA
179:41 I CE
대회 종료 후 오픈컨테스트가 끝날 때까지 조금은 조마조마한 마음으로 시간을 보냈다. 우리 팀이 패널티를 워낙 많이 받아서 동 솔브수 팀 중 최하위일 것이라 예상했는데, 8문제를 풀었을 가능성이 있는 팀을 전부 따져보니 본선 커트라인을 넘어서는 것이다. 우리가 푼 문제 중 크게 어려운 문제가 없었으니 예선 탈락의 가능성이 있겠구나 하는 생각을 갖고 오픈컨테스트가 끝날 때까지 5시간 정도 쉬고 왔다. 다행히도 8솔브 이상인 팀이 총 30팀이었고, 예상과 동일하게 우리는 그중 최하위였다.(와!)
총평을 조금 해보자면, 재활이 덜 된 우리 팀으로써는 가능한 최대의 아웃풋을 뽑아낸게 아닌가 싶다. 총 10문제 중 8문제를 풀었으나 맞은 문제에서 틀린 횟수가 모두 합하여 17번이라는 기적적인 횟수를 일궈낸, 역사에 길이 남을 기록을 세웠다. 패널티 줄이는 연습을 할 필요가 있어보이긴 한다. 추가적으로, 플레티넘 문제도 빠르게 푸는 연습을 좀 해서 본선에서는 더 좋은 아웃풋을 내야 하지 않나 싶다. 아무튼, 잘하긴 했다. 끝.
A: 문자열 반복 + 단순 사칙연산
B: 선분교차 + 그리디
C: 몰?루 트리dp랬나 그리디랬나.
D: 좌표압축 + 세그orPBDS
E: "파이썬"
F: 단순 구현
G: constructive
H: 카탈란 수 + 올바른괄호열
I: 진짜 모름.
J: ad-hoc? 수학 쓰는 경로 압축
ICPC에서는 jjaewon9가 다른 대학이라 팀원 한 명을 구해야 하는데 누굴 데려와야 할 지 모르겠다. 흠.
'etc' 카테고리의 다른 글
| HackTheon 2022 후기 (0) | 2022.08.11 |
|---|