작년 ICPC의 Entropi 팀이 그대로 돌아왔다.
팀명을 Entropii로 하려다가 (대회 한 번 칠때마다 뒤에 있는 로마 숫자가 1씩 커지는 느낌) 재미가 없어서 기각.
논의 끝에 Moonlight가 출제한 문제인 '멀티버스를 여행하는 한별이를 위한 안내서'에서 착안하여, '멀티버스를 여행하는' + (어떤 캐릭터)로 팀명과 닉네임을 짓기로 했다.
닉네임은 아래와 같이 지었다.
Cenix820 (나) : 고양이블롭 (마땅한 최애캐가 없어서 그냥 들고왔다)
Moonlight : 콜롬비나 하이포셀레니아
Loreips : 카가미네 린
그리고 난 팀노트에 고양이블롭에 대한 컨셉질을 했다. (사실 컨셉만 내가 잡고 글은 Gemini가 썼다)
팀원 소개나 하자. 일단 작년 ICPC때의 소개를 그대로 들고왔다.
Cenix820 (나) : 저점이 높은 대신 고점도 그 정도이다. 쉬운 문제 스피드런과 해 구성하기가 강점이다. 코드포스 기준 블루 실력이다.
Moonlight : 저점이 낮지만 고점이 꽤 높다. 수학, 특히 정수론이 강점이다. 코드포스 기준 블루 실력이다.
Loreips : 딱히 약점이 없는 우리 팀의 올라운더이다. 애드 혹과 구현이 강점이다. solved.ac 기준 Ruby III이며, 코드포스 기준 오렌지 실력으로 추정된다.
저게 작년 가을~겨울의 이야기이고, 그동안 우리는...
Cenix820 (나) : 겨울방학 때 허리디스크로 ps를 접었다가 봄학기 초에 kolorvxl과 sorohue의 멘토링을 받으며 고점 갱신. 5월에 열린 SCSC 대회 Div. 2에서 13등 달성. 코포 max rating이 1898이라 아직 블루이다.
Moonlight : 피안분이 되었다. :blobangery:
Loreips : 겨울방학 때 플래2~다이아5 정도의 난이도로 랜덤디펜스를 하더라. 봄학기에는 나랑 같이 코포를 하다가 치터로 오인되어 계정이 정지당한 후로 코포를 접었다. (Loreips는 초반이 매우 강한 스타일이다. 그레이가 초반에 찐레드 퍼포를 내고 있으니... 오해받기 딱 좋다.) SCSC 대회 Div. 2에서 7등을 했고, 요즘은 ps를 잘 하지 않는다.
이번 대회의 목표를 아래 두 가지로 정했다.
1) 꼭 본선에 진출하자.
개개인이 조금씩 성장을 했다고는 하지만 팀 전체의 전력은 작년 ICPC 때와 비교해서 크게 달라지지 않았다는 것이 팩트이다. ICPC 본선에서 우리 팀이 낼 수 있는 거의 최악의 퍼포먼스를 내며 47등을 했었기에, 이번 UCPC에서는 그때처럼 말리지 말고 무난하게 본선만 가자는 마인드가 컸다.
2) 이제는 나도 1인분을 할 수 있다는 것을 증명하자.
작년 ICPC 당시의 나는 평균적으로 민트, 운 좋으면 블루 퍼포를 내던 사람이었다. 애초에 0.5인분이라도 하면 기적이었다. 실제 대회장에서도 플래4를 2시간동안 풀어내지 못하며 팀에 별 도움이 되지 못했고, 무력함과 비참함을 느꼈다. 아직도 ICPC 본선 후기글이 없는 이유가 그 때를 다시 생각하기 싫기 때문이다.
이번에는 그러고 싶지 않았다. 플래티넘을 스스로 풀어내던가, 아님 그냥 골드 이하의 문제라도 빠르게 썰어내면서 팀에 도움이 되고싶었다.
팀원 모두가 학교에 모여서 치는 것이 이상적이지만, Loreips와 Moonlight가 각자의 집에 있어서 디코 통화로 소통하기로 했다.
대회 직전 Zoom 환경을 점검하는 시간에 꼬꼬면을 한 그릇 먹고, 팀원들과 노가리를 까다가 대회가 시작되었다.
0:00 (대회 시작)
Loreips가 A~D, Moonlight가 E~H, 내가 I~L을 보기로 했다.
A는 늘 그랬듯이 브론즈 문제였고, Loreips가 빠르게 풀어냈다.
0:01 (A solved)
Moonlight는 헬파이어 문제들을 보며 고통받고 있었다. 나는 I를 잠깐 고민해보다가 별로 어렵지 않은 문제인 것 같아서 Moonlight에게 토스했다.
뒤의 문제들을 읽다가 스코어보드를 보니 C가 풀려있길래 내가 잡았다. 지문을 이해하는 것에서 조금 절었지만 그래도 바로 맞췄다.
0:07 (C solved)
Loreips는 문제를 순서대로 읽어나가다가 E를 MST로 풀 수 있다고 주장하고 코드를 짜기 시작했다. 나는 계속해서 슥보를 따라 D를 잡았다. 역순정렬을 하고 적당히 그럴듯한 전략을 구현했다. 너무 때려찍은 느낌이라 제출할지 말지 망설이다가 냈는데, 다행히 틀리지 않고 단번에 맞았다.
0:12 (D solved)
Loreips가 열심히 E를 구현했다. 이것도 1트컷했다.
0:22 (E solved)
이 시점에서 풀려있던 다른 문제는 I와 L이었다.
Moonlight가 연립방정식을 이용한 I 풀이를 찾아 구현했지만, 내가 반례를 바로 찾았다. 그렇게 코드 짜오고 반례 찾기를 여러 번 반복했다. I를 계속 틀리고 있는 팀들이 많았기에 반례 찾기에 신경을 많이 썼다.
나와 Loreips는 L을 보며 LIS니 dp니 이것저것 토론하다가, J가 풀린 모습을 보고는 J로 넘어갔다. 잠시 뒤 Loreips가 J에서 정렬된 수열과의 차이가 최소화되도록 최종 수열을 만드는 그리디한 방법을 떠올렸고(찍었다고 한다), J 구현을 시작했다.
나는 솔브가 나온 B를 보고 touch the sky(다이아4)나 scenery(루비2)로 환원하는 풀이를 생각했다가 기각했다...
Loreips가 J에서 최종 수열을 만드는 코드를 가져왔고, 내가 이어서 cost를 계산하는 코드를 짜서 예제만 돌려보고 바로 제출했다. 1트컷 야미
1:07 (J solved)
내가 J를 이어서 짜는 동안 I의 풀이는 완성되어 있었다. 홀짝을 나누고 스위핑하며 그리디하게 뭔가를 하는거였는데 나는 잘 모르겠다. 암튼 Loreips가 Moonlight의 풀이로 I를 새로 구현했고, 만들어놓은 예제가 모두 잘 돌길래 바로 제출해서 맞췄다. I마저 한 번만에 맞추는데 성공했다!
1:09 (I solved)
여기까지 6솔브 + 패널티 178. 당시 13등이라는 꽤 높은 위치에 있었기 때문에 지금부터 한 문제만 더 풀더라도 안전하게 본선에 진출할 수 있을 것 같았다.
나는 그리디로 추정되는 B를 계속 고민하기 시작했고, Loreips와 Moonlight는 수학 문제인 L을 잡았다.
노트에 B 관련해서 이것저것 끄적이다가, 코포에서 자주 본 결정 문제로 바꿔서 파라메트릭 서치를 하는 전략이 떠올랐다. (사실 이 전략이 꽤 빨리 떠오르긴 했는데 그게 시너리로 이어져서 폐기했었다) 그러면 데드라인이 모두 동일하기 때문에 시작시간이 빠른 빵을 먼저 구우면 되겠더라. 그렇게 B를 풀었다고 주장하고 구현했다.
N 제한이 20만인 문제에서 시간복잡도가 NlogN * log(40억)인 코드가 돌아갈지 의심이 들었지만 일단 제출했다. 역시나 TLE가 나더라. (1:47)
Loreips가 내 코드를 C++로 번역한 후에 다시 제출했고, 맞았다.
2:02 (B solved)
스코어보드가 프리즈되었다. 프리즈 시점에서의 등수는 22등. 나쁘지 않았다.
그 사이 Loreips와 Moonlight가 잡은 L도 풀이가 나와있었다. Inversion 개수로 풀려고 하다가 기각하고는 에디토리얼의 풀이와 동일한 풀이를 찾았더라. 비재귀 세그트리까지 쓸 필요는 없겠지??라고 하면서 제출. 그리고 또 시간초과. (2:08)
얘도 C++로 다시 짜면 돌 것 같은 문제였고, Loreips가 또 번역 작업을 시작했다. 본선 진출은 이미 안전했기에 천천히 작업했다. 그런데 번역하고 보니까 타이핑 실수로 RTE가 계속 나서 조금 위험할 뻔함.
2:41 (L solved)
내가 K 풀이를 찾았다고 주장했지만 짤 시간이 없었고(나중에 알고보니 틀린 풀이였다), 남은 문제와 스코어보드를 구경하다가 대회가 종료되었다.
3:00 (대회 종료)
15등을 했다! 기대했던 것보다 훨씬 높은 순위로 본선에 진출하게 되었다.
나는 이번 대회에서 B, C, D를 풀고 I의 반례 nmk개 생성, J의 구현 막타치기 (+ L 디버깅에 아주 약간의 기여)를 하며 나름 1인분을 해낸 것 같아 더욱 만족스러웠다.
Loreips와 Moonlight도 좋은 퍼포먼스를 내서 얻을 수 있었던 성과라고 생각한다. 본선에서도 이만큼만 해줘라ㅎㅎㅎㅎㅎㅎ
오늘이 내 고점에 가깝다는 것을 알면서도, 본선에서는 이 이상의 퍼포먼스를 내고 싶다는 욕심이 든다.
남은 기간동안 셋을 많이 돌며 수련해야겠다.
+ 여담
대회 직후 아마스빈이 땡겨서 즉흥적으로 외출. 그렇게 학교(대전)에서 세종까지 갔다. (대전에는 아마스빈이 없더라)
콩국수랑 아마스빈 맛있게 먹었다.
