2023 UCPC 본선 후기

서론

UCPC 본선에 참가하였다. 팀 구성 등의 정보는 예선 후기에 대부분 나와 있다. 우리팀뿐만 아니라 다른 팀의 포스텍 분들도 지방에서 오시는 분들이 많아 전날에 미리 모여 숙소를 잡고 당일 아침 일찍 대회장으로 출발했다. 대회 목표는 작년 000102팀의 구성원 세 명이 모두 다른 팀 (강한친구대한국군, 당신을 대신해 UCPC 팀명을 정해드릴게요, 문제가 맛있어지는 주문) 으로 갈라져서 본선에 출전했는데, 이 중 1등을 하는 것을 목표로 하였다. 사실 객관적 전력은 세 팀 중 가장 열세였기에 저 목표만 이뤄도 괜찮은 기분으로 대회를 마칠 수 있을 것 같았다. 대회장은 대형 스코어보드가 없었다는 점만 빼면 작년보다 괜찮았던 것 같다. 자리가 끝쪽이라 나름 쓸 수 있는 공간이 많았던 점도 좋았다.

 

대회 중

대회 링크: https://www.acmicpc.net/category/detail/3630

 

petamingks가 앞, 내가 가운데, minsung05가 뒤를 보고 시작했다. 후배들이 컴퓨터 자리에 앉혀주어서 컴퓨터로 편하게 문제를 볼 수 있었다.

 

~0:43

내가 잡은 부분은 E~I이다. 지문이 비교적 짧고 (당시에는 몰랐지만 어려운) E, F, I를 먼저 읽었다. I가 재미있어 보여서 제일 먼저 잡았다. DP식은 쉽게 나오는데, 이를 최적화할 방법이 빠르게 떠오르지 않았다. monge한지도 체크해봤는데 아쉽게도 아니었다. 다른 팀원들도 바로 풀 문제가 없다고 해 I와 씨름을 하고 있었는데, 상당히 늦은 시간에 L 퍼솔이자 대회 전체 첫 솔브가 나와서 컴퓨터에 앉아 있던 내가 바로 봤다. L은 약간 전형적인 문제였는데, 한 부분을 꼬아 놓은 점이 재미있었다. 예전에 앳코더에서 비슷한 문제를 풀다 억까를 많이 당한 기억이 있어서 이번에는 구현을 꼼꼼히 해 한 번에 AC를 받을 수 있었다.

 

~1:02

L을 푼 후 스코어보드에서 풀린 문제는 C, G, H 정도가 있었다. petamingks가 수학인 H를 가져갔고, minsung05가 C를, 내가 F를 읽었다. F는 문제는 쉽지만 생각이 바로 나지 않았다. 그 사이 petamingks가 H 풀이를 찾아 구현했고, 상당히 빠른 시간에 AC를 받았다.

 

~1:42

H 코딩이 이루어지는 중 minsung05한테 C 설명을 들었는데, 그냥 다익스트라 슥슥 돌리는 문제인 것 같아서 컴퓨터가 비자 마자 바로 잡았다. 코딩은 어렵지 않았고, 예제도 잘 나와 제출했는데, WA를 받았다. 딱히 코딩할 문제도 없어서 20분 정도 뚫어져라 쳐다보니 실수한 부분이 보여 고쳐 바로 AC를 받을 수 있었다.

 

~2:55

이 때쯤에는 G가 상당히 많이 풀려 petamingks와 minsung05가 같이 G를 풀었고, 나는 F를 조금 더 생각하기로 했다. 서브트리는 ETT를 돌리면 구간 쿼리로 바뀌고, 교집합이니 직사각형 최댓값 쿼리가 된다. 이 문제는 직사각형 구간합보다 살짝 어렵다. 직사각형 구간합 쿼리를 처리하는 방법은 크게 3가지로 알고 있었는데, 1.PST 2.세그+오프라인 스위핑 3.머지소트트리였다. 1번과 2번은 역연산이 존재하지 않는 max 연산의 특성상 발전시키기가 어렵고, 3번 방법에 집중하였다. 생각을 해 보니, 머지소트트리의 각 노드에 Sparse Table을 박으면 합 쿼리와 비슷한 방법으로 가능할 것 같았다. 마침 G 풀이도 나왔다고 해 두 문제는 거의 동시에 코딩이 이루어졌다. G를 먼저 짰지만 한 번 틀렸고, F는 열심히 짰지만 로컬에서 자꾸 이상한 RTE가 나와 문제였다. 다행히 G를 먼저 고쳐서 맞았다.

 

~3:09

다행히 F 코드의 문제점을 찾을 수 있었다. 머지 소트 과정에서 이상한 인덱스에 접근한 부분을 잘 바꾸어주니 예제가 나와 제출했다. 채점이 상당히 오래 돌았지만 다행히 한 번에 AC. F 짜는 과정에서 알았는데 알고 보니 C, L 코드에 fastio를 쓰지 않고 제출했었다. ㅋㅋ 맞았으니 다행이니 이걸로 페널티를 적립했다면 좀 어지러웠을 것 같다.

 

~5:00

그 다음으로 많이 풀린 문제는 M, B, I였다. 나는 B와 I를 동시에 잡았고, petamingks와 minsung05가 M을 잡았다. 다행히 M 풀이가 비교적 빨리 나왔다. 여기서 분기점이 생긴다. 두 가지의 판단이 가능했는데, 1.M 풀이를 듣고 직접 짠다. 2.M 구현을 팀원들에게 맡기고 B와 I 풀이를 계속 생각해본다. 가 그것이었다. 전자는 확실히 6솔이 가능했지만, 7솔 이상을 노리기 위해 후자를 택했다. 아쉽게도 M의 구현은 (내가 중간중간 B 사풀로 컴퓨터를 뺏긴 했지만) 시간 안에 완성되지 못했고, 나 역시 두 문제의 풀이를 찾지 못해 5솔로 마무리했다.

 

최종 18등, 5솔 중 1등으로 마무리했다. 페널티 관리가 잘 된 탓인지 솔브 수에 비해 등수가 상당히 높게 나왔다. 실제로 초반부(3솔까지)에는 등수가 꽤 괜찮았는데, 중반에 어려운 문제들 풀이를 제대로 내지 못하면서 수상에 실패하였다. 처음 목표였던 000102 세 팀 중 1등은 대회 시작부터 프리즈 전까지 놓치지 않고 유지했지만, 프리즈 때 강한친구대한국군 팀이 1문제를 풀어내며 밀려나게 되었다. 하지만 저 팀은 16등임에도 불구하고 특별상을 받지 못했다. 제출을 정확히 12번 해 특별상을 받아낸 우리 팀의 승리라고 생각한다.

 

문제별 요약

A (D2, Not solved) : 문제를 읽지 않았다.

B (P1, Not solved) : 후반부에 정말 열심히 생각했는데, set으로 넣었다 뺐다 하며 계산하는 문제라는 점은 알았지만 결국 구체적인 식을 구해내지 못했다.

C (P5, solved by leo020630) : 각 정점별로 차원을 하나 추가하자. 금지된 경로를 잘 따라온 경우와 그렇지 않은 경우로 나누면 된다. 케이스워크를 꼼꼼히 해야 하니 조심해서 구현해주자. 좋은 다익스트라 응용문제라고 생각한다.

D (R5, Not solved) : 문제를 읽지 않았다. 대회 중간에 petamingks가 엄청 어렵다고 한 점만이 기억난다.

E (D5, Not solved) : 슬쩍 보았지만 풀이의 감도 잡지 못해 놓아두었다. 풀이를 들었을 때 정말 놀랐다. 나만 몰랐는지는 모르겠지만.. 굉장히 좋은 문제인 것 같다.

F (D5, solved by leo020630) : 풀이의 상당 부분은 위에 잘 적어두었다. 정해는 상당히 어렵고, 메모리 제한이 늘어난 이후에는 굉장히 다양한 풀이가 나왔다고 한다.

G (P4, solved by minsung05) : 증명이 어려운 그리디 문제라고 한다.

H (P2, solved by petamingks) : 상당히 까다로운 수학 문제로 보이는데, petamingks가 빠른 시점에 잘 풀어주었다.

I (D5, Not solved) : 정말 열심히 생각했지만, trivial한 점화식에 비해 최적화 방법이 잘 떠오르지 않았다.

J (D4, Not solved) : 중간에 petamingks가 열심히 보던데, 별 다른 성과를 얻지 못했다. 전체 0솔 문제니 그럴 만 하다고 생각한다. 출제자분이 굉장히 슬퍼하시던데.. 안타깝다.

K (D3, Not solved) : 문제를 제대로 읽지 않았다.

L (G1, solved by leo020630) : 놀랍게도 가장 쉬운 문제이다. 답의 성질을 알아내는 것은 비교적 쉽고, 분할 정복 느낌으로 구현해주면 되는데 까다로운 부분이 있을 수 있다. 나는 그냥 O(1) RMQ를 박아서 예외 케이스를 최대한 줄였다.

M (P4, Not solved) : 구현이 까다로운 문제인 것 같다. 문제를 제대로 읽지 않았다.

 

느낀 점

등수는 목표만큼, 오히려 더 괜찮게 나왔다. 실제로 예선 등수에서 10등 이상 올랐는데, 충분히 더 잘할 수 있었을 것이라 생각해 아쉬움이 남는다. 후배들도 제 몫을 충분히 다 해주었고, 나는 3문제를 풀긴 했으나 2개가 가장 쉬운 문제이다. 나름 자료구조를 괜찮게 한다고 생각해 F를 푼 것 까지는 좋았지만, 모두 자료구조 문제인 B, I를 하나도 풀지 못한 것은 약간 아쉬웠다. 다행인지 불행인지 셋의 난이도가 정말 어려운 탓에 말린 팀들이 많은 것 같다. 실제로 작년 월파와 비교를 해 보았을 때 크게 밀리지 않는다. 실제로 위를 보면 스코어보드를 따라가느라 제대로 읽지 못한 문제가 많다는 사실을 알 수 있다. 스코어보드를 무시하고 문제를 공략하는 능력도 필요한데, 이런 게 되는 팀은 정말 소수인 것 같다. 또한 이런 셋에서 8솔 이상을 해낸 팀이 저렇게 많다는 사실이 다시 한 번 놀라웠다. 이런 괴물들 사이에서 오렌지-퍼플-블루로 수상권 근처까지 갔으니 선방이긴 한데, ICPC에서도 좋은 결과를 내려면 연습을 더 열심히 해야할 것 같다.

 

대회 결과 외적으로는 역시 몇 없는 온사이트 대회인 만큼 즐거웠다. 운영진 분들이 굉장히 공을 들인 느낌이 여실히 들었다. 올해는 작년과 달리 포스텍 사람들도 본선에 많이 와 덜 외롭게 대회를 칠 수 있었던 것 같다. 매년 열어주세요 감사합니다~