BOJ 20665-20672 shake! 2020¶
https://www.acmicpc.net/category/detail/2399
20665 독서실 거리두기¶
지문에 주어진 대로 구현하는 문제입니다. (2021년 2월 18일 기준으로) 빠진 조건이 있는데, https://www.acmicpc.net/board/view/62814 를 참조하시기 바랍니다.
제한이 작기 때문에, 좌석을 이용할 수 있는지 1분마다 한 번씩 확인해도 충분합니다.
자세한 설명은 https://www.slideshare.net/MinGyuKim6/2020-shake-solution을 참조하시면 좋습니다.
20666 인물이와 정수¶
처음에는 아무 아이템도 없으니까, 모든 (a, b, t)에 대해 b의 난이도를 t 올립니다. 아이템 a를 얻고 나면 b의 난이도가 t 내려갈 것입니다. 각 a마다 (b, t)의 목록을 저장해 두면 난이도를 알맞게 내릴 수 있습니다.
매 순간마다, 살아있는 몬스터 중 난이도가 가장 낮은 몬스터를 잡아야 합니다. 그 몬스터를 나중에 잡는다고 해서 얻는 이득이 없기 때문입니다.
가장 쉬운 몬스터는 우선순위 큐로 찾을 수 있습니다. 단, 몬스터를 잡으면 다른 몬스터의 난이도가 바뀌기 때문에, (난이도, 몬스터 번호) 순서쌍을 우선순위 큐에 넣고, 난이도가 바뀔 때마다 다시 넣어줘야 합니다. 같은 몬스터를 여러 번 잡지 않도록 중복 처리를 해줍시다.
20667 크롬¶
BOJ 7579번 (앱) 문제와 비슷한 발상을 사용합니다. 메모리 할당량이 너무 큰데 우리가 구해야 되는 중요도 합은 작으니까, 메모리 할당량 말고 중요도 합을 DP 인자로 넣는 것입니다. DP[i][j][k] = "첫 i개의 탭만 고려했을 때, 지운 탭의 CPU 합이 j, 중요도 합이 k일 때, 메모리 합의 최댓값"으로 두면 i <= N, j <= NM, k <= 5N이 되어 O(N^3M) 냅색 문제가 됩니다.
N^3M은 여전히 너무 큽니다. 하지만 사실 CPU 합이 M 이상이 되면 정확히 얼마이든 중요하지 않기 때문에, DP[i][M][k], DP[i][M+1][k], ..., dp[i][NM][k]은 전부 하나로 합쳐줄 수 있습니다. 그러면 j <= M이 되어 O(N^2M)에 DP를 계산할 수 있습니다.
이제 DP[N][M][k] >= K인 가장 작은 k를 찾으면 됩니다.
20668 카트라이더¶
속도 제한이 <= 10이므로, 속도는 10보다 크게 올릴 수 없습니다. 이제 "새로운 그래프"를 이렇게 모델링합니다.
- 원래 그래프의 정점 a와 속도 v에 대해, 새로운 그래프의 정점 (a, v)를 만듭니다.
- 원래 그래프의 간선 a->b (길이 L, 제한 K)와 속도 v에 대해, 만약 v <= K라면, 새로운 그래프의 간선 (a, v) -> (b, v), (a, v) -> (b, v-1), (a, v) -> (b, v+1)을 가중치 L/v로 긋습니다.
- 맨 처음에 속도를 올릴 수도 있기 때문에, (1, 1) -> (1, 2)를 가중치 0으로 긋습니다.
이제 (1, 1)에서 (N, v)로 가는 최단거리를 구하면 됩니다. 하지만 힌트를 잘 보면 "double, long double 등의 실수형을 사용하여 출력할 경우 유효 숫자 범위로 인해 틀릴 수 있다."라고 적혀있습니다. 실제로 문제에서 요구하는 정확도가 너무 크기 때문에, 이걸 그냥 구하면 안 됩니다.
가중치를 잘 보면, 모든 가중치의 분모가 10 이하이기 때문에, 분모가 lcm(1, 2, ..., 10)인 분수로 나타낼 수 있습니다. lcm(1, 2, ..., 10) = 2520이므로, 분모가 2520인 분수를 가중치로 두면 정수형만 써서 풀 수 있습니다. 분수를 쓰고 싶지 않다면 모든 L에 2520을 곱하면 됩니다.
20669 Close to You¶
그래프에서의 경로의 개수는 행렬 곱으로 나타낼 수 있다는 사실을 기억합시다. 그래프의 인접 행렬을 A라고 할 때, 특정 정점에서 시작해서 특정 정점으로 끝나는 길이가 K인 경로의 개수는 행렬 A^K를 통해 구할 수 있습니다. 분할정복 (또는 그와 비슷한 풀이)을 통해 O(A^3logK)에 A^K를 구할 수 있음이 잘 알려져 있습니다.
이 문제에서는 길이가 1 이상 K 이하인 경로의 개수를 구해야 하므로, (A + ... + A^K) mod (10^9+7)을 구하면 됩니다. A^K를 구하는 방법과 비슷한 형태의 분할정복으로 구할 수 있습니다. BOJ 15712 등비수열
20670 미스테리 싸인¶
볼록다각형 내부 점 빠르게 판별을 참조하세요.
20671 요새 파괴¶
블록이 미사일에 맞을 때, 파괴되는 게 아니라 "망가진다"고 합시다. 블록을 없애는 게 아니라 일종의 표식을 붙이는 것이죠. 이렇게 하면 "위에 있는 블럭은 피해 없이 그대로 아래로 내려온다." 이 부분을 구현할 필요가 없습니다.
그런데 미사일은 실제로 파괴되지 않은 블록 P개를 타격해야 하니까, 미사일의 작동 과정은 이렇게 바뀝니다.
- X 위치의 맨 위에 있는 블록을 찾습니다.
- 한 블록씩 내려가면서, 망가지지 않은 블록이 나올 때마다 그 블록을 망가뜨립니다. 블록 P개를 새로 망가뜨렸거나 더 이상 내려갈 수 없을 때까지 반복합니다.
두 과정 모두 그냥 구현하면 O(N^2)이므로, 각각을 최적화해야 합니다.
- 일단 편의를 위해, 바닥도 블록이라고 합시다. 단, 바닥은 절대로 망가지지 않습니다.
- 미사일을 아무리 쏴도 X 위치의 맨 위에 있는 블록은 바뀌지 않습니다. (망가질 뿐이죠.) 그래서 이걸 전처리할 수 있습니다. 왼쪽으로 블록을 쭉 훑으면서, 맨 위에 있는 블록이 바뀔 때마다 X좌표와 블록 번호를 기록합니다. std::set 등 여러 방법이 있습니다. 이제 미사일이 주어질 때마다 맨 위에 있는 블록을 이분 탐색으로 구할 수 있습니다.
- 한 블록씩 내려가는데 망가진 블록이 너무 많으면 비효율적이므로, 이 망가진 블록들을 건너뛰는 방법이 필요합니다. 이는 disjoint set으로 구현할 수 있습니다. 블록이 망가질 때마다, 바로 밑에 있는 블록과 합쳐주고, 합쳐진 집합의 대푯값은 "그 집합에 속한 블록 중 가장 낮은 블록"으로 둡니다. 그 블록은 망가지지 않은 블록일 것입니다. 이제 망가진 블록을 만날 때마다, 그 블록이 속한 집합의 대푯값으로 가면 망가진 블록들을 모두 건너뛸 수 있습니다.