사실 열린다는걸 알고 있긴 했으나 원래 자주 팀을 이루던 Hyp3rFlow 팀원들도 각자 바쁘기도 하고 굳이 참가할 생각이 없던 대회였는데, 생각치도 못하게 준태님께 연락이 와 참가하게 되었다. CV에 한 줄 적을 수 있는 기회는 놓칠 수 없으므로.
대회 전날까지 "적어도 크립토에서 1인분을 하자"라는 마인드로, RSA나 격자, 기타 등등의 것을 복습하고 있었으나, 실상 대회에는 크립토가 오직 두 문제만 출제되어 굉장히 당혹스러웠다. 그마저도 대회 시작 21분만에 모두 풀어 남은 7시간 39분간 뭘 해야할 지 막막한 상황에 이르렀다.
다른 팀원들이 pwn, rev, web 문제를 풀고 있었기에 나는 잘 모르지만 Forensic 문제를 잡아보기로 하였고, 구글링을 동원하여 열심히 풀어냈다. 생각보다 구글링이 잘 되는 키워드들이라 풀기 수월했던 것 같다. 그렇게 Forensic 두 문제를 해결한 시각이 11시 08분, 나는 또 5시간 52분간 놀 위기에 처했다. 다행히 준태님이 REV1을 리버싱한 코드를 주셔서 그거 풀었다. 그래도 3시간 11분 놀았다. 3시간 11분간 놀면서 다른 문제 브포 코드 잘못 짜인거 발견해서 고치고 다른 팀원들 응원하면서 지냈는데 그동안 과자를 너무 많이 먹어서 살 빼긴 그른 거 같다.
문제 퀄리티에 관해서는 개인적으로 조금 불만이 많다. 데프콘과 시기가 겹쳐 출제 위원을 제대로 확보하지 못한 것인지, 작년 CCE 문제를 flag prefix도 수정하지 않은 채 가져온 문제가 상당히 많았고(체감 상 절반 이상) 쉬운 리버싱 문제(rev1)의 난이도를 올리고 싶었던 건지 small trick이라면서 misc 요소를 넣어서 잘 푼 팀들이 이상하게 말려버렸고, 결국 어떤 팀은 마지막의 small trick을 제외하고서는 11시 4분에 해결하였으나 small trick에 막혀 마지막까지 rev1을 풀지 못했던 것으로 기억한다. 아무리 좋은 문제가 안 나와도 작년에 진행된 대회의 문제를 그대로 가져오면 공정성 등 여러 문제가 있는데 이렇게 대회가 진행된 건 참 아쉬운 점 중 하나이다. 마지막 문제 제출 시간이 아깝게 밀려 상금이 200만원 깎여버린것도 아쉬운 부분 중 하나지만... 버스 탄 입장에서 만족한다.
올해 처음으로 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에서 $x$ 이하의 수의 개수를 온라인으로 셀 수 있는 자료구조가 필요하다고 생각했고 당황한 나머지(+재활을 게을리한 나머지...) 제대로 떠올리지 못하고 있었다. jjaewon9가 pbds를 써보라고 제안했지만 사용법을 몰랐고, jjaewon9가 kth 세그를 제안했다. 이거다 싶었던 나는 곧바로 구현에 들어갔고 정확히 구현했다고 생각했으나 정말 왜인지 모르겠는 의문의 출력초과 3개를 팀원들에게 선물했다. 아직도 왜 출력초과가 발생했는지는 이해하지 못했다. 팀원들의 압박감을 더하거나 덜어주려는 누군가의 계략이 분명하다고 생각한다.
50:25 D WA
58:06 D WA
64:54 D WA
미안하다... (https://jjaewon.tistory.com/29)
이 시점에서 사실 추가선발이 아닌 본선진출은 어렵지 않을까 생각하고 있었는데, 아마 팀원 모두가 그렇게 생각하고 있었을 듯하다. 모두가 맞왜틀만을 외치기를 약 한 시간, 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가 다른 대학이라 팀원 한 명을 구해야 하는데 누굴 데려와야 할 지 모르겠다. 흠.
