5주차 연습 (2)

이번 주차는 쉬어가는 주차로 준비했습니다.

https://www.acmicpc.net/problem/12430

12430번: 생존자 (Large)

풀이

음식을 먹는 순서가 $s_1, s_2, s_3, \cdots, s_K$라고 합시다. 우리는 인접해서 음식을 먹는 $a = s_i$ 번째와 $b = s_{i+1}$ 번째 음식에 집중할 것입니다.

 

$s_{i-1}$ 번째 음식까지 먹었을 때 지난 시간을 $X$ 분이라고 합시다.

$a$와 $b$ 순서대로 음식을 먹었을 때 조건은 $a$번째 음식을 먹기 전의 조건인 $X \le P_a$와 $b$번째 음식을 먹기 전의 조건인 $X+S_a \le P_b$가 있습니다. 즉, $X \le \min(P_a, P_b-S_a)$를 만족해야 합니다.

 

만약에 두 음식의 순서를 바꿔서 $s_1, s_2, \cdots, s_{i-1}, b, a, s_{i+2}, \cdots, s_K$순으로 음식을 먹는다면, 만족해야 하는 조건은 $X \le \min(P_b, P_a-S_b)$가 될 것입니다. 두 방법이 생존할 수 있는 시간은 동일합니다. 그리고 차이가 있는 조건은 $X$가 $\min(P_a, P_b-S_a)$ 이하인지 $\min(P_b, P_a-S_b)$ 이하인지의 차이가 있습니다.

 

그래서 우리는 "올바른 순서를 유지하면서, $a$와 $b$의 순서를 바꿀 수 있는지"에 대해 집중해 보겠습니다. 더 $X$의 범위가 넓은 경우, 즉 $\min(P_a, P_b-S_a) \le \min(P_b, P_a-S_b)$인 경우 $a$와 $b$의 순서를 바꾼 것도 답이 될 수 있습니다.

 

$\min(P_a, P_b-S_a) = P_a$라면 조건에 의해서 $P_a \le P_a - S_b$를 만족해야하므로, 모순입니다.

즉, $\min(P_a, P_b-S_a) = P_b-S_a$ 이고, 대소관계에 따라 식을 정리하면 $P_b-S_a \le P_a-S_b$가 되며, 식을 조금 바꾸면 $P_b+S_b \le P_a+S_a$가 됩니다. 이는 음식을 먹는 순서로 $P_i + S_i$가 큰 것이 먼저 올 경우, 먹는 순서가 인접한 두 음식을 바꿀 수 있다는 의미가 됩니다.

 

즉, 우리가 고려해야 하는 답은 $P_i + S_i$ 순으로 정렬된 답만 고려하면 됩니다. 그렇지 않은 답이 존재할 경우, $P_i + S_i$순으로 오름차순 정렬된 답으로 바꿀 수 있기 때문입니다. 얼마나 생존할 수 있는지는 동적 계획법을 통해서, 가령이면 $DP_{i, j}$를 $i$번째 음식까지 먹었을 때, $j$분동안 생존할 수 있는지 등으로 해결할 수 있습니다.

 

시간 복잡도는 $P$와 $S$의 최댓값을 $MAX$라고 했을 때 $O(N \log N + \frac{N \cdot MAX}{w})$ 입니다.

 

코드: https://www.acmicpc.net/source/share/8c045f6ff4794dc6a47b0220401fa5fd

 

https://www.acmicpc.net/problem/15311

15311번: 약 팔기

 

풀이

판매대의 길이가 $2 \sqrt{N}$이라는 점을 이용합니다. 왼쪽에 $\sqrt{N}$을 $\sqrt{N}$개 배치하고, 오른쪽에 $1$을 $\sqrt{N}$을 배치할 경우, $N$ 이하의 수 $x$는 $x = a\sqrt{N} + b$로 표현되고, $0 \le a, b \le \sqrt{N}$이 되도록 할 수 있습니다. 즉, 가운데를 중심으로 약을 왼쪽에서 $a$개, 오른쪽에서 $b$개 가져가면 $x$를 줄 수 있습니다.

 

코드: https://www.acmicpc.net/source/share/03e67a079a4544c98c102fe6eef8d649

 

https://www.acmicpc.net/problem/24616

24616번: Moo Network

풀이

세 위치 $a, b, c$에 대해 $x_a \le x_b \le x_c$이고 $y_a \le y_b \le y_c$를 만족하면 $(x_a-x_b)^2 + (y_a-y_b)^2 + (x_b-x_c)^2 + (y_b - y_c)^2 \le (x_a - x_c)^2 + (y_a-y_c)^2$ 입니다(한 좌표에 대해 부호를 바꿔도 성립합니다.) 그렇기 때문에 $a$와 $c$를 잇는 것 보다 $a$와 $b$를 잇고 $b$와 $c$를 잇는 것이 더 비용이 적게 들고 $a$와 $c$ 사이의 간선을 고려해 줄 필요가 없습니다.

 

$y$ 좌표의 범위 제한이 작은 것을 이용합시다. 우선 $y$ 좌표가 같은 정점끼리는, $x$ 좌표가 인접한 정점끼리만 이어주면 됩니다.

 

$y$ 좌표가 서로 다른 두 정점을 잇는 경우에는 해당하는 $y$ 좌표를 가지는 위치에 대해서 $x$ 좌표가 인접한 정점끼리만 이어주면 된다는 사실을 알 수 있습니다. $y_a = y_c$이면 $y$ 좌표가 같은 경우이므로, 위의 경우에서 이미 고려가 되었고, $y_a \ne y_c$이면 $y_a \le y_b \le y_c$ 혹은 $y_a \ge y_b \ge y_c$를 항상 만족하기 때문입니다.

즉, 우리는 $O(Y^2N)$개의 간선만 고려해서 스패닝 트리를 만들면 됩니다. 여기서 $Y$는 $Y$좌표의 범위입니다.

 

코드: https://www.acmicpc.net/source/share/5c2bc4f7daff49eaa33b349bf8e9aa7b

https://www.acmicpc.net/problem/19246

19246번: Tribute

풀이

답이 존재한다고 가정합시다. 부분집합의 합 중에서 가장 작은 수는 $a_i$ 중 가장 작은 수 일 것입니다. 이 수를 $a_1$이라고 합시다. 나머지 부분집합은 $a_1$을 포함하는 부분집합과 아닌 집합으로 나뉘어지기 때문에 이 수열에는 $x$와 $x+a_i$가 하나씩 존재해야합니다.

std::multiset 등을 이용해서 쌍을 짝지을 수 있는지 확인합니다. 짝지을 수 있다면 $a_1$을 제외한 나머지 $a_i$들의 부분집합의 합에 대한 수열은 $x$를 모은 것이기 때문에 위 풀이를 재귀적으로 적용해서 답을 구해나가면 됩니다.

 

코드: https://www.acmicpc.net/source/share/6eec729a51a74cbba8b389c293b2bbdc

 

https://www.acmicpc.net/problem/24536

24536번: 정원장어

풀이

왼쪽에 R, 오른쪽에 L이 존재해서 정원 장어가 서로를 쳐다보게 된다면 이 두 정원 장어중 적어도 하나는 기분이 나쁩니다. 그렇기 때문에 남아있는 장어는 어떤 위치를 정해서 왼쪽에는 L, 오른쪽에는 R만 존재하도록 해야합니다.

 

왼쪽의 L은 증가수열을 이루어야하고 오른쪽의 R은 감소수열을 이루어야하며, 남아있는 장어의 수를 최대화해야 합니다. L과 R을 나눌 위치를 고정합니다. 왼쪽은 L로 이루어진 최장 증가 부분수열, 오른쪽은 R로 이루어진 최장 감소 부분수열을 구한 뒤 합쳐주면 해당 위치를 기준으로 장어를 제일 많이 남기게 됩니다.

이를 모든 위치에 대해서 시도해주면 되고, 원하는 LIS 알고리즘 중 순차적으로 값을 하나하나씩 계산하는 알고리즘을 사용해서 답을 구해주면 됩니다.

코드: https://www.acmicpc.net/source/share/c3868ba8a5ea47788c4b6cedb9de69e8