UCPC 2020 본선 후기

 

5 solve 패널티 703min, 28등으로 종료했다. 올해는 PS 관심 있는 초심자 두 분 대리고 팀 대회 경험 + 연습 시켜드린다는 느낌으로 참여해서 성적은 크게 생각 안 했는데, in30 했으니 성적도 나쁘지 않게 잘 마무리한 것 같다. in50을 목표로 했는데 훨씬 초과 달성. 본선에서 각각 한 문제씩은 풀게 해드리고 싶었는데 이것도 충족해서 깔끔하게 잘 끝난 것 같다.

 

아래는 타임라인별 정리. 다른 두 팀원분은 각각 대회 신청 당시 이름인 51호관114호 / 나무둥지 로 지칭해서 썼다.

~00:15

문제를 쭉 읽고 간단하게 풀이를 생각했다. A는 읽고 대충 풀이 방향이 생각은 났는데, 좀 더 쉬운 문제가 있을 것 같아서 일단 내버려두고 다른 걸 봤다. 근데 더 쉬운 문제가 없었다.. ㅋㅋ 다른 문제 풀이 고민하는 사이 나무둥지 님이 A번 풀이 방향을 잘 접근해주셨고, 맞는 것 같아서 그대로 구현에 들어가셨다.

~00:30

스코어보드를 보니 C가 많이 풀렸길래 C 풀이를 고민해봤고, 조금 고민해보니 스케치가 나와서 이 풀이를 그대로 51호관114호 님한테 전달드렸다. 난이도가 아주 낮은 문제는 아니다보니 풀이 전달에 시간이 좀 오래 걸렸다.

~00:46 A WA

그리고 B도 많이 풀렸길래 B를 읽어봤다. B도 읽어 보니 풀이가 바로 생각 나서 구현에 들어갔다. 구현하는 사이 나무둥지 님이 A를 구현해서 제출했으나 WA.

~00:51 B AC

그 다음에 내가 B 구현을 완료해서 제출 후 AC. 생각난 풀이가 세그 트리라 세그 트리 써서 풀었는데 나중에 풀이를 보니 오버킬이었다. 어쨌건 뭐 빨리 잘 풀었으니 상관없긴 하지만 ㅋㅋ

~00:52 A AC

그 사이 나무둥지 님도 디버깅을 완료해서 재제출 후 A도 AC.

~01:15 L RTE

다음으로 많이 풀린 문제인 L을 잡았다. O(100N^2) DP 풀이는 금방 생각났는데, 제한이 좀 빡빡해 보여서 탑다운으로 풀면 틀릴 것 같기도 해서 다른 풀이를 조금 더 고민하다, 뭐 틀리면 다시 짜지 생각하고 그냥 탑다운으로 짜서 냈다. 그런데 예상치 못한 RTE가 떴다.

~01:16 L WA

실수한 부분을 하나 찾아서 바로 재제출했으나 WA.

~01:17 L WA

또 다른 부분 하나 더 찾아서 다시 제출했는데 WA. 좀 신중하게 했어야 했는데 여기서 막 제출하면서 패널티를 너무 쌓았다 ㅋㅋ

~01:28 C WA

그 사이 51호관114호 님이 C 구현을 마쳐서 제출. 하지만 WA가 났다. L을 잠깐 내버려두고 C 디버깅을 도와드렸다. 여기서 내가 싸이클이 있는 경우의 식을 잘못 생각했다는 걸 알았고, 고친 식을 알려드린 뒤 다시 L 디버깅으로 돌아왔다.

~01:45 L AC

L에서 선공이 피자를 먹는 경우의 식이랑 후공이 먹는 경우 식이 살짝 다르다는걸 찾고 그걸 고쳐서 AC. 식을 좀 대충 세워서 너무 많이 틀린 것 같다. 확실히 검증했어야 했는데 검증 안하고 적당히 대칭이겠거니 하고 넘어간게 너무 큰 실수였다. 안 좋은 습관인데 잘 고치질 못하는 듯.

~01:47 C WA

C도 디버깅이 끝나서 재제출하셨으나 WA. 코드를 보니 모듈러 연산 실수하신 부분이 있어서 말씀드렸다.

~01:47 C AC

그것도 고쳐서 AC. 여기서 가장 쉬웠던 ABCL을 다 풀었고 페이스가 그렇게 나쁘진 않았던 것 같다. 남은 것중에 그나마 풀만한게 D라서 다 같이 D를 좀 고민하다, D 풀이 방향성이 살짝 잡혀서 팀원 두 분한테는 I를 봐달라고 말씀드렸다.

~03:17 D WA

그런데 여기서 한참 진전이 없었다. 위 아래에서 각각 A,B 인덱스까지 연결했을때 다음칸을 보는 식을 세운다는 방향성은 맞았는데, 이 식을 어떻게 세워야 할지 갈피를 못 잡고 한 시간 정도를 보낸 것 같다. 그러다 너무 막히는 것 같아서 팀원분들한테 I 어디까지 생각했는지 여쭤보고, 나도 생각한 부분까지 D 풀이를 설명드렸다.

 

설명드리고 나서 다시 찬찬히 생각해보니 간선을 기준으로 간선 왼쪽 컴포넌트 / 오른쪽 컴포넌트를 분리할 수 있다는게 갑자기 떠올랐고 이걸 이용하면 수식을 깔끔하게 정리할 수 있다는 걸 깨달았다. 이렇게 정리한 후 제출했으나 WA. 식이 워낙 간단해서 틀릴 곳이 없다고 생각했는데 틀려서 약간 당황했다.

~03:27 D WA

그 다음에 혹시나 해서 한 군데 수정해서 제출해봤는데 또 WA. 이건 뭔가 코딩 실수가 아니라 식을 잘못 세운 부분이 있을 것 같다는 생각이 강하게 들었다. 그래서 식을 다시 정리해보다가, 손으로 작은 반례 케이스를 하나 만드는데 성공했다. 이 반례 케이스에서 식 틀린 부분을 찾아서 고쳤다.

~03:48 D AC

그래서 D를 맞추는데 성공. D에서 시간을 너무 오래 쓰는 바람에 다른 문제를 고민할 시간이 별로 안 남아서 약간 초조해졌다.

~04:1x

I를 좀 더 고민하다 직선일 때 풀이 갈피는 잡았다. 그런데 이 풀이가 약간 부정확했고, 좀 더 가다듬으면 풀이가 나올 것 같긴 했는데 이거 찾는다고 원형 풀이가 나올지에 대해 확신이 없었다. 이 과정에서 G랑 I를 번갈아봤는데, G는 풀이를 정리하면 $가 1개일 땐 쉬웠고 $가 여러개일땐 초반 몇 개의 K만 보면 된다는 생각이 들었다. 구현이 어려워보이긴 했지만 풀이도 안 나온 I보다는 G를 잡는게 나을 것 같아 G로 넘어가서 구현을 했다.

~04:50

하지만 시간이 없어서 G도 깔끔하게 풀이를 정리하지 못하고 구현에 들어갔다보니 중간 과정에서 여기저기 막혔고, 결국 10분쯤 남은 상황에서 더 이상 고민해도 답이 안 나올 것 같아 그냥 포기했다.

~05:00

마지막 10분은 그냥 대충 잡담하면서 보냈던 것 같다.

 

그리고 끝난 뒤 풀이를 보다, I 풀이 설명에서 sparse table 언급하는 부분보고 아 이거 내가 아는 문제구나 생각이 딱 들어서 너무 아쉬웠다. 충분히 풀만 했는데 직선일 때 풀이를 좀 더 구체화하지 않은게 제일 나쁜 선택이었다. 시간이 좀 더 여유가 있었으면 좋았을텐데.. 직선 풀이만 제대로 생각했으면 100% 풀었을 것 같아 정말 너무너무 아쉬웠다. 뭐 D에서 시간을 너무 많이 쓴게 근본적인 문제라 어쩔 수 없었던 것 같긴 하다.

업솔빙

그리고 다음날 풀이를 아는 G, I 두 문제 업솔빙을 했다. I는 깔끔하게 생각했던 풀이 그대로 구현해서 맞았는데, G는 분명 맞는 것 같은데 계속 틀려서 한 시간 정도 헤맨 것 같다. 그러다 kdh9949님께서 본인이 고생했던 예외 케이스를 말씀해주셨는데 나도 그 부분이 문제였어서... 그거 고쳐서 AC. 잘못하면 오늘 하루종일 G 디버깅할 뻔 했다.

 

G 틀렸던 예외도 단순하게 "당연히 이렇겠지"하고 넘어간 부분이 문제였다. 어렵고 복잡한 문제를 풀 때마다 항상 느끼지만, 무의식 중에 당연하다고 생각하고 넘어가는 부분이 제일 큰 문제인 것 같다. 풀이의 모든 부분 모든 케이스를 꼼꼼하게 살피고 증명하는 습관을 들이도록 노력해야 할 듯. 계속 이걸 노력하고 있는데 여전히 이런 실수를 해결하지 못하는 걸 보면 어쩔 수 없나 싶기도 하고 ㅋㅋ...

 

나머지 문제들은 난이도가 넘 높아서 찬찬히 하나씩 풀어봐야 할 것 같다. 아무튼 문제도 재밌었고 대회도 좋았다.