UCPC 2023 본선

UCPC 2023 본선

서론

라피신 때문에 후기가 많이 늦었다.

결과만 보자면 28등이라는 처참한 성적으로 마무리하였다.

그래도 예선 등수 41등보다 많이 올라갔고 사실상 1인 팀이었다는 것을 감안하면 조금은 위안이 된다.

팀원은 학교 친구인 bugsbunni22와 hyup98이다.

역할은 각각 라디오 1, 라디오 2였는데 덕분에 5시간 동안 지루하지 않았다.

5시간 동안 다양한 주제로 수다를 떨었는데 긴 시간 동안 잘 버텨주어서 너무 고마웠다.

 

PA - 풍선 수집

대회 시작 후 30분이 지났을 무렵 bugsbunni22가 갑자기 사라졌다.

뭔가 느낌이 싸해서 hyup98에게 그녀의 행방을 물어보니, 자기도 풍선 갖고 싶다고 풍선 구하러 갔단다.

당장 잡아오라고 하였는데 이미 스태프한테 저지당해서 돌아오는 길이었다.

풍선을 빨리 구하지 못한 내 잘못이다.

 

풀만한 문제를 뒤지다가 I번에 그리디 풀이를 시도하였고 WA를 받았다.

L번이 그나마 풀리고 있길래 L번을 잡았다.

 

L - 나무늘보

다음과 같은 배열 C를 정의하자.

C[i] = 후위 순회 결과에서 i가 등장하는 인덱스

 

배열 C를 이용하면 2263번과 유사하게 재귀적으로 풀이할 수 있다.

답은 2^(자식 정점이 유일한 정점의 개수)가 된다.

재귀를 돌리면서 순회 결과가 올바른지도 검사해야 한다.

감이 다 죽었는지 구현이 오래 걸렸다.

01:09 AC

 

C - 황혼

각 정점을 2개로 분할하면 dijkstra로 풀이할 수 있다.

01:31 AC

 

G - K번째 스페이드 찾기

누적 합을 이용하면 스탑을 외쳐야 하는 순간을 모두 구할 수 있다.

하지만 이 풀이는 아무리 봐도 O(N^2) 같아 보였고 연속된 하트를 건너뛰는 최적화를 추가해서 제출하였다.

02:06 RTE

최적화 과정에서 약간의 잔실수가 있었다.

02:08 AC

 

에디토리얼을 보니 최적화 없이도 O(N log N)이 보장된다고 한다.

경이로운 방법으로 이를 증명할 수 있는데 자세한 내용은 에디토리얼을 참고하자.

 

대회 종료까지 대략 3시간이 남았었다.

그리고 3시간 동안 한 문제를 겨우 푸는 기적 같은 실력을 보여주었다.

중간에 다른 문제들도 구경하였지만 감도 오지 않았다.

지금 보면 M번이 그나마 괜찮았는데 대회 중에는 아무리 읽어도 문제 이해가 되지 않아서 그냥 버렸다.

어차피 M번을 풀었다고 가정하면 H번은 시간 부족으로 못 풀었을 것이고 4솔이라는 결과는 변하지 않는다.

 

H - 피보나치 반반수열

규칙은 다음과 같다.

우선 n < 4인 n에 대하여 a_n = n이다.

a_4부터는 다음과 같이 구할 수 있다.

 

a_4 = 4라면 정의에 어긋나게 되고 a_4 = 5라면 a_5 = f_4 = 5가 되어 이 또한 정의에 어긋나게 된다.

따라서 a_4 = 6이 되어야 한다.

a_6 = f_4 = 5

a_5 = f_6 = 13

a_13 = f_5 = 8

a_8 = f_13 = 377

a_377 = f_8 = 34

a_34 = f_377 = -1

이런 식으로 -1이 나올 때까지 채워나가면 된다.

이 방법으로 a_87까지 구하면 된다.

 

a_88부터 아직 값을 구하지 못한 모든 항 a_n에 대하여 다음이 성립한다.

a_n = (n + 1) or (n + 2) or -1

필요할 때마다 적절히 계산해주면 된다.

03:44 WA

03:47 WA

 

무언가 오류가 있었는데 원인을 찾지 못하였다.

다행히 대회가 끝날 무렵 원인을 찾았는데 사소한 실수가 있었다.

위에서는 a_34 = f_377 = -1로 마무리하였는데 사실 이게 끝이 아니다.

a_34 = f_377 = -1

a_(f_377) = f_34 = 9227465

a_9227465 = f_(f_377) = -1

이를 해결하는 범용적인 코드는 작성하기도 어렵고 작성할 필요도 없다.

a_9227465 = -1로 예외 처리만 해주면 된다.

04:38 AC

 

남은 시간 동안 더 이상 풀 수 있는 문제가 없다고 판단하여 저녁 메뉴를 고르면서 짐 정리를 하였다.

M번까지 풀었으면 만족스러웠을 것 같은데 아쉽게도 실력이 많이 부족하였다.

 

M - 산 색칠 (not solved)

대회 중에는 지문 해석에 실패하여 풀이를 생각해보지도 않았다.

업솔빙 중에도 지문 해석에 실패하였고 에디토리얼을 보고 나서야 문제를 이해할 수 있었다.

 

그림의 히스토그램을 이루는 직사각형 중 양쪽 직사각형보다 높이가 높은 직사각형은 반드시 색칠하여야 한다.

이러한 직사각형들을 색칠할 수 있는지 확인하고 색칠할 수 있다면 색칠 결과가 그림과 동일한지 확인하면 된다.

구현량이 약간 많은 편이다.

 

I - 안테나 설치 (not solved)

다음과 같이 함수 f(i, j)를 정의하자.

f(i, j) = i번 집부터 j번 집까지 각각의 집에서 요구하는 네트워크 연결 속도를 제공하기 위한 안테나 하나의 최소 세기

이를 이용하면 다음과 같은 점화식을 세울 수 있다.

dp[j] = 1번 집부터 j번 집까지 각각의 집에서 요구하는 네트워크 연결 속도를 제공하기 위한 안테나 세기의 합의 최솟값

 

구체적으로는 다음과 같이 계산할 수 있다.

f(i, j) = max(A[i .. j]) + j - i

f(i, j) <= P를 만족하는 i의 최솟값을 x라고 할 때,

dp[j] = min(dp[i - 1] + f(i, j)), x <= i <= j

이는 O(N^2)이므로 최적화가 필요하다.

 

특정 상황에서 (dp[i - 1] + f(i, j))와 (dp[i] + f(i + 1, j))의 대소 관계를 비교해보자.

A[i] = max(A[i + 1 .. j]), 즉 A[i]가 구간 (i, j)에서 유일한 최댓값이 아니라고 가정하자.

앞선 정의에 따라서 f(i, j) = f(i + 1, j) + 1이다.

이때 dp[i - 1] < dp[i]이므로 다음이 성립한다.

dp[i - 1] + f(i, j) = dp[i - 1] + f(i + 1, j) + 1 <= dp[i] + f(i + 1, j)

따라서 A[i]가 구간 (i, j)에서 유일한 최댓값이 아니라면 (dp[i] + f(i + 1, j))는 고려하지 않아도 된다.

 

구간 (x, j)에서 최댓값이 바뀌는 인덱스를 각각 c_1, c_2, ..., c_k = j라고 하자.

이때 dp[j]는 다음과 같이 계산할 수 있다.

dp[j] = dp[x - 1] + A[c_1] + j - x;

for i = 1; i < k; ++i

    dp[j] = min(dp[j], dp[c_i] + A[c_(i + 1)] + j - c_i - 1);

여전히 O(N^2)이므로 추가적인 최적화가 필요하다.

 

set에 (dp[c_i] + A[c_(i + 1)] - c_i)를 저장하자.

set이 비어 있지 않다면 dp[j] = max(dp[j], *S.begin() + j - 1)을 수행하면 된다.

이제 set을 효율적으로 관리할 방법을 찾아야 한다.

 

A[c_i] > A[c_(i + 1)]이 성립한다는 사실에 주목하자.

이를 이용하면 c를 dq로 관리할 수 있다.

dq.front() < x라면 dq.pop_front()를 하고 set에서 해당하는 값을 제거한다.

A[dq.back()] <= A[j]라면 dq.pop_back()을 하고 set에서 해당하는 값을 제거한다.

마지막으로 dq.push_back(j)를 하는데 dq가 비어 있지 않다면 set에 해당하는 값을 삽입한다.

이렇게 하면 O(N log N)에 문제를 풀이할 수 있다.

 

F - 두 트리 (not solved)

두 트리에서 euler tour를 수행하고 순회 결과를 각각 in1, out1, in2, out2라고 하자.

다음과 같은 배열 B를 정의하자.

B[in2[i]] = {in1[i], A[i]};

그리고 배열 B를 이용하여 각 노드에 Segment Tree를 저장하는 기괴한 Merge Sort Tree를 구성하자.

이제 각 정점에 대하여 다음과 같이 신나게 query를 날리면 된다.

ans[i] = mergeT.query(in2[i], out2[i] + 1, in1[i], out1[i] + 1);

 

E - 격자 속의 직선 경로 (not solved)

모든 구역 (x, y)에 좌하단 방향으로 대각선을 긋고 이를 L(x, y)라고 하자.

그리고 L(1, 1)과 L(R, C)의 우상단 끝점을 잇는 직선을 uL, 좌하단 끝점을 잇는 직선을 dL이라고 하자.

 

다음과 같이 점 집합 A, B를 초기화하자.

A = {uL의 양쪽 끝점}, B = {dL의 양쪽 끝점};

설비가 설치된 구역 (x, y)에 대하여 L(x, y)가 uL과 교차한다면 집합 A에 L(x, y)의 좌하단 끝점을 추가한다.

마찬가지로 L(x, y)가 dL과 교차한다면 집합 B에 L(x, y)의 우상단 끝점을 추가한다.

 

각 집합에 속한 점들로 convex hull을 구성하자.

두 convex hull이 겹치거나 접하지 않는다면 조건을 만족하는 직선 경로가 존재한다.

 

B - I forgor 💀 (not solved)

필요한 턴 수는 (실패 횟수) + N이다.

실패 횟수를 구하기 전에 실패 카드를 정의하자.

어떤 카드가 실패 카드이려면 이전에 동일한 카드가 등장하지 않았고 다음 카드가 동일한 카드가 아니어야 한다.

 

실패 카드는 구간으로 표현할 수 있다.

실패 횟수는 각 구간에 대하여 ((구간의 크기 - 1) / 2 + 1)의 합이 된다.

set을 이용하여 구간을 잘 관리하면 문제를 해결할 수 있다.

 

A - 계통수 추론 (not solved)

Pass

 

D - 거대 로봇 전투 (not solved)

Pass

 

J - 회전초밥 (not solved)

Pass

 

K - 그건 가지가 아니라 대파예요 (not solved)

Pass

 

끝

9월에 열리는 SCPC 본선에서 만족스러운 결과를 받으면 이번 학기에 졸업하려고 한다.

그러면 이번이 마지막 UCPC가 될 것이고 망하면 졸업유예 박고 내년에도 참가한다.

졸업하게 해주세요.

끝