UCPC 2024 예선 후기

https://www.acmicpc.net/category/detail/4252

 

'금주 2주째라 창작활동에 문제있음' 팀으로 UCPC 2024에 출전했다. (10솔)

팀원은 junseo, thak00, nick832

 

A. 체육은 수학과목 입니다 

[+00:00:41, nick832]

 

직사각형 안에 최대한 큰 원을 넣으면 되는 문제.

50 * min(A, B)가 답이다.

 

여담으로 나의 이 문제 제출은 41초가 걸렸기에 퍼솔을 노릴만 했다.

하지만 실제 퍼솔은 +29초이고 나는 2번째...

어떻게 29초만에 A를 풀지?

 

J. 동전 쌍 뒤집기

[+00:32:57, thak00]

 

한 번 동전을 뒤집으면 홀수 번째와 짝수 번째의 같은 면 동전이 같이 뒤집히게 된다.

따라서 (홀수 번째의 뒷면의 수) = (짝수 번째의 뒷면의 수)가 성립해야만 한다.

 

이제 앞에서부터 뒷면을 향한 동전들을 보자.

현재 보고 있는 뒷면 동전이 L번째이고 다음 뒷면 동전이 R번째일 때

(L, R) 기우성이 다르다 : 사이에 있는 모든 앞면 동전을 뒤집고, 이들을 포함해서 또 전부 뒤집으면 된다.

-> (R - L)번의 조작이 필요

(L, R) 기우성이 같다 : 기우성이 다른 동전이 나올 때까지 진행

-> (L1, L2, L3, R1, R2, R3)과 같은 형태가 되고 (R1 - L3) + (R2 - L2) + (R3 - L1)번이 필요

-> 괄호 문자열과 비슷한 형태니 stack으로 뒷면 동전의 index를 관리해주면 된다.

 

E. 지금 자면 꿈을 꾸지만

[+00:34:59, junseo]

 

잠은 한 번만 잘 수 있으므로 과제 -> 잠 -> 과제의 순서로만 이루어지게 된다.

따라서 초반에 보는 과제를 개수 x, 잠을 자는시간 y만 결정되면, 과제 진행이 모두 결정된다.

x, y를 결정하는 경우의 수가 N * A이므로 모든 경우를 해보면 된다.

 

D. 이진 검색 트리 복원하기

[+00:35:30, nick832]

 

이진 검색 트리이므로 같은 depth에 존재한다면, 왼쪽에서 오른쪽까지 정렬된 순서로 존재할 것이다.

정렬 후 depth가 i인 애들을 depth가 i - 1인 애들의 left, right에 순서대로 삽입가능한지 체크해보면 된다

-> depth가 i - 1의 left, right을 모두 소모하고도 depth가 i인 애들이 남는다면 불가능

삽입가능한지는 다음을 확인한다

-> A 값이 left라면 나보다 더 작아야 하고, right면 더 크다.

-> mini를 관리하여, 나의 자식노드라면 무조건 mini 이상이어야 한다

-> maxi를 관리하여, 나의 자식노드라면 무조건 maxi 이하이어야 한다

 

이진검색트리이므로 내 왼쪽 아래의 노드는 모두 나보다 작아야 한다.

하지만, 처음에 문제를 착각하여 (나 -> 왼쪽 -> 오른쪽)으로 내려갈 때, 나보다 큰 노드가 나와도 되는줄 알았다.

패널티 쌓기의 귀재가 되어버렸다.

 

G. 석고 모형 만들기

[+00:50:15, thak00]

 

석고 모형을 (가로, 세로, 높이)로 각각 이등분하면 R * C * 8 조각으로 만들 수 있다.

그러면 H, I, O 또한 1 * 1 * 1 석고 모형을 적당히 4등분하는 것으로 생각할 수 있다.

-> 등분하지 않은 방향의 두 조각은 서로 연결되어 있다.

-> 같은 1 * 1 * 1에 속하지 않은, 가로, 세로 방향에 놓인 두 석고 조각은 서로 연결되어 있다.

이제 R * C * 8 조각을 이용하여 union find를 하든, dfs를 하든, bfs를 하면 최종 조각 수를 구할 수 있다.

 

H. 만보기 대행 서비스

[+01:17:13, junseo]

 

다음과 같은 네 케이스만 고려하면 된다. (왼쪽 끝을 L, 오른쪽 끝을 R이라 하자)

1) 0 -> L -> D만큼 이동 -> L -> R -> D만큼 이동 -> R -> 0

2) 0 -> L -> R -> D만큼 이동 -> R -> L -> 0

3) 0 -> R -> L -> D만큼 이동 -> L -> R -> 0

4) 0 -> L -> R -> L -> (D - (L + R))만큼 이동 -> L -> R -> 0

 

C. 미어캣

[+01:25:18, nick832]

 

제일 큰 미어캣이 어딘가 x에 위치하게 될 것이다.

그러면 x의 왼쪽에 있는 미어캣들은 R을 볼 수 없고, x의 오른쪽에 있는 미어캣들은 L을 볼 수 없다.

따라서 x의 왼쪽에는 제일 키가 큰 L들과 제일 키가 작은 R들을 배치한다

마찬가지로 x의 오른쪽에는 제일 키가 큰 R들과 제일 키가 작은 L들을 배치한다

[0, i]에 최대한 왼쪽을 보는 미어캣이 많도록 그리디하게 배치할 때 최대로 망을 보는 수를 cntL[i]라 하자.

-> 오른쪽을 보는 미어캣은 최대한 작도록 해주고, 왼쪽을 보는 미어캣은 이를 넘는 최소의 미어캣으로 해준다.

[i, N]에 최대한 오른쪽을 보는 미어캣이 많도록 그리디하게 배치한 것은 cntR[i]라 하자.

그러면 제일 큰 미어캣의 위치 x에 대해서 cntL[x] + cntR[x]값이 이 경우 망을 볼 수 있는 최댓값이다.

따라서 미어캣의 위치로 가능한 모든 지점에 대해서 MAX(cntL[x] + cntR[x])를 구해주면 된다.

 

조금 의아했던 점은 N = 5000인데 풀이가 O(NlogN)이다.

심지어 미어캣의 키가 permutation이여서 사실 정렬도 선형으로 가능하여, O(N)이 가능한 문제이다.

이거 때문에 풀이를 매우 여러 번 검사했다.

왜 상수를 이렇게 잡았는지 잘 모르겠다.

 

K. 나무 심기

[+02:16:26, nick832]

 

일단 보자마자 NO인 경우는 복숭아나무가 홀수개 인 경우이다.

인접한 쌍을 세면 (x, y), (y, x)로 두번씩 세지기에 무조건 짝수이기 때문이다.

 

우선 다음과 같이 두 줄 심는 것을 생각해보자.

-> 한 줄에는 x + y개의 씨앗을, 한 줄에는 y개의 씨앗을 차례대로 심는다 (x > 0, y > 0)

이 경우 사과나무는 x + 2개, 복숭아나무는 2y - 2개가 심어지게 된다.

따라서 우리는 A <= 2거나 B = 0인 케이스만 고려해주면 된다.

 

1. A <= 2 && B > 0

우선 다음과 같은 배치를 하면 사과 나무가 생기지 않는다 (A = 0)

.O.      . O .      . O .

.O.      OO.      OO.

           . O .      . OO

                        . O .

위와 같이 2개씩 늘려나가면 (0, 2K)를 만들 수있다.

이때 맨 마지막에 밑에 씨앗을 더 추가하면 A의 수를 늘릴 수 있다.

. O .

OO.

. O .

. O .  와 같이 배치하면 사과를 1개 추가할 수 있다.

 

2. B = 0

OO

OO 와 같이 배치하면 사과만 4개 얻을 수 있다.

여기에 우측 아래에 씨앗을 3개 더 심으면

OO

OOO

   OO와 같이 되고 사과를 7개 얻을 수 있다.

즉, 이렇게 3개씩 추가하는 방법으로 3N + 1개의 사과를 모두 얻을 수 있다.

OOO

O . O

OOOO

      OO 처럼 이렇게 하면 3N + 8개의 사과를 모두 얻을 수 있다.

OOOO

O . . O

OOOOO

        OO처럼 하면 3N + 12개의 사과를 모두 얻을 수 있다.

여기에 속하지 않는 (2, 3, 5, 6, 9)는 조금 노력해봐도 불가능할 것 같아 NO를 출력했다.

 

I. 민들레

[+02:44:23, nick832]

 

C x로 어떤 민들레가 x번 화분에 놓인다고 생각하자.

x번 왼쪽에는 L번 화분에, 오른쪽에는 R번 화분에 이미 민들레가 있다고 하자.

그러면 정확히 min(x - L, x - R)번 바람이 분다면, x번 화분의 민들레들은 L 혹은 R번 화분과 만나게 된다.

즉, 민들레가 놓이는 순간, 이미 언제 왼쪽과 오른쪽의 민들레와 병합될지가 결정된다.

 

현재 화단에 있는 '민들레 무리'의 개수가 cnt라 한다면, 바람이 불 때 총 민들레의 수는 정확히 cnt개 늘어난다.

즉, 항상 민들레 무리의 수만 관리해준다면, 총 민들레의 수를 구할 수 있다.

위에서 언급하였듯이 언제 병합되는지가 무조건 결정되기 때문에 놓일 때마다 cnt++, 병합될 때 cnt--해주면 된다.

물론 (L, x), (x, R)의 병합이 일어나면 (L, R)의 병합은 무효화해주는 것도 필요하다.

 

F. 두 배

[+02:58:44, junseo]

 

z algorithm으로 특정 자리에서 맨 앞에서부터 몇 자리와 같은지 확인해두자.

어떤 i번째 자리에서 '두 배'가 되었다고 생각하자.

그러면 즉시 문자열이 길이가 2i + 1이 될 것이다.

하지만, T와 일치하지 않는 부분은 반드시 지워주어야 한다.

즉 i + min(i, z[i]) 만큼의 길이만 살려둘 수 있다.

단, z[i] >= i이고, c = T[2i + 1]이라면, 하나도 지우지 않을 수도 있다.

 

따라서 다음과 같이 T의 각 부분을 연결해줄 수 있다.

-> (i -> i + 1), (i -> i - 1), (i -> i + min(i, z[i])), (i -> 2i + 1)

여기서 다익스트라를 쓰면 필요한 최소 입력을 구할 수 있다.

 

준서는 무슨 해싱 + 이분탐색 + 다익스트라를 했다고 한다

해싱과정에서 RTE를 내서 이를 찾느라 12번 패널티를 쌓았다.

뭐 시간내에 풀었으면 된거지

 

B. Two trees, twelve forests

[unsolved]

 

문제 형태부터 벌써 어지러워서 대회 중에는 그냥 읽지도 않았다.

분명 어제만 해도 D3였는데 고수들이 D5로 내려놨다.

 

 

전체적으로 나쁘지 않은데 패널티가 좀 끔찍하다.

여느 팀이든 비슷하지만 모든 패널티를 없애버리면 10솔 1등이 될 수준이니..
D는 문제를 잘못 읽고 말리고, C가 선형 풀이가 나와서 조금 오래 끌기도 했다

그리고 다들 자기가 읽은 문제를 그냥 풀어버려서 팀적으로 피드백할게 있나 싶다.

아무튼 본선은 나갈 거 같으니 그때는 잘 해보는거로.