2023 ucpc 본선 후기

UCPC 본선에 "김앤장" 팀으로 출전했다. 팀원들은 나, 김지훈(etyu), 장보규(maruii)이다.

 

요즘 열심히 CCO도 밀고 현대 모비스 대회도 쳐서 감이 나름 살아있다고 생각해서 ucpc 전에 특별히 ps 연습을 안 했다. 팀연습은 했어야 하나 싶기도 한데 평소에도 대회 전에 특별히 연습을 안해서 그냥 안 했다. 대회 전날에 일찍 자려고 노력했지만 체스를 두느라 새벽 5시에 자버렸다. 아침 8시 반에 일어났음에도 불구하고 컨디션이 괜찮았다. 평소에도 4시에 자서 그런 듯하다. ucpc는 문제 퀄리티가 항상 좋으니까 재미있는 문제 풀 생각에 신이 났다.

 

대회 장소에 도착하니까 평소에 온라인으로만 보던 사람들을 볼 수 있어서 좋았다. 잠깐 돌아다니다가 세팅을 시작했다. 대회 장소가 SK 판교 사옥이었는데, 공간도 넓고 깔끔하기도 하고 좋았다. 커다란 모니터도 하나 있어서 쓰려고 했는데 모니터 2개를 못 써서 못 쓴다고 하더라... 그래서 모니터는 못 쓰고 그냥 노트북 하나로 대회를 쳤다. 

 

대회 시작 전에 평소처럼 내가 ABCD, etyu가 중간, maruii가 후반을 보자고 했다. A번을 봤는데 골드거나 다이아처럼 생긴 구성적 문제가 나왔다. 스코어보드가 난이도를 알려줄때까지 안 보기로 하고 B번으로 갔다. 쿼리 문제길래 C번으로 넘어갔다. C번을 읽으니까 NP 문제처럼 생겼다. D번으로 넘어가니까 이것도 쿼리 문제길래 다시 C번으로 돌아왔다. 이상해서 문제를 다시 읽으니까 하나의 정점이 최대 하나의 경로에 들어간다는 조건을 빼먹었더라;; 일단 K=0이면 다익스트라 문제이기 때문에 이 문제는 다익스트라 문제이고, 내 경험상 다익스트라 문제는 보통 쉬워서 좀 잡고 있었다. 새로운 그래프를 만들고 다익스트라를 만들면 되었다. 그래서 구현을 하겠다고 하고 키보드를 잡았는데, 내가 무슨 그래프를 만들고 있는지를 모르겠었다. 좀 뇌절하다가 팀원한테 키보드를 넘기고 다시 생각하다가 구현했다. 다 구현했는데 예제가 안 나오길래 프린트하고 코드를 유심히 보니까 별의별 구현에서 삑사리가 났더라... 좀 고치니까 1시간이 지나갔다. 그래서 우리 팀의 첫 AC는 1시간대이다. ㅈㅅㅋㅋ;;

 

etyu가 F번을 풀고 maruii가 L번을 풀어서 나는 슼보에 풀린 문제들을 대충 읽고 있었다. B번이 대충 식정리를 한 다음에 셋으로 잘 관리해주는 풀리는 문제처럼 생겼다. 식정리를 위해서 열심히 관찰을 했다. 같은 종류의 두 숫자 중에 뒷쪽 숫자의 위치를 고정해주면 사이 간격으로 식이 잘 나오더라. 셋으로 잘 관리하면 되겠다 해서 maruii가 L번을 풀 때까지 기다렸다. 기다리면서 문제들을 둘러 봤는데, 그래도 조금 풀린 M번은 히스토그램에 산 그리는 문제라서 별로 풀고 싶게 안 생겼다. 옆에 etyu가 H번 보라고 하길래 봤는데 무슨 수학 문제가 있었다. 대충 끄적여보다가 B번을 풀러 키보드를 잡았다. 구현은 티피컬해서 힘들지 않게 할 수 있었다. 다 구현하고 나니까 WA가 뜨더라. 프린트하고 보니까 인덱스를 넣을 자리를 헷갈린 이슈였다. 고치고 깔끔하게 AC.

 

내가 코딩을 하는 사이에 etyu가 M번을 풀어줬다. 이맛에 팀대회 치지ㅋㅋ H번이나 다시 잡았다. 대충 시뮬레이션 하면 되는 문제였다. 그래서 etyu의 M번 코딩을 마치고 짜려고 기다리고 있었다. 그런데 maruii가 I번 구현을 빨리 할 수 있다고 키보드를 넘겨줬다. 그리고 H번의 케이스워크 같이 보이는 것들을 조금씩 정리하고 있었는데, maruii가 갑자기 구현을 못하겠다고 하더라. 대충 들어봤는데 국산 자료구조 비빔밥이더라. 이런거를 etyu가 첨에 잡았으면 1시간컷 냈을텐데 조금 아쉬웠다. 암튼 대충 구현은 쉬워보여서 내가 대신 구현을 해주고 maruii한테 H번의 풀이를 대략적으로 설명해준 뒤에 I번을 구현했다. segment tree 2개를 짜고 dp에 스택으로 잘 해주니까 120줄 정도 코드가 나왔다. 예제가 안 돌길래 maruii한테 키보드를 넘겨주고 프린트해서 디버깅하기 시작했다. 생각보다 잔실수들이 많길래 연필로 끄적대면서 고쳤다. 중간에 몇 번 틀린 것을 발견했을 때 키보드를 빼앗았는데 예제가 안 나왔다. 팀원들한테 미안해서 코드를 끝까지 다 읽어서 잔실수를 다 고친 다음에 키보드를 빼앗기로 했다. 제출을 했는데 WA가 나왔다. 뭐가 틀렸는지 봤는데 long long 이슈더라. 고쳐서 깔끔하게 AC.

 

이때 시간이 50분 남았는데 풀이가 뜬 문제가 한 3개 정도 있었다. etyu한테 풀이를 들었는데 E번은 기하더라. 기하인데 쉽다고 주장하길래 풀이를 들었는데 중간에 조금 틀린 부분이 있었다. 수정하고 나니까 convex hull에 머시기 저시기 구현해야 했다. 이거 구현했다가는 아무 문제도 못 풀 것 같아서 버렸다. K번은 들으니까 대충 되는 풀이처럼 생겼다. 빨리 짤 수 있다고 하길래 나는 maruii가 H번을 풀고 etyu가 K번을 풀고 싱글벙글하는 시나리오를 상상했다. 그런데 H번이 생각보다 안 풀렸다. 같이 디버깅을 했는데 뭔가 덕지덕지 케이스들을 끼워맞춘 느낌의 코드가 있길래 디버깅이 너무 어려웠다. 내가 깔끔한 H번 코드를 짤까 생각했는데 키보드는 K번 구현 때문에 못 쓰고 있어서 연필로 좀 끄적였다. K번 구현이 예상 외로 오래 걸려서 못 풀 것 같았다. 한 7분 남았을 때 키보드를 뺏어서 H번 코드를 짰는데 WA가 떠서 결국 H와 K 둘 다 못 풀었다.

 

스코어보드를 까는데 H번을 못 푼 팀이 거의 우리 팀 밖에 없었다. 집 가서 코드 다시 봤는데 한 10분 만에 풀었다ㅜㅜ 초반과 마지막에 좀 말린 것 같았다. 근데 결과적으로는 작년과 비슷한 등수인 13등을 했다. 잘 친건지 못 친건지 잘 모르겠지만 문제를 재미있게 풀었으니까 좋은 대회였다.