2023 POSTECH Programming Contest Open

2023 POSTECH Programming Contest Open

A - 모범생 포닉스

단순 수학

00:01 AC

 

C - 이상한 배열

다음과 같이 배열 B와 set S를 정의하자.

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

S = {1, 2, 3, ..., N - 1, N};

그리고 배열 B는 오름차순으로 정렬해주자.

 

이제 정렬된 배열 B의 원소를 순회하면서 B[i].second를 S에서 제거하면 된다.

이때 S에서 B[i].second의 다음 원소를 가리키는 iterator를 it라고 하자.

B[i].first == B[i + 1].first인데 it == S.end()이거나 *it != B[i + 1].second이면 배열 A는 이상한 배열이 아니다.

00:08 AC

 

G - 대회 상품 정하기

수식을 정리한 후 그대로 계산해주면 된다.

구체적으로 i번째 상품의 개수는 ((X - N * A[M]) / (A[i] - A[M]))이 된다.

여기서 N은 남은 참가자의 수이고 1번째 상품부터 차례대로 계산하면 된다.

마지막으로 M번째 상품의 개수는 N이 된다.

00:17 WA

 

수식 계산 중 결과값이 N을 초과할 수 있다.

따라서 min((X - N * A[M]) / (A[i] - A[M]), N)과 같이 계산해야 한다.

00:20 AC

 

K - 회전초밥

모든 초밥 종류에 대하여 별도의 queue를 구성해주자.

00:29 AC

 

M - 약속 장소 2

S = "KNU"라고 가정하자.

가능한 문자열을 순서대로 나열하면 다음과 같다.

ANU -> ... -> JNU -> KAU -> ... -> KMU -> KNA -> ... -> KNT

-> KNU

-> KNV -> ... -> KNZ -> KOU -> ... -> KZU -> LNU -> ... -> ZNU

 

가능한 문자열의 개수는 (25 * N + 1)개이므로 위의 과정을 그대로 구현해주면 된다.

00:37 WA

사소한 구현 오류가 있었다.

00:38 AC 

 

N - 마지막 문제

배열 A를 정렬한 후 인접한 원소 사이의 간격 중 최댓값을 찾으면 된다.

00:42 AC

 

F1 - 단순한 그래프와 이상한 쿼리

SCON I번과 매우 유사한 방법으로 풀이할 수 있다.

SCON 리뷰 링크를 남긴다.

00:54 AC

 

J1 - 나무 타기

트리 dp

N 제한이 작기 때문에 가능한 모든 정점을 고려하는 O(N^2) 풀이가 가능하다.

01:06 AC

 

여기까지 잘 하고 말아 먹었다.

D번은 쉬워 보였는데 레버를 구현하다 보니 특정 정점에서 보물을 중복 획득하는 상황이 발생하였다.

E번도 쉬워 보여서 바로 구현에 들어갔는데 마지막 병합 과정을 O(N^3)에서 더 이상 줄일 수 없었다.

1시간 가까이 허비한 상황에서 스코어보드를 보고 L번을 잡았는데 그마저도 순탄치 않았다.

 

L - 라이벌

포함 배제 dp 문제이다.

이 문제를 풀면서 내가 얼마나 포함 배제를 못하는지 깨달을 수 있었다.

아무리 생각해도 식이 세워지지 않았고 오랜만에 멘탈이 붕괴되었다.

몇 번이고 처음으로 되돌아갔고 1시간이 넘어서야 식을 세울 수 있었다.

03:23 AC

 

생각을 조금만 바꾸면 보다 쉽게 문제를 풀이할 수 있다.

지문에서 핵심적인 부분은 "최소 한 영역에서 B의 능력치가 A의 능력치보다 높다면 A는 B를 라이벌로 설정한다"는 것이다.

다른 말로 표현하자면 "모든 영역에서 B의 능력치가 A의 능력치보다 낮거나 같다면 A는 B를 라이벌로 설정하지 않는다"는 것이다.

이렇게 생각하면 일반적인 포함 배제 문제와 같이 쉽게 해결할 수 있을 것이다.

 

H - 삼각형 모험

모든 정점은 최대 2개의 정점과 연결되어 있다.

그리고 각 연결 요소의 모양을 관찰하면 일자형 또는 사이클형으로 구분할 수 있다.

일자형의 경우 시작 정점 또는 끝 정점에서 dfs를 수행하면 된다.

사이클형의 경우 임의의 정점에서 동일한 작업을 수행하면 된다.

이렇게 적절히 전처리를 마쳤다면 각 query를 O(1)에 처리할 수 있게 된다.

구현이 조금 더러운 편이다.

04:08 AC

 

J2 - 나무 타기 (Hard)

J1과 동일한 점화식을 사용하되 이를 O(N)에 계산할 것이다.

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

B[i] = 깊이가 i인 정점에 대한 가중치

 

각 정점의 강도에 따라 배열 B를 업데이트하면 되는데 naive하게 하면 O(N^2)이 된다.

다행히 업데이트 구간은 항상 연속해 있으므로 이를 마치 누적 합처럼 관리할 수 있다.

현재 정점의 번호가 x이고 깊이가 d일 때 다음과 같이 배열 B를 업데이트할 수 있다.

B[d + 1] += 2 * B[d];

B[d + A[x] + 1] -= B[d];

(자식 정점 재귀 호출)

B[d + 1] -= 2 * B[d];

B[d + A[x] + 1] += B[d];

 

B의 초깃값은 B[0] = 1, B[1] = -1로 두면 된다.

B[d + 1]에 B[d]를 두 번 더하는 이유는 다음과 같다.

• 첫 번째로 B[d]의 누적 합을 B[d + 1]로 전파하기 위해서이다.
• 두 번째로 B[d]의 누적 합을 B[d + 1 ... d + A[x]]로 전파하기 위해서이다.

04:46 AC

 

B - 폭발 속에서 살아남기 (not solved)

Voronoi diagram 문제라는데 역시 기하는 믿고 거르고 도망가야 한다.

convex hull 풀이가 가능하다고 해서 완벽한 이해 없이 구현만 하였다.

 

D - 보물 사냥 (not solved)

레버가 없으면 매우 쉬운 scc 문제가 된다.

레버가 있다고 하여도 처음에는 그저 구현만 복잡해 보인다.

막상 구현하다 보면 보물의 중복 획득을 방지할 방법을 찾을 수 없어 풀이를 포기하게 된다.

 

레버를 당기지 않는 경우의 답은 쉽게 구할 수 있으므로 생략한다.

레버를 당기는 경우에는 모델링이 많이 복잡해진다.

먼저 각 정점 u를 u1과 u2로 분할하자.

그리고 간선 (u, v)에 대하여 (u1, v1)과 (u2, v2)를 추가해주자.

레버의 구현은 단순히 (a1, a2), (x2, y2), (y2, x2)를 추가하면 된다.

 

이제 보물의 중복 획득을 방지해보자.

정점 u에서 보물을 중복 획득할 수 있다는 것은 u1에서 a1으로 가는 경로가 존재하고 a2에서 u2로 가는 경로가 존재한다는 것이다.

그런데 u1에서 a1으로 가는 경로가 존재하면 u2에서 a2로 가는 경로도 존재하게 된다.

따라서 정점 u에서 보물을 중복 획득할 수 있다면 u2와 a2는 동일한 scc에 속하게 된다.

a2와 동일한 scc에 속하는 정점 u2에 대하여 u1의 보물 가치를 0으로 설정하면 보물의 중복 획득을 방지할 수 있다.

 

E - 지구평면설 (not solved)

먼저 h[1][1] * h[i][j] == h[i][1] * h[1][j]를 만족하지 않는 (i, j)가 존재하면 답은 -1이 된다.

a[2] = k * a[1]로 정의하면 a[i]는 다음과 같이 표현할 수 있다.

• a[2 * i - 1] = h[1][1] / h[i][1] * a[1];
• a[2 * i] = h[1][1] / h[1][i] * a[2] = h[1][1] / h[1][i] * k * a[1];

이때 a[2 * i - 1]과 a[2 * j]가 동일하려면 k는 h[1][j] / h[i][1]이어야 한다.

따라서 가능한 (i, j) 쌍에 대하여 (h[1][j] / h[i][1])를 계산한 후 최빈값의 개수를 구하면 문제를 해결할 수 있다.

 

F2 - 평범한 그래프와 이상한 쿼리 (not solved)

정해는 무슨 말인지 잘 모르겠다.

별해도 대강 감만 잡았는데 다음 생에는 확실하게 이해하려고 한다.

 

I - 분탕 (not solved)

핵심적인 관찰은 특정 구간 내에 다른 구간이 완벽하게 포함될 수 없다는 것이다.

다이아 조합론 문제답게 역시나 어려웠는데 덕분에 카탈란 수의 일반항 유도 방법은 확실하게 배울 수 있었다.

 

끝

끝