UCPC 2019 본선 후기

https://www.acmicpc.net/category/detail/2054

UCPC 2019

17등! 개인적으로는 그냥 딱 우리 실력에 풀 수 있는 걸 다 푼 느낌이였는데 생각보다 높은 순위를 받았다. 이번 셋이 워낙에 어려웠고 5솔 표준 세트였던 ABEKL중에서 A, E가 정말 말리기 쉬운 문제였기 때문에 그런 듯 하다. 

 

타임라인:

0분: 시작할 때 gyuni가 ABCD, 내가 EFGH, nevivurn이 IJKL을 맡기로 했다. 우선 난 E의 페이지수를 보고 바로 빡구현문제라 판단해 일단 넘어갔고, F는 미친기하의 냄새가 나서 도망갔다.

 

7분: (현장 사진)"어 이거 그냥 트리 대충 그어보면 나오지 않을까?" 하고 G번에 뭔갈 적고 있는 dlwocks31. 아니였다고 한다.

이때쯤 gyuni가 B번이 매우 쉽다고 선언하고 컴퓨터를 잡고 있었다. 나는 대회중에 문제를 읽지 않았다.

 

14분: B AC! 

G번은 뭔가 잘 그어지지 않았고, H번 또한 선인장이라는 이름에서부터 고인 그래프의 느낌이 났다. 내가 맡은 파트에서 더 읽을 문제가 없어, 옆에 앉은 nevivurn한테 M번을 받아 읽었다. 그리디 풀이에 대해 잠깐 nevivurn과 토론하고, 반례를 발견해 포기하고 K번을 받았다.

 

K번은 딱 봤을때 파라메트릭 같았고, 그래서 다음 문제까지 걸리는 최대 시간이 k인게 가능한지 판단하는 쪽으로 생각했다. 첫 직관은 그냥 두 슬롯 중 더 시간이 많이 있는 슬롯에 들어갈 수 있는 가장 긴 풀이를 집어넣는 것이였다. 예제가 맞아서 제출했고, 당연히 34분에 WA를 받았다. 지금 생각해보면 참 황당한 그리디인데, 음.. 앞으론 그리디 짤 때 생각을 좀 해야겠다? 같은 길이가 있으면 교대로 다른 슬롯에 들어가기 때문에 최적일 수 없다.

 

이 시점에서 nevivurn이 L번 풀이를 발견했다고 선언해 코딩에 들어갔고, 재귀적인 방법이였고 내가 그때 대략적으로 알고리즘을 들었는데 큰 모순이 없는거같아 맞을 줄 알았는데 장렬히 WA를 받았다. 내가 K번을 잡고 있는 동안 nevivurn과 gyuni가 L번을 같이 잡았다.

 

K번에서 금방 반례를 발견하고, 우선 문제 사이의 간격이 k라면 모든 풀이시간을 k의 정수배로 표현하기로 했고(즉, 모든 풀이가 k의 정수배 시간에 풀린다고 생각하기와 같음. 귀류법으로 생각하면 이게 맞는 걸 확인하고 이렇게 했다.), 그리디 전략을 바꾸기로 했다. 처음에는 가장 짧게 남은 슬롯부터 채워나가는 전략을 썼는데, 여전히 예제에서 틀렸고, 조금 더 생각하다가 이제 짧은 슬롯 채우는 전략을 유지하되 긴 슬롯이 가장 긴 풀이와 시간이 같아지면 긴 슬롯을 채우는 전략을 사용했다. 대략적인 직관은 빈틈을 최대한 줄이자는 데에서 온 것 같다. 몇가지 구현 실수를 마저 고치고, AC를 받을 수 있었다.

1:24: K AC!

nevivurn과 gyuni는 계속 L번을 잡고 있는 듯 했고, gyuni가 나한테 A번 풀이를 대략적으로 전달해 줬다. 적당한 preprocessing+이분탐색으로 모든 쿼리를 "a번째 숫자로 시작하는 b번째 닉네임은 무엇인가?" 로 환원시킬 수 있고, 이 쿼리는 어레이를 뒤에서 앞으로 보면서 현재 보고 있는 위치 뒤에 뭐가 나타났었는지를 BIT에 추적하는 것을 통해 오프라인+BIT으로 해결할 수 있다. 이해를 하고 내가 코딩에 들어갔다.

 

구현이 살짝 까다로웠고, 여기서도 구현 뇌절을 몇번 하고 2:17에 WA를 받았다. 이때쯤 nevivurn과 gyuni가 왼쪽에서 매우 치열하게 L번에 대해 토론중이였다.. WA의 원인은, 내가 어레이를 훑으면서 어레이에서 나타났던 숫자들에 대해서는 처리를 해줬는데, 나타나지 않은 숫자들을 처리를 해주지 않은 것이였다.. 내 코드가 모든 경우의 수를 어레이를 훑는 것만으로 고려하는지 좀 더 생각해봤어야 하는 거 같다.

 

이걸 처리하려는 도중에, nevivurn이 급하게 interrupt를 날렸고 컴퓨터를 잡고 토론에서 나온 L번의 문제점을 고쳐서 맞았다!

2:33 L AC!

나도 금방 A번을 마저 고쳐냈다.

2:40 A AC!

이때 우리가 4솔이였고, 우리 위로 DEFM밖에 더 풀리지 않았고, 그마저도 최대 2팀밖에 잡지 않았기 때문에 gyuni가 빡구현인 E를 풀러가고, 남은 문제들을 다 하나하나씩 읽어봤고, 짧게나마 같이 토론을 해 보았다. 갓문제들 사이에서 헤매다가 최종적으로는 nevivurn이 F에서 "공 하나를 더 추가할 때, 최대 원 하나와의 교점만 고려하면 된다"라는 결론에 도달해 F를 잡아보기로 했다. 이때가 3:30분이 좀 덜 됐을때 같은데, gyuni가 E를 구현하다가 스트링 파싱에서 막혀 내가 파이썬으로 잡으러 가고, gyuni와 nevivurn이 F풀이를 공략했다.

 

F에는 "trivial하지 않은 예외 케이스"들이 몇몇 발견되었고, 결국은 끝까지 풀이를 얻어내지 못했다. 공식 풀이를 보니까 뭔가 수식을 잘 전개해 그런 예외 케이스를 피해간 것 같은데..

 

나는 홀로 택시와의 외로운 싸움을 이어갔고, 수도 없는 뇌절(ex. A로 가는 승객을 태웠을 때 바로 A로 이동한다던가..) 끝에 모든 예제가 맞았고, 대회 종료 30분 전에 제출을 했으나 시간 초과. 파이썬 fastio 문제 같아서 fastio로 바꿔서 냈더니 WA.. 이런 문제에서 2KB짜리 코드를 어떻게 디버깅할지 모르겠어서, 이때쯤 F번을 반쯤 포기한 gyuni와 nevivurn이 코드를 프린트 해 오면 같이 봐주겠다고 해서 3명이서 같이 벼랑끝 디버깅을 시작했다.

 

나는 소수점 아래를 절사하는 로직이 확실하지 않아서 그쪽을 계속 보고 있었는데, 헷갈리긴 했지만 그 부분은 맞는 코드였다. 마지막 버그는 gyuni가 찾아냈는데, 나는 차가 얼마만큼의 기름을 가지고 있는지 저장하지 않고 대신 얼마만큼의 거리를 갈 수 있는지를 저장하고, 각 주유소에서 1거리당 얼마의 돈이 드는지를 저장하고 있었는데, 주유소에서 거리를 충전할 때 [현재 돈*(1거리당 얼마의 돈이 드는지)]를 차가 갈 수 있는 거리에 더하고 있었다.. 단위가 맞지 않다는 걸 gyuni덕에 알아냈고, 딱 그 부분을 고쳐서 제출했더니..

4:52 E AC!

5솔을 자축하며 남은 시간동안 스코어보드 구경하고 나가서 음료수를 마셨다.

 

총평

전체적으로는 매우 만족스러운 등수고, 말했듯이 우리 실력으로 풀 수 있는 문제는 다 푼 것 같다. 그래도 아쉬웠던 건 내 코드를 쓸 때 구현실수가 너무 많아서 시간을 많이 까먹었다는 점이였고, K번도 좀 더 체계적으로 접근했으면 더 빠르게 AC를 받을 수 있었을 텐데.. 정도? 물론 지금은 딱 5솔할 실력이 맞는 것 같지만, 조만간 시간이 나면 F번, M번 같은 우리 능력 조금 위의 문제도 업솔빙해보고 더 성장하고 싶다. 그리고 종료 8분 전에 E를 맞아낸 그 느낌을 정말 잊을 수가 없다..ㅋㅋㅋ 이런 느낌이 너무 좋아서 PS를 계속하게 되는 것 같다. 앞으로도 더 열심히..!