UCPC 2023 예선 간략한 후기

전대프연 스탭을 하려다가 너무 바빠서 계획을 취소했기 때문에 올해는 참가자로 나왔습니다. 작혼우인전3of4너만오면고 팀으로 @havana723, @ydk1104 님과 함께 출전했고, 7문제를 풀었습니다(ABCDHIK).

저희 전략은 구현이 빠른 제가 구현을 다 하고, 제가 구현을 하는 동안 다같이 풀이를 생각하는 거였습니다. 간략한 풀이와 대회 중에 있었던 일 등을 소개합니다.

A. 체육은 코딩과목 입니다

+, 86초(페널티 1분). B4.5, #implementation, #arithmetic

@shiftpsh가 사이트가 열리자마자 보고 풀었습니다. UCPC 예선은 항상 첫 문제가 가장 쉬운 문제입니다.

북쪽을 기준으로 오른쪽으로 얼마나 많이 돌았는지를 저장합시다.

왼쪽으로 $90$도 돈다는 건 오른쪽으로 $270$도돈다는 것과 같으니까, $t_i$들을 다 더하고 $4$로 나눈 나머지를 보는 것만으로 충분합니다. 이 값이 $0$이면 그대로 북쪽입니다. 가장 시간이 오래 걸린 부분은 오른쪽이 동쪽이 맞는가가 생각이 바로 안 났던 부분인 것 같습니다.

저는 A를 풀고, H가 쉬워 보인다는 의견에 H를 잡으러 갔습니다.

D. 더 흔한 타일 색칠 문제

+, 26분(페널티 26분), S3, #implementation, #greedy

@havana723이 스코어보드를 보고 쉬운 문제라고 보고 잡았고, 바로 풀었습니다.

각 $K\times K$ 영역의 $i$행 $j$열에 나오는 문자를 봅시다. 모든 영역들에 걸쳐 어떤 문자가 몇 번씩 나왔는지 보고, 가장 많이 나온 문자로 바꿔 주면 됩니다.

처음에 D 지문의 형태를 보고 호락호락하지 않을 거라고 생각하고 넘어갔는데, 쉬운 문제였습니다.

I. 자석

+, 29분(페널티 29분), S1, #ad_hoc

@shiftpsh가 H를 보다가 좀 아닌 것 같아서 많이 풀린 I를 봤고, 바로 풀었습니다.

S극을 N극에 왼쪽에 놓는 경우는 그냥 배열을 뒤집어 놓고 N극을 왼쪽에 놓는 경우와 같으므로, 일반성을 잃지 않고 N극을 왼쪽에 놓는 경우만 생각하면 됩니다.

N극을 $i$번 위치에, S극을 $j$번 위치에 놓는다고 생각해 보면 변화량은 $a_i-a_j+K(j-i)$만큼입니다. $K(j-i)$ 부분이 없다면 $i$번째 위치 이전까지의 최댓값을 전처리하는 변수 $mx$를 만들어서 다음과 같은 알고리즘으로 쉽게 구할 수 있습니다.

for i = 0..n - 1
    answer = max(answer, mx - a[i])
    mx = max(mx, a[i])

$K(j-i)$ 부분이 문제인데, \[a_i-a_j+K(j-i)=(a_i-Ki)-(a_j-Kj)\] 로도 쓸 수 있습니다. 따라서 새로운 배열 $b_i=a_i-Ki$를 만들어 놓고 $b$에 대해서 위의 알고리즘을 돌리면 됩니다.

K. 세미나 배정

+, 52분(페널티 52분), G3, #parametric_search, #greedy

풀이를 @ydk1104가 냈고, 그걸 @havana723이 구현했습니다.

세미나 수의 최솟값에 대해 이분 탐색을 합시다. 최솟값을 고정하면 스케쥴이 만족 가능한지는 그리디하게 판정할 수 있습니다.

제가 문제를 안 봐서 잘 모르기는 합니다만, 팀원 분들의 의견에 의하면 이분 탐색에서 그리디하게 판정하는 과정에서 off-by-1 등 디테일하게 신경쓸 부분이 많았다고 합니다. 저는 그 동안 C를 짜고 있었습니다.

C. 차량 모듈 제작

+, 60분(페널티 60분), G3, #geometry, #mst, #greedy

@shiftpsh가 처음에 보고 구현이 복잡해 보여서 넘겼는데, 나중에 와 보니 그렇게 어렵지 않은 문제인 것 같아서 풀었습니다.

기어가 몇 개 안 됩니다. 기어를 노드로 생각하고, 기어와 기어를 연결하는 벨트의 길이를 비용으로 하는 $1\,000^2$짜리 완전 그래프가 있다고 생각할 수 있겠습니다. 벨트가 없어도 되면, 즉 기어와 기어가 접해 있거나 겹쳐 있다면 이 비용은 $0$입니다. 결국 최소 비용으로 모든 노드를 연결되게 해야 하는 문제가 됩니다. 이는 그래프에서 최소 신장 트리를 구하고, 모든 간선의 비용의 합을 구하는 것으로 해결할 수 있습니다.

벨트가 있을 때와 없을 때의 간선의 비용 차이는 많이 크기 때문에, 포함 관계 판정은 정확하게 해야 합니다. 포함 관계는 보통 두 원 사이의 거리 $d$가 두 원의 반지름의 합 $r_1+r_2$보다 큰지 작은지로 판정하는데, $d$는 정수로 표현하지 못하는 경우가 있을 수 있습니다. 다만 두 원 사이의 거리의 제곱 $d^2$는 정수로 표현 가능하므로, $d$와 $r_1+r_2$을 비교하는 대신 $d^2$와 $\left(r_1+r_2\right)^2$를 비교해 주면 됩니다.

벨트의 길이를 구하는 건 삼각함수에 대한 이해가 어느 정도 필요합니다. 위의 그림에서 벨트의 길이를 구하려면 $t$와 $\theta$의 값을 구해야 합니다.

일단 편의를 위해 $r_1<r_2$라고 합시다. 그리고 $\Delta r=r_2-r_1$로 둡니다. 그러면 피타고라스의 정리에 의해 \[t=\sqrt{d^2-\Delta r^2}\]가 됩니다.

$\theta$는 \[\cos^{-1} \frac{\Delta r}{d}\quad\text{또는}\quad\tan^{-1}\frac{\Delta r}{t}\]로 계산할 수 있습니다.

왼쪽 원의 호의 중심각은 $\pi-2\theta$고, 오른쪽은 $\pi+2\theta$입니다. 호의 길이는 중심각 곱하기 반지름의 길이이므로, 정리해 보면 벨트의 총 길이는 이렇게 됩니다. \[L = r_1\left(\pi-2\theta\right)+r_2\left(\pi+2\theta\right)+2t.\]

B. 물류창고

+1, 95분(페널티 115분), P3, #mst, #disjoint_set, #smaller_to_larger

모두가 머리를 맞대고 풀이를 생각했고, @shiftpsh가 구현했습니다. MST 아이디어는 @shiftpsh가, smaller to larger 아이디어는 @havana723이 생각했습니다.

첫 번째 관찰은 간선이 $M$개까지 필요하지 않을 수도 있다는 사실에 기반합니다. 상한이 작은 간선 몇 개는 절대 선택되지 않을 수도 있습니다. 조금 더 생각해 보면 주어진 그래프의 최대 신장 트리를 구하면 이 간선들만이 선택됨을 알 수 있습니다.

그러면 이제 문제 상황을 그래프가 아니라 트리로 줄여볼 수 있습니다. 이제 모든 노드의 쌍에 대해 경로의 상한의 합을 구해야 합니다.

두 번째 관찰은 문제를 작은 문제로 쪼개는 것에서 시작할 수 있습니다. 트리에서 가장 상한이 낮은 간선을 지나는 경로들을 생각해 봅시다. 이 간선을 지우면 트리는 두 개로 나눠질 것입니다(트리니까요). 각 색깔에 이 간선이 영향을 주는 경로는 대해 두 개로 나눠진 트리에서 해당 색깔을 가지는 노드의 수를 곱한 것만큼 있을 겁니다. 가장 작은 노드 순서대로 끊어 주면서 트리를 두 개로 쪼개고, 각각의 트리에서 문제를 해결할 수 있겠습니다.

그러나 일자 그래프에서 양 끝 노드들만 계속 삭제하는 상황을 생각한다면, 색상이 최대 $50\,000$개 존재할 수 있으니 여전히 굉장히 느리겠습니다.

여기서 트리를 작은 간선부터 끊어 주는 아이디어 대신 큰 간선부터 이어주는 아이디어를 생각해볼 수 있습니다. DSU를 하나 만들고, DSU 트리의 루트마다 (색상, 노드 개수)의 map을 sparse하게 관리해 줍시다. DSU에서 merge 연산을 할 때 무조건 작은 트리를 큰 트리에 붙여 주면서 작은 노드의 map에 있는 원소들을 큰 노드의 map에 누적해 줍니다. 이 테크닉은 smaller to larger라는 이름으로도 불리며, $50\,000$개의 색상의 노드가 $2$개씩 있는 최악의 경우에라도 $\mathcal{O}\left(n \log n\right)$ 정도밖에 안 걸리게 됩니다.

H. 팔찌

+4, 177분(페널티 257분), P1, #ad_hoc, #constructive, #stack

모두가 머리를 맞대고 풀이를 생각했고, @shiftpsh가 구현했습니다. Circular와 reflection이 상관이 없다는 중요한 관찰을 @ydk1104가 해 줬습니다.

첫 번째 관찰은 1번 쿼리와 2번 쿼리는 정확히 서로 반대의 역할을 한다는 점에서 착안합니다. 어떤 문자열 $A$를 어떤 과정 $r$을 거쳐 $A^\prime$으로 만들 수 있다면, 반대의 과정 $r^{-1}$로 다시 $A$로 만들 수 있습니다.

이 점을 이용해서, 주어진 두 개의 문자열 $A$와 $B$를 똑같은 문자열 $X$로 만들 수 있는지 봅시다. $A$에서 $X$로 가는 과정을 $r_A$, $B$에서 $X$로 가는 과정을 $r_B$라고 한다면, $A$에서 $B$로는 $r_Ar_B^{-1}$ 순서대로 실행하는 것으로 가능합니다.

일단 circular한 구조는 항상 linear하게 펼치고 생각하는 게 좋기 때문에, $1$번 구슬과 $N$번 구슬을 합치는 경우는 없다고 생각합시다.

두 번째 관찰은 어떤 문자열에 $1$번 연산을 가능한 한 많이 사용하면 똑같은 문자가 반복되는 형태로 만들 수 있다는 것입니다. 입력으로 받은 문자열을 순회하면서, 스택 구조를 활용해서 다음 알고리즘을 돌려 줍시다.

stack = []
for c in str
    emplace c to stack
    while length of stack >= 2
        if last two characters of the stack is same
            break
        else
            discard top two elements of the stack
            emplace the result of the 1st query to the stack

세 번째 관찰은 같은 문자가 반복되는 문자열은 홀짝성을 유지하면서 길이를 바꿀 수 있다는 것입니다. 아래는 길이를 $2$ 줄이는 연산에 대한 예입니다.

• RRR / R → GB
• RRGB / RG → B
• RBB / RB → G
• GB / GB → R

첫 번째 관찰에 의해 위의 연산들을 역으로 실행해 주면 길이를 $2$ 늘릴 수도 있습니다. 종합해 보면 모든 문자열은 R, G, B, RR, GG, BB 중 하나로 줄일 수 있습니다.

네 번째 관찰은 RR, GG, BB를 서로 바꿀 수 있다는 것입니다.

• RR / R → GB
• RGB / RG → B

하지만 R, G, B를 서로 바꿀 수는 없습니다, 또한, 예를 들어, R을 RR로 만들 수 없습니다. 어떤 연산을 하더라도 R, G, B에서 어떤 두 색깔을 고른 것의 개수의 합의 홀짝성을 바꾸지 않기 때문입니다.

이 관찰을 종합하면, 다음 중 한 가지 경우에만 문자열을 바꿀 수 있습니다.

• 두 문자열 모두 R, G, B 중 하나로 줄일 수 있고, 줄어든 문자열 두 개가 같은 경우.
• 두 문자열 모두 RR, GG, BB 중 하나로 바꿀 수 있는 경우. 줄어든 문자열 두 개는 달라도 됨.

이제 이걸 어떻게 circular하고 reflective하게 바꿀 수 있는지 생각해 봅시다. 그런데 모든 문자열들은 R, G, B, RR, GG, BB로 만들 수 있고, 이들은 이미 circular하고 reflective하기 때문에 크게 상관이 없을 것 같습니다. 이 방법으로 그냥 linear하게 해결하면 됩니다.

구현이 꽤 힘들었고, 구현 미스로 4번 틀렸습니다. 안타깝네요.

F. 응원단

시도하지 못함, P2, #ad_hoc

다른 사람들이 H번 구현에 고통받는 동안 @havana723이 풀이를 열심히 생각했습니다. 구현도 어느 정도 했지만 안타깝게도 시간 내에 제출하지는 못했습니다.

자리를 바꾸는 경우를 제외하고 생각해 봅시다. 셀을 4가지 경우로 나눌 수 있습니다.

• 행이 홀수, 열이 홀수
• 행이 홀수, 열이 짝수
• 행이 짝수, 열이 홀수
• 행이 짝수, 열이 홀수

어떤 셀이 모든 쿼리를 거치고 얼마나 이동해 있는가는 이 4가지 경우 안에서 전부 같다는 관찰이 가능합니다.

쿼리를 온라인으로 처리하면서, 각각의 경우에 대해 처음 시작 위치에서 얼만큼 이동했는지를 관리합시다. $\left(r, c\right)$에 어떤 값이 저장되어 있는지를 알고 싶다고 합시다. 4가지 경우 각각에 대해 $\left(r, c\right)$에서 이동 벡터를 빼 보고, 그게 실제로 처음에 각 경우의 맞는 셀의 위치에 있는지 확인합시다. 맞는 경우는 한 가지밖에 없을 것입니다. 그 경우에 대해, 초기 배열에 $\left(r, c\right)$에서 이동 벡터를 뺀 곳에 있던 값이 현재 $\left(r, c\right)$에 있는 값이 됩니다.

교체 쿼리의 처리를 위해 별도의 배열 swap을 관리합시다. Swap 쿼리가 나오면 그 때의 $\left(r_1, c_1\right)$, $\left(r_2, c_2\right)$ 값을 계산하고, 이 값을 swap 배열에서 바꿔 줍시다. 최종 출력에서 swap 배열에 있는 값을 출력해 주면 됩니다. 사실 swap 쿼리는 $\left(r_1, c_1\right)$과 $\left(r_2, c_2\right)$의 값을 구하는 쿼리와 크게 다르지 않은데 어느 정도 정해로 접근하는 데 연막의 기능을 했다고 생각합니다.