UCPC 2020 본선 후기

고3 때를 포함해서 3번째 UCPC. ICPC멤버 그대로 (imeimi2000, jhhope1, TAMREF) 완전탐색 원툴 16등 도전합니다팀으로 참가했다. 최종 성적은 10 / 12 solve 5등으로, 역대 UCPC 중에서는 제일 좋은 성적이 나왔다. 팀연습이라고는 UCPC 예선밖에 없었는데 결과는 별로 나쁘지 않았다 ㅋㅋ 기억나는대로 타임라인을 재구성해본다. 약한 스포일러가 있으니 주의.

 

---

초반 (0~1시간)

 

내가 앞, 이멘이 중간, 즈홒이 뒤를 맡았다. A에 후원사 로고가 붙어있는 걸 발견했지만 뭔가 "제일 쉬운 문제"로 불릴 정도는 아닌 것 같아서 B랑 C를 보고 있었다. 한창 복잡한 지문을 읽고 있는데 스코어보드에 초록색 A들이 쫙 깔리기 시작했다. 정신 차리고 보니 쉬운 문제더라. 트리에서 높이가 D 이상인 정점의 개수 * 2가 답이었다. AC (12min).쉬운 문제를 알아보는 능력이 필요할 듯. 이건 실제로 셋을 많이 돌아보면 감이 잡힐 것 같다. 골드급 문제들을 쌓아놓고 풀 건 아니니까...

 

이멘은 F를 잡겠다고 했고, 즈홒은 L에서 고전하고 있었다. 갑자기 그런디 얘기를 하길래 화들짝 놀라서 일단 그거 풀지 말라고 했다 ㅋㅋㅋ 다행히 그런디를 알고 한 이야기는 아니었다. B 지문을 모르겠어서 C로 넘어갔다. C는 내가 좋아하는 functional graph 문제였다. N이 크지 않아서 생각을 자유롭게 할 수 있었고, 적당히 O(N^2 log N ~ N^3) 정도에 돌아가는 풀이를 무리없이 구현했다. 나쁘지 않은 문제인 듯.  AC (34min). 

 

즈홒의 L 뇌절이 생각보다 오래가길래 어려운 문제일 거라 생각했고, 이때쯤 즈홒은 K로 넘어갔던 것 같다. 일주일 전에 dual graph에 대해 공부하기는 했지만, 나는 아직 평면그래프 문제를 보면 도망치고 싶은데 어떻게 바로 돌격하는지 모르겠다. 이 맛에 즈홒이랑 팀 한다 ㅋㅋ! 이멘의 3500B짜리 F 코드가 틀렸고 아직 갈 길이 멀었다. 나는 일단 많이 풀린 B로 넘어가기로.

 

정신차리고 B를 읽어보니 그리 어렵지 않아보였다. 항상 가능한 x좌표의 범위가 구간의 형태로 나타난다는 걸 깨닫고 코딩으로 들어갔다. 모든 구현스펙을 미리 생각하고 들어간 게 아니라서 구현에 좀 힘이 들었다. O(N + KMlogM) 풀이를 짜고 AC (55min). 이때까지 코드가 한 번도 안 틀렸다 ㅋㅋㅋㅋㅋ 컨디션이 좋은 게 느껴졌다.

 

예상과 다르게 스코어보드에서 L이 풀리고 있어서 L로 넘어갔다. 즈홒은 이미 K에 꽂혀있었고, 두세 시간 정도 박겠다 싶었다. 문제 지문을 어찌저찌 읽어보니 JOI 케이크 자르기 2 랑 스펙이 거의 똑같았다. 비슷한 느낌의 dp를 짐작했는데.. 2차원 dp로 잘 안되는 것 같아서 이런저런 짓을 해보니까 크기 2억짜리 dp table을 잡으면 된다는 결론이 나왔다. "메모리 800MB? 해볼만하지 ㅋㅋ" 를 외치면서 돌격했다. 원 위에서 dp 돌리는 건 언제나 짜증난다 ㅡㅡ... 근데 이것까지 한 번에 AC (87min). 코딩머신 역할을 제대로 해내고 있었다 ㅋㅋ

 

중반 (2~4시간)

 

L을 맞고 I를 봤는데 디스크립션이 이거저거 난잡한 게 많았다. 직선일 때는 전형적인 문제 같았는데 원일 때는 어떻게 할 지 모르겠더라. 이멘은 D가 dnc opt로 풀린다며 회심의 제출을 시도했지만 틀렸고, 즈홒은 K에 첫 제출을 하면서 수난시대를 열고 있었다. 이때쯤 순위가 10위권에 들어왔고, 보드 위쪽을 보니 rkm0959팀이 H를 풀어놨길래 보기로 했다. ㅋㅋ!

 

그런데 H는 정수론이었다. 출제자가 ahgus89 아니면 sait2000님일 것 같아서 입구에서 돌아나왔다. 그런데 옆에 있는 G는 문자열이었다 ㅋㅋㅋㅋㅋ 그래도 둘 중에 자신있는 정수론을 보기로 했다. 식 정리가 너무 터프해서 시간이 오래 걸릴 건 예상하고 있었다.

 

즈홒은 K에서 20분 간격으로 제출하고 틀리고를 반복하면서 눈물을 한 바가지 쏟고 있었고, 이멘은 다행히 빠르게 dnc에서 빠져나와 2차원 dp를 구현해 AC (+1, 147min). 나는 공책 가득 H 식정리를 하면서 출제자를 욕하고 있었다. I가 할만하다고 이메이미한테 말하자마자 "그냥 잘 하면 되는 듯" 하면서 바로 맞았다. AC (165min). 사람일까 ㅋㅋ

 

H 식을 정리해보니 Dirichlet Convoluton으로 \(\sum_{k = 1}^{n} \phi(k)\)를 빠르게 구해야 한다는 결론이 나왔고, 풀려면 내가 풀어야 한다는 생각으로 피타고라스 쌍 코드를 긁어왔다. 그런데 예제 2에서 컷당하더라 ㅜㅜ 코딩머신은 여기까지였다. 식정리를 잘못 했다는 결론이 나오고, 한 시간 정도 더 지난 뒤에야 \(\sum_{k = 1}^{n} \phi(k), \sum_{k = 1}^{n} k\phi(k), \sum_{k = 1}^{n} k^{2}\phi(k)\)를 다 구해야 한다는 미친 결론을 얻을 수 있었다. 아니 알큼은 이걸 어떻게 58분에 푼 건데 ㅋㅋㅋㅋ

 

내가 ahgus89에 대한 악감정을 쌓아가고 있을 때, 이멘은 G를 등반하고 있었다. 이멘답지 않게 5번이나 틀린 뒤에야 AC(+5, 218min). 그런데 풀이 들어보니까 틀릴 만하더라 ㅋㅋㅋ 내가 짰으면 더 오래 잡았겠다 싶었다. 

 

즈홒의 코드는 4800B를 넘기고 있었다. 원래 헤비한 코드를 잘 짜지 않는 즈홒인데 엄청 힘들었겠다 싶다... 그러더니 K를 진짜로 맞아 왔다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ AC(+5, 235min). 사실상 4시간 가까이 한 문제만 본 셈인데 나는 그렇게까지 말려서 맞은 적이 한 번도 없다. 진짜 리스펙이다... 코딩을 내가 도와줬다면 시점 자체는 앞당겼을 수도 있지만 어쨌든 이걸로 즈홒은 1인분을 다 했다.

 

종반 (4~5시간)

 

그 뒤로 눈물 위에 쌓은 H 코드가 완성되었는데 2번을 틀렸다. 왜 틀렸는지 몰라서 한참을 헤맸는데 코드가 진짜 개판이었다... SIEVE 크기를 바꿔가면서 열심히 디버깅한 결과 \(\sum k^{3}\) 대신 \(\sum k^{4}\)를 구했다는 놀라운 사실을 알 수 있었다. 그 사이 이멘은 F에 다시 도전하더니 툭 맞아왔다. AC(+2, 260min).  들어보니 dp 계산이 까다로운 문제같았다.

 

H에 30분을 더 바친 결과 드디어 SIEVE=3과 SIEVE=3e6이 같은 결과를 냈다 ㅋㅋㅋㅋ 하지만 코드에 떡칠된 int128과 mod연산 때문에 TLE가 걱정이었다. O3를 박을까 생각하다가 그냥 냈는데 이게 맞았다!! 우리 팀 마지막 AC(+2, 268min).

 

내가 H를 고치는 동안 둘은 나머지 문제를 보고 있었는데, J는 Money for Nothing on Tree라서 남은 시간 안에는 풀 수 없다는 결론이 나왔고, 문제에 "플로우를 돌려라"라고 쓰여 있는 E를 보고 있었단다. 정말 사풀처럼 생긴 풀이가 완성이 되었고 예제가 나오길래 냈다. 당연히 WA 3번 쌓고 끝났다. 그 와중에 그게 "intended 사풀" 이어서 출제자에게 즐거움을 주었다.

 

총평

순위는 5등이었는데, 1 - 4등 팀에 은퇴선수가 대부분이고 실력이 넘사라서 결과 자체에는 만족한다. 특이 유형인 H를 푼 것 때문에 순위가 높게 나온 것 같긴 하지만... 돈 더 받으니 좋은 게 좋은 거다 ㅋㅋ!좋은 부분은 내가 ABCL을 dirt 없이 맞은 것과, 즈홒이 결국 가장 적게 풀린 그룹 중 한 문제인 K를 맞아낸 것. 솔직히 두 역할이 바뀌었으면 결과가 엄청 나빠졌을 것 같다. 이메이미가 웰노운을 무리 없이 밀어줘서 H에 집중할 수 있었던 것도 좋았다.다만 맨 처음에 가장 쉬운 문제인 A, L을 알아보지 못하고 날린 시간이 10~30분이고, D와 F, G에서 조금 억울하게 시간과 페널티를 날린 감이 있다. 작년 ICPC J처럼 치명적인 수준의 뇌절은 아니지만, 합쳐놓고 보면 1시간 정도의 기회비용이 발생한 것 같다. 마지막 AC 기준으로 1시간 40분 ~ 2시간이 남았다고 생각하면 E를 열심히 풀어보거나, J를 맞을(!) 수도 있었단 걸 생각해 보면 아쉬운 부분이 없지는 않은 셈이다. 물론 뇌절 없는 대회는 없기 때문에 어쩔 수 없다.

 

여러 사건이 많았지만 결국 성공적으로 대회를 이끌어주신 운영진(...ahgus89는 남아^^)께 감사를 표한다. SNUPC 어떡하지 ㅋㅋ