UCPC 2018 온라인 예선

뭔가 운좋게 문제가 잘 풀려서 팀명대로 8 솔브에 성공하고 17등으로 본선 진출권에 안착했다.

아래는 타임라인 별 진행

~00:00

시작하기 전에 내가 맨 앞 4문제, 규정님이 중간 3문제, 진일님이 마지막 3문제를 읽어보고 풀기로 정했다.

~01:43 Solve A

A번 읽고 보니 굉장히 쉬운 문제라 그냥 바로 코딩에 들어가서 AC.

~06:59 Solve B

그다음 B번을 읽었는데, 그리디하게 풀면 풀릴 것 같아보이긴 했지만 증명이 감이 안 잡혀서 넘겼다. 그 다음 C,D 둘 다 읽어봤는데 이 두 문제도 별로 만만치 않아보였고, 이 시점에서 스코어보드를 보니 B를 많이 풀었길래 그러면 그리디가 맞겠지 생각하고 에라 모르겠다 짜서 제출 후 AC. 하지만 여전히 왜 그리디가 동작하는지 증명하지 못했고 증명이 궁금하다.

~15:19 Solve G

 내가 D번을 고민하는 사이 진일님이 G번을 풀어주셨다.

~16:30 Solve D

C를 조금 고민하다가, 아무래도 쉬운 문제가 아닌 것 같아서 다시 D로 넘어왔다. 대충 읽고 좀 어려운 건줄 알았는데 스코어보드를 보니 많이 풀려있길래 쉬운 풀이가 있나보다 해서 좀 더 고민해보니 정말 쉬운 풀이가 있었다. 그래서 바로 코딩 들어간 후 AC.

~36:54 Solve F

트리를 순회해서 구간으로 편 후 편 구간에 대해 c이하의 원소 개수를 구하면 해결되는 문제다. 구간으로 편다는 아이디어를 비교적 빨리 떠올렸는데, c 이하의 원소 개수 구하는게 잘 생각이 안나서 시간을 조금 썼다. merge sort tree로 풀면 쿼리당 log^2n 으로 풀리고, 미리 짜둔 merge sort tree 코드가 있어서 복사붙여넣기 슥삭해서 풀었다.

~56:52 J WA

이후에 C번 잠깐 보다가, 아무래도 빨리 안 풀릴 것 같아서 팀원 분들한테 혹시 뒤쪽에 풀만한 문제가 있냐고 물어보았다. 진일님이 J번이 풀릴 것 같은 문제라고 말씀하셔서 바로 J로 넘어갔고, 첫번째 숫자는 비슷한 문제를 많이 풀어본 적 있어서 쉽게 구했다. 두번째 숫자를 구하는 방법에서 좀 고민을 많이 했는데, 방법을 하나 떠올렸고 이게 분명히 맞다고 생각해서 코딩 후 제출했다. 하지만 WA.

~57:57 J WA 2

다시 보니 1번 숫자 구할 때 모듈러를 안했다는 것(...)을 깨달아서 모듈러 후 제출. 하지만 여전히 WA.

~65:15 J WA 3

여기서 입력 범위도 잘못 봤다는 걸 깨닫고, 다시 고쳐서 제출했지만 여전히 WA를 받았다. 분명 고칠만한 실수는 다 고쳤음에도 불구하고 WA가 나오는게 뭔가 반례가 있는게 분명하다는 생각이 들어서 여기서 잠깐 멈췄다. 

~75:08 Solve H

반례를 찾는 사이에 규정님이 H를 풀어주셨다.

~ 93:48 Solve J

반례를 찾기 전까지는 제출하지 않기로 마음먹고 반례를 좀 찾다가, 도저히 못 찾겠어서 팀원들한테 우선 풀이를 설명했다. 이상하게 풀이를 설명하고나서 다시 테스트해보니 바로 반례가 나와서 그걸 수정. 금방 수정하고 맞췄다. 여기서 반례를 찾지 못해서 시간을 좀 많이 썼다. 꼼꼼하게 이것저것 넣어봤으면 꽤 빨리 찾았을텐데, 이게 좀 아쉽다.

~ 120:22 Solve I (WA 1)

여기서 이제 남은 3문제(C,E,I)중에 뭘 풀까 고민하다가, I번 붙잡고 계시던 진일님이 I 완전 단순한 구현 문제라고 하셔서 그걸 넘겨 받았다. 문제에서 시키는 거 정직하게 구현한 후 한번 멍청한 실수로 WA 받고나서 AC. 

~ 180:00

남은 한 시간 동안 나는 E를 잡고, 진일님 규정님은 계속 C에 시간을 썼다. 여기서 왠지 머리가 멈춰서 풀이가 잘 안 떠올랐고, 풀 수 있는 방법을 30분쯤 지난 후에 떠올렸는데 남은 30분동안 구현할 체력도 자신도 안 들어서 포기. 여기서 같이 C 풀이에 붙었고 5분쯤 남겨둔 시점에서 점화식을 짤 실마리를 찾았는데 당연히 시간 부족으로 포기했다.  어쨌든 팀명대로 8솔브에 성공해서 만족스럽게 끝.

끝나고 나서 곱씹어보니 J 반례에서 막혔을 때 J를 계속 붙잡고 있지 말고 I를 먼저 풀고 올 걸 그랬다는 생각이 든다. 이제 보니 J 처음 WA후 거의 40분을 반례를 찾는데 낭비했다. 아마 이 40분 사이에 I를 풀고 왔어도 결과적으로 J를 푸는데 걸린 시간이 별 차이는 없었을 것 같다. 그랬다면 시간이 꽤 많이 남았을 것이고, C나 E중에 하나는 더 풀지 않았을까. 마지막에 그냥 같이 C풀걸 나눠서 들어간 것도 패착인 것 같고.. 좀 더 잘했다면 올 솔브도 가능했을 것 같은데 그 점이 아쉽다.