BOJ 18221-18227 2019 Overflow Programming Contest (OPC)

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

BOJ 18221 교수님 저는 취업할래요

그냥 구현 문제입니다.

BOJ 18222 투에-모스 문자열

재귀적 구조의 k번째 원소 구하기

BOJ 18223 민준이와 마산 그리고 건우

정점 a에서 b로 가는 최단거리를 dist(a, b)라고 했을 때, dist(1, N) = dist(1, P) + dist(P, N)이면 건우를 도울 수 있고, 아니면 건우를 도울 수 없습니다. dist는 [[다익스트라 알고리즘]]으로 구하면 됩니다.

BOJ 18224 미로에 갇힌 건우

하루를 2m초라고 하고, 0, 1, ..., m-1초는 낮, m, ..., 2m-1초는 밤이라고 합시다. 이제 (행 번호, 열 번호, 현재 시각)을 하나의 상태로 보고 [[BFS]]를 돌립니다. 이러면 O(N^2M)개의 상태가 등장합니다.

이걸 그냥 하면 하나의 상태에서 다음 상태로 가는 데 O(N)이 들어서 안 되고, 각 위치에서 벽을 넘었을 때의 도착점을 미리 계산해 둬야 합니다. 그건 O(N^3)만에 끝낼 수 있고, 그 후에는 한 상태에서 다음 상태로 가는 데 O(1)이 들기 때문에 시간 내에 돌아갑니다.

구현량이 조금 있습니다.

BOJ 18225 당구공을 넣자

우선 꼭짓점을 언제 치는지를 구합니다. p와 q가 서로소이므로, 당구공이 정수 좌표 점을 지나는 시간은 무조건 정수입니다. 따라서 다음 두 방정식을 만족하는 최소의 자연수 t를 찾으면 됩니다.

(1) x + tp = 0 (mod W)

(2) y + tq = 0 (mod H)

좌표 범위가 작기 때문에 O(W+H)에 풀 수 있습니다.

우선 t를 1씩 늘려 가면서 (1)이 성립하는지 봅니다. t가 100만을 넘어갔는데도 (1)이 성립하지 않으면 꼭짓점을 칠 수 없습니다.

(1)이 성립하는 순간의 t를 구했다고 하면, 그 후로부터는 W/gcd(W, p)의 주기로 (1)이 성립하게 됩니다. 따라서 t를 W/gcd(W, p)씩 늘려가면서 (2)가 성립하는지 봅니다. 그 늘리는 작업을 100만 번 넘게 했는데도 (2)가 성립하지 않으면 꼭짓점을 칠 수 없습니다. (2)가 성립하는 순간의 t가 꼭짓점을 최초로 치는 순간입니다.

이제 t초까지 당구공이 가로 방향 변을 치는 횟수와 세로 방향 변을 치는 횟수를 더하고 1을 빼면 됩니다. (1을 빼는 이유는 꼭짓점 때문입니다.)

BOJ 18226 안 읽은 사람은 누구?

우선 안 읽은 사람의 수가 한 번이라도 감소하면 답은 0입니다.

이제 각 사람마다 "마지막으로 읽은 메시지 번호"를 구하려고 합니다. 편의상 "마지막 번호"라고 부르겠습니다. 한 메시지도 읽지 않았다고 하면 그 번호를 0이라고 합시다.

우선 각 사람마다 마지막 번호의 최솟값이 정해져 있습니다. 한 사람이 마지막으로 보낸 메시지 번호가 x이면, 그 사람의 마지막 번호는 x 이상이여야 합니다. 또한 모든 사람의 마지막 번호를 정렬했을 때 무슨 배열이 나와야 하는지도 정해져 있습니다. 안 읽은 사람의 수가 어떻게 변하는지를 살펴보면 됩니다.

그러므로 우리는 이런 문제를 풀어야 합니다. "배열 A의 각 원소에 0 이상 m 이하의 정수를 써넣되, 원소마다 최솟값이 정해져 있고, 배열을 정렬했을 때 배열 B가 나와야 한다. 가능한 배열의 개수를 구하시오."

이것은 A의 각 원소에서 B로 매칭을 하는 것으로 해석할 수 있습니다. 예를 들어 m=2, A의 각 원소의 최솟값이 0, 0, 1, 2이고, B = [0, 1, 2, 2]라고 할 때, 이런 그림을 생각할 수 있습니다.

이런 표에서 가능한 매칭의 개수를 세면 되는데, 사실 첫 번째 2와 두 번째 2를 구별하면 안 되기 때문에 전체 매칭의 개수에서 2를 나눠야 합니다. 구체적으로, B에서 같은 원소가 N개 들어있으면 N!로 나눠야 합니다. 나눠야 한다는 걸 염두에 두고, 매칭의 개수를 구해서 잘 나눠 주면 됩니다.

그래서 매칭의 개수는 어떻게 구할까요? 일반성을 잃지 않고 A의 각 원소의 최솟값이 정렬되어 있다고 가정합시다. 그러면 각 원소가 B의 원소 몇 개와 매칭될 수 있는지를 이분 탐색으로 찾을 수 있고, 그 범위는 점차 증가하는 형태가 됩니다. 따라서 A의 x번째 원소가 B의 원소 y개와 매칭될 수 있으면, x번째 이전까지의 모든 원소가 매칭된 상태에서 남은 원소의 개수는 y-(x-1)입니다. 한 순간이라도 y <= 0이 나오면 답은 0입니다.

BOJ 18227 성대나라의 물탱크

각 정점에 물을 부을 때 항상 그 정점의 깊이 만큼 물을 붓기 때문에, 전부 1L씩이 아니라 차례대로 1L, 2L, ...이 채워진다고 해서 어려워지는 점은 없습니다. 그냥 1L씩 부어 놓고 정점의 깊이를 곱해서 출력하면 됩니다.

그 상태에서 잘 생각해 보면, 문제를 이렇게 바꿀 수 있습니다. 쿼리의 내용은 다르지만 결국 출력하는 값은 동일함을 알 수 있습니다.

1 A: 트리의 정점 중 하나의 값에 x를 더한다.

2 A: 한 서브트리 내 정점의 값의 합을 구한다.

이제 트리에 [[오일러 투어 트릭]]을 써서 일자로 펴면 전형적인 [[세그먼트 트리]] 문제가 됩니다.