겨울 숲의 초대

겨울 숲의 초대

A - 눈 치우기

시뮬레이션

00:03 AC

시뮬레이션 없이 수학적으로 답을 구할 수 있다.

답은 max(maxv, (sum + 1) / 2)이 된다.

 

C - 별꽃의 세레나데 (Easy)

조금 어이 없게 풀었다.

그냥 아무 식이나 때려 맞춰보다가 예제가 나오길래 제출하였다.

00:06 AC

기댓값은 확률의 역수라는 사실을 알고 있다면 쉽게 공식을 구할 수 있다.

 

B - 은나무

특수한 모양의 트리에서 lca의 깊이를 구하는 문제이다.

파란색 노드의 전체 개수는 (K + 1)^H - 1개이다.

이보다 A 또는 B가 크다면 답은 -1이 된다.

A와 B가 동일하다면 답은 0이 된다.

 

이외의 경우 lca는 항상 흰색 노드이다.

O(N) lca 알고리즘처럼 노드의 깊이를 맞춰준 후 A와 B가 동일한 노드가 될 때까지 부모 노드로 이동하면 된다.

초기에는 A와 B 모두 파란색 노드이므로 각 노드마다 최소한 한 번은 이동이 필요하다.

 

흰색 노드에 번호를 붙이는 것이 상당히 까다롭다.

흰색 노드의 번호는 파란색 자손 노드 중 가장 작은 번호를 사용하자.

하지만 이렇게 하면 여러 노드가 동일한 번호를 가지게 된다.

해당 노드들의 깊이는 모두 상이하므로 번호와 깊이를 동시에 관리하면 된다.

 

편의를 위하여 노드의 번호가 0부터 시작한다고 가정하자.

x번 노드의 깊이가 h일 때 부모 노드의 번호는 다음과 같이 구할 수 있다.

par = x - x % (K + 1)^(H - h + 2);

01:10 AC

 

D - 생산 시스템 관리

다음과 같은 점화식을 세울 수 있다.

dp[i][j] = 기계 1..i에 대하여 총 비용을 j 이하로 사용하였을 때 P의 최댓값

각 상태 전이 횟수는 100번 미만이므로 시간 내에 문제를 해결할 수 있다.

01:29 WA

역추적 과정에서 실수가 있었다.

01:31 AC

 

이후 E번과 F번을 시도하였다.

E번은 기댓값의 개념을 잘 몰라서 풀 수 없었다.

대회 중에는 C번의 풀이조차 이해하지 못하였다.

F번은 답에 근접하였으나 증명에 실패하였다.

 

E - 별꽃의 세레나데 (Hard) (not solved)

dp 문제처럼 보였지만 도저히 점화식을 세울 수 없었다.

에디토리얼을 보아도 풀이가 직관적으로 이해되지는 않았다.

수학 문제에 너무 약하다.

 

다음과 같은 점화식을 세울 수 있다.

dp[m1][m2]..[mi] = i번째 종류의 꽃이 최소 mi 송이씩 필요할 때 피워야 하는 씨앗 개수의 기댓값

상태 전이는 특정 i에 대하여 (mi - 1)인 상태로부터 이루어진다.

예를 들어 N = 3이고 a = [3, 2, 1]일 때 dp[1][2][0]으로의 상태 전이는 다음과 같이 이루어진다.

• 1번째 종류의 꽃이 3/6 확률로 피어나면 dp[0][2][0]으로부터 상태 전이가 이루어진다.
• 2번째 종류의 꽃이 2/6 확률로 피어나면 dp[1][1][0]으로부터 상태 전이가 이루어진다.
• 3번째 종류의 꽃이 1/6 확률로 피어나지만 m3 = 0이므로 상태 전이는 이루어지지 않는다.

각 상태 전이의 확률도 다음과 같이 계산해주어야 한다.

• 1번째 또는 2번째 종류의 꽃이 피어나야 상태 전이가 이루어지므로 상태 전이가 이루어질 확률은 5/6이다.
• 1번째 종류의 꽃은 3/6 확률로 피어나므로 상태 전이가 dp[0][2][0]으로부터 이루어질 확률은 3/5이다.
• 2번째 종류의 꽃은 2/6 확률로 피어나므로 상태 전이가 dp[1][1][0]으로부터 이루어질 확률은 2/5이다.
• 3번째 종류의 꽃은 1/6 확률로 피어나지만 m3 = 0이므로 상태 전이는 이루어지지 않는다.

위의 정보를 이용하여 다음과 같이 dp[1][2][0]의 값을 계산할 수 있다.

• dp[1][0][0] = 2
• dp[0][1][0] = 3
• dp[1][1][0] = 6/5 + 3/5 * 3 + 2/5 * 2 = 19/5
• dp[0][2][0] = 6
• dp[1][2][0] = 6/5 + 3/5 * 6 + 2/5 * 19/5 = 158/25

코드로는 다음과 같이 계산할 수 있다.

dp[1][2][0] = (sum(a) + dp[0][2][0] * a[1] + dp[1][1][0] * a[2]) * (a[1] + a[2])^(MOD - 2);

 

모든 풀이는 예제 없이 작성하고 있지만 기댓값 dp의 계산 과정을 보여주기 위하여 예제를 사용하였다.

생성 함수 풀이가 존재하지만 적어도 이번 생에는 공부할 일 없을 듯 하다.

 

F - 겨울 숲의 썰매 트랙 (not solved)

에디토리얼에 나온 배치를 대회 중에 시도하였으나 빈칸이 너무 많아서 최적이라고 생각할 수가 없었다.

코딩이 간단하였으면 proof by ac라도 시도하였을 텐데 코딩도 간단하지는 않다.

증명이 어려운 문제이며 구체적인 증명 과정은 에디토리얼에서 확인하자.

 

G - 겨울 숲과 마법 불꽃 (not solved)

다양한 풀이가 존재하지만 에디토리얼 풀이 외에는 공부하지 않았다.

핵심 아이디어는 비용 절감이 필요한 간선들을 묶어서 동시에 관리하자는 것이다.

비용을 절감시킬 때는 루트 노드와 가까운 간선을 선택하는 것이 최적이다.

따라서 루트 노드와 연결된 간선들부터 시작하여 차례대로 적절히 비용을 절감시키면 된다.

priority queue를 이용하여 구현할 수 있으며 query는 offline으로 처리하면 된다.

자세한 풀이는 에디토리얼에서 확인하자.

 

H - 겨울 숲의 수호자 (not solved)

논문 기반 문제이며 풀이는 링크에서 찾아볼 수 있다.

 

끝

끝