올해 초에 PS를 본격적으로 시작하기 전까지는 팀 대회를 할 때마다 코드포스 기준 민트 후반~블루 초반 실력에, 퍼플/오렌지로 구성된 팀에 들어가는 바람에 팀에 기여를 거의 하지 못했는데, 이번에는 1인분이라도 하기 위해 코포 레이팅이 비슷한 artichoke42(본인), jame0313, kyaryunha로 팀을 만들었습니다. 팀명은 어쩌다 보니 이재명! 이재명! 이재명! 이재명!이 되었는데… 음… 팀명은 정치와 무관함을 미리 밝힙니다.
대회 진행 초반(~60분)
대회 시작하면 구현 속도가 제일 빠른 jame0313님이 A를, kyaryunha는 B를, 그리고 저는 무슨 바람이 들었는지 J부터 거꾸로 보기로 했는데… 그러지 말았어야 했습니다. 어려운 문제가 다 후반부에 포진되어 있더군요… 덕분에 약 30분간 문제 읽기만 했습니다.
한편, jame0313님과 kyaryunha는 각각 A와 B 풀이를 찾았고, A는 대회 시작 후 10분경에 AC를 받았으나, B는 WA를 받았습니다. 이후 jame0313님은 그다음으로 할만해 보이는 H를 잡았고, 이 문제도 26분에 AC를 받았습니다.
그동안 저는 C를 읽기 시작했고, 간단한 확률dp문제라 식 정리 자체는 금방 되었으나, 소수점 곱셈이 여러번 되다보니, 부동소수점 오차 문제때문에 고민중이었습니다. 그런데 H를 풀고 스코어보드를 지켜보던 jame0313님이 C번 많이 풀린 것으로 봐서 부동소수점 문제가 없을 것 같다고, 믿음의 long double을 써보겠다고 해서, 정리한 식을 넘겨주고, 저는 B를 오래 잡고 있었던 kyaryunha의 B 코드를 보고, 반례를 던져줬습니다. 그 결과, C는 40분에 AC, B는 51분에 AC를 받았습니다.
대회 진행 중반(~120분)
4솔브 이후 스코어보드를 봤을때, D랑 G가 많이 풀려서, 제가 D를, 나머지 두명은 G를 같이 논의해보기로 했습니다. D는 지문 읽자마자 dp라는 생각이 들어서 dp로 풀었다가 WA를 맞았는데, 다시 생각해보니 믿음의 그리디(?)가 가능해보여서 제출했고, 이번에는 AC(61분)을 받았습니다.
이후 셋이서 다같이 G로 30분간 뇌절하다가, 스코어보드 상으로 E랑 I를 푼 사람이 많아서 저는 E랑 I를 손대기 시작했습니다. E는 naive하게는 N-K+1개의 길이 K의 연속한 구간에 대해 t값을 기준으로 삼분탐색하면 될 것 같다고 팀원들에게 전달했더니, jame0313님이 세그트리 쓰면 O(Nlg^2N)에 가능할 것 같다고 해서 코딩을 맡겼고, I는 constructive한 풀이를 금방 찾았으나, 구현이 많이 빡세보였습니다. 둘다 구현하다가 뇌절할 것 같아서 각각 I 코딩을 따로 하기로 했는데, 사실 코딩 시작한 시점이 대회 시작 90분 전이었음에도 대회 종료 전에 코딩 끝낼 자신이 없었습니다..
대회 후반(~180분)
구현을 맡긴 E에서 131분에 AC를 받았고, jame0313님은 다시 G를 풀기로 했습니다. 그리고 I 코딩 진행도가 kyaryunha쪽이 더 되어있는 것 같아, I 구현을 그쪽에 맡기고 저도 G 풀이 생각하는 쪽으로 선회했습니다. 그러던 중 jame0313님이 상자에 들어있는 공들의 숫자를 공차가 소수인 등차수열로 두는 아이디어를 제안했는데, 두 소수의 공배수에 대한 처리 문제가 있었습니다. 한 10분정도 더 뇌절한 뒤, 공차를 2000 이상 2500 이하의 소수로 두면, 공 개수가 최대 2000개까지기 때문에 공배수 문제를 해결할 수 있고, 공에 적힌 숫자도 500만 이하로 유지할 수 있다는 사실을 발견했고, jame0313님에게 코딩을 맡긴 결과 161분에 AC를 받았습니다. G 풀고 난 뒤엔 다른 문제 손대기엔 늦었다 싶어서 끝날때까지 I 구현을 지켜봤는데.. 아쉽게도 제출을 못해본 채로 대회가 종료되었습니다 ㅠㅠ…
대회 결과 7솔브를 하여 32등에 안착했습니다! 본선 진출 안정권 성적이긴 하지만, I를 못풀어서 8솔(및 solved.ac 기준 플래티넘 이하 문제 올솔)을 놓친 것과, G를 너무 늦게 생각해서 페널티 좀 쌓인게 아쉬웠습니다. 그리고 풀이 떠올린 문제는 여러개(C, D, G, I)지만 정작 제가 직접 코딩까지 한건 D밖에 없네요.. 이번 대회를 제 구현 능력의 심각성도 깨닫게 된 것 같습니다. 구현 연습 좀 해야겠어요 ㅠㅠ