UCPC 2020 예선 후기

안타깝게도 서버가 터지는 바람에 마라톤 대회같은 형식으로 진행됐다. 문제가 전반적으로 퀄리티가 높았고 재밌었는데 예기치 못한 사고로 인해 정상적으로 운영되지 못한게 안타깝다. 4문제만 풀면 본선 진출이었지만 그래도 최대한 열심히 문제를 푸는게 출제자 분들에 대한 예의일 것 같아 최대한 열심히 풀었다. 그리고 전반적으로 문제가 꽤 어려웠던 것 같은데 다들 굉장히 잘 풀어서 놀랐다. 확실히 사람들의 평균적인 실력이 많이 높아졌다는게 체감된다.

 

딱히 시간 제한이 없었던 대회라(+4solve만 하면 통과였다보니) 스코어보드가 딱히 의미가 있는 것 같지는 않지만, 아무튼 시간 중에는 7솔브 29등으로 예선을 통과했다.

 

아래는 내가 푼 예선 문제들을 난이도 순으로 정리해 본 것.

 

A. 수학은 비대면 강의입니다.

단순히 모든 x, y에 대해 주어진 연립 방정식을 다 체크해보면 풀린다. 이렇게 안하고 O(1)에 처리해보려고 식 정리를 해서 냈다가 두 번 틀리고 그냥 brute-force로 풀었다.

G. 루머

위상정렬 구현하듯이 내 주변 인접한 정점 중 루머가 퍼진 정점이 몇 개가 있는지를 갱신하면서 퍼지는걸 계산해주면 된다. 기본적인 그래프 응용 문제고 비슷한 유형을 풀어봤다면 어렵지 않게 해결할 수 있다.

D. ㄷㄷㄷㅈ

기초적인 트리 DFS 문제다. 지문이 너무 재밌어서 좋았던 문제. 역시 비슷한 유형의 문제를 풀어봤다면 어렵지 않게 해결할 수 있는 문제다.

F. 전투 시뮬레이션

매년 한 문제씩은 있는, 난이도가 높다기보다는 구현이 어려운 문제. 문제에서 주어진 조건을 충실하게 이행해서 구현하면 된다. 제한이 크지 않아 매 쿼리마다 일일히 최단거리를 구해줘도 충분히 시간 안에 동작한다.

H. 사과 나무

개인적으로 굉장히 약한 유형이라 풀면서 엄청 고생했다. 주어진 문제의 연산을 적절히 여러 케이스로 분리해서 케이스별로 어떻게 동작해야하는지를 정리하면 풀 수 있는데, 항상 이런 케이스 정리에서 몇 군데를 빼먹거나 잘못 생각해서 한참 고생하게 된다. 혹은 더 쉬운 풀이가 있는건가 싶기도 한데 그것도 잘 모르겠다.

 

끝나고 풀이 보니 엄청 단순한 문제였는데 말려서 그런건지 내가 그냥 못한건지 잘 모르겠다. 이번 예선은 유달리 많이 말린 것 같은데..

J. 역학 조사

엉뚱한 풀이로 한참 고생하다 다른 문제 풀고 오니 제대로 된 해법이 생각나서 맞췄다. 분명히 유사한 사고 방식을 사용하는 문제를 예전에 몇 번 풀어 본 적이 있었는데, 너무 오랜만이라 엄청 헤맨 것 같다. 풀이 방향을 처음에 잘못 설정하면 말리기 굉장히 쉬운 문제. 하지만 처음에 발상을 제대로 하면 맞추기 쉬운 문제이기도 하다.

 

 "초기 감염자"를 찾아야 해서 앞에서부터 시간순으로 생각하려고 하게 되는데, 그게 아니라 시간 역순으로 되짚어가면서 초기 감염자일 수 없는 사람을 제거하는 방식으로 해결하면 간단하다. "최종 감염자와 최종 감염자가 아닌 사람"이 섞인 모임에 참여한 모든 사람은 초기 감염자가 될 수 없고, 이런 식으로 감염자들을 지워나가다보면 초기 감염자일 수 있는 사람들만 남는다. 이 사람들을 초기 감염자라고 가정하고 시뮬레이션한 뒤 결과가 같은지 체크해주면 간단하게 구현할 수 있다.

E. 감자 농장

 풀이 아이디어가 어렵다기 보다는 구현이 어려운 문제다. 문제에서 주어진 조건을 잘 분류해보면 바위를 기준으로 구간이 나뉜다는 걸 알 수 있는데, 양쪽이 다 바위로 막힌 구간은 쉽게 해결할 수 있다. 이제 한쪽만 바위가 막혀 있는 구간 or 양쪽다 바위가 없는 구간에 대해서 총 몇개의 감자를 캐는지 + 얼마의 시간이 걸리는지를 계산해주면 된다. 이 때 각 구간별로 그 구간에 속한 감자의 위치를 다 배열에 정렬된 상태로 저장해두면, 주어진 x에 대해 이분 탐색으로 그 x의 오른쪽에 있는 감자 개수, 왼쪽에 있는 감자 개수를 알 수 있다. 

 

이렇게 양쪽 각각에 대해 감자 개수를 알고 있으면 좌우로 몇 번 방향을 전환하면서 움직이는지 횟수도 계산 가능하다. 이 횟수를 계산하고 나면 부분합을 응용해서 이동 거리가 얼마인지도 계산할 수 있다. 이 식들을 전부 잘 세워서 구현하면 AC를 받는다. 시간 복잡도는 O(N+QlogN) 정도가 된다. 구현 과정에서 적절히 여러 번 이용되는 로직들을 함수로 분리하면 그나마 실수할 확률이 줄어든다. 

 

예선 막바지에 I를 겨우 풀고 나서 E 풀이를 고민했는데, 풀이는 금방 생각났지만 구현이 워낙 오래 걸리는 문제라 대회 중에는 해결하지 못했다. 끝나고 나서 Open Contest에서 AC.

I. 인버스 ㄷㄷㄷㅈ

개인적으로 이번 예선에서 제일 재밌었던 문제. 처음 접근부터 상당히 어려운 Constructive 문제다. 가능한 트리의 형태가 워낙 다양하다보니 초점을 잡기가 힘들다. 이렇게 답의 형태가 엄청 다양한 문제는 적당히 제약을 걸어서 '특정한 형태의 트리'만 고려해도 문제를 해결할 수 있는지 확인해보는 식으로 접근하는게 좋다.

 

 더 좋은 패턴이 있을 것 같은데 나는 사실 좀 복잡하고 지저분하게 해결했다. n >= 15 케이스에서는 항상 답을 구할 수 있는 패턴을 찾아서 이 경우는 간결하게 해결했고, n < 14 인 경우는 적당히 형태를 한정한 후 brute-force로 해결했다. 이 brute-force가 n = 14일 때의 답을 못 찾아서 n = 14는 손으로 찾아서 해결한 걸 집어넣어서 AC. 예선 끝나기 직전에 시간이 없어서 이렇게 했는데, n = 14일 때 손으로 해결한 케이스를 잘 일반화해야하는게 아닌가 싶다. 나중에 좀 더 고민해볼 생각.

 

 아무튼 내가 접근한 패턴은, 일자로 된 트리를 하나 만들고, 이 일자 트리의 노드 중 몇 개를 골라 그 노드에 좌우로 노드를 몇 개 덧붙여보는 형태였다. 이렇게 하면 일자 트리의 특정 노드에 다른 노드를 추가했을 때 ㄷ, ㅈ 모양의 개수가 어떻게 변화하는지를 식으로 정리할 수 있는데, 이 상태에서 경우를 잘 찾아보다 답을 만들 수 있는 패턴을 유도했다. 

고민의 흔적.. 이렇게 트리 그리는걸로만 노트 10페이지는 넘게 쓴 것 같다.

C. 삼항 연산자

개인적으로는 I가 C보다 좀 더 어려운 거 같기도 한데 잘 모르겠다. 비슷한 난이도인가 싶기도 하고. 파싱 및 Union-Find 응용에 대한 이해가 있으면 풀 수 있다.

 

주어진 식을 잘 파싱했다고 가정하면, 조건식이 항상 두 변수에 대해 그 x==y 꼴로 주어지는데, 이게 참인 경우 x랑 y가 결과적으로 같은 값을 가져야하고 거짓인 경우 x랑 y가 다른 값을 가져야 한다. 그러나 어느 경우든 x값이 결정되면 y값도 같이 결정되므로 둘을 같은 컴포넌트로 생각할 수 있다.

 

이제 조건이 참인 경우 x랑 y를 같은 그룹으로 묶어주고(union-find 이용), 거짓인 경우 다른 그룹으로 묶어준 뒤 해당 경우의 expr을 다시 체크한다. 그룹으로 묶는 과정에서 모순이 발생하는 경우 해당 expr로 가는 경우가 존재하지 않는다는 의미이므로 이 경우는 패스.

 재귀적으로 같은 과정을 반복하다 마지막 노드에 도달하면, 그 노드에서 컴포넌트 개수를 계산한다. 0 혹은 1이랑 묶인 컴포넌트의 경우 값을 바꿀 수 없으니 제외하고, 그 외의 경우는 컴포넌트 단위로 1혹은 0 값을 자유롭게 설정할 수 있는 게 되므로 2^(컴포넌트 개수)를 답에 더해주면 된다. 조건식을 타고 내려갈 때 해당 조건식이 true인 경우와 false인 경우는 절대 겹치는 케이스가 없으므로(겹친다면 true이면서 false가 되는 조건식이 있다는 이야기인데 이건 말이 안됨) 이런 방식으로 해결할 수 있다.

 

 사실 이런 파싱 문제를 별로 좋아하지 않아서 최대한 나중에 잡았다. B부터 풀고 싶었는데 B를 풀 수가 없어서 일단 C부터 품.

 

B는 결국 못 풀었다. 나중에 풀이 보고 짜야지