BOJ 18857-18867 제1회 논산 코드 페스티벌

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

18857 집 떠나와 열차 타고

선인장의 block-cut tree를 생각해 봤을 때, 정점 1과 N 사이에 있는 경로만 생각해도 충분합니다. 그런 경로만 생각하면 그래프는 대충 이런 형태가 됩니다.

이제 1번 정점에서 N번 정점으로 못 가게 하려면, 이 그래프의 BCC 중 하나를 완전히 끊어야 합니다. 완전히 안 끊고 예를 들어 사이클에서 하나의 간선만 제거한다거나 그러면 소용이 없습니다. 따라서, 각각의 BCC를 끊는 비용을 구하고, 그 중 최솟값을 구하면 됩니다.

18858 훈련소로 가는 날

DPu[i][j] = "길이 i, 마지막 정수 j이며, 마지막 두 수가 오름차순인 경우의 수", DPd[i][j]는 거의 똑같은데 "오름차순이 아닌 경우의 수"로 두면 O(NM^2)가 나옵니다. 이것만으로 시간 내에 돌아가지만, prefix sum을 적절히 사용하여 O(NM)으로 줄일 수도 있습니다.

18859 부모님께 큰절 하고

감소수열과 증가수열을 생각하지 말고, 맨 첫 원소를 공유하는 두 개의 증가수열로 분해한다고 생각해 봅시다.

1. 맨 첫 원소는 수열의 최솟값이어야 합니다. 그 수를 m이라고 합시다.
2. 한 수열의 공차는 (m 제외 최솟값) - m이어야 합니다. 그 공차를 d라고 합시다. d = 0이면 답은 No입니다.
3. m+d에서 시작해서 공차가 d인 등차수열을 적절히 제거했을 때, 남은 수들도 등차수열을 이루어야 합니다.

3번은 어떻게 할까요? 수들을 정렬하고, 인접한 수들의 차를 모두 계산했을 때, 그중 최솟값과 최댓값이 같아야만 등차수열을 이룰 수 있습니다. 인접한 수의 차를 모두 저장하는 자료구조를 생각해 봅시다. 여기서 수 x를 지우면, 이런 변화가 일어납니다.

i) x 왼쪽과 오른쪽에 있는 수를 L, R이라고 합시다. L이나 R이 없을 수도 있습니다.

ii) L이 있으면, 자료구조에서 L-x가 제거됩니다. R이 있으면, 자료구조에서 x-R이 제거됩니다.

iii) 그리고 L과 R이 모두 있으면, 자료구조에 R-L이 추가됩니다.

따라서 수를 제거, 추가하고, 최솟값과 최댓값을 받아오는 자료구조를 쓰면 됩니다. 가장 대표적인 것으로 multiset이 있고, 임의의 원소 삭제가 가능한 힙을 만들 수도 있습니다. (그 힙에 대한 설명은 제 블로그 어딘가에 있습니다.)

18860 대문 밖을 나설 때

특정 펌프가 처음으로 작동을 시작한다고 하면, 전체 과정은 이렇게 생각할 수 있습니다.

1. 현재 작동 중인 펌프가 포함된 가장 작은 서브트리를 채웁니다.
2. 이제 석유가 넘쳐서 더 큰 서브트리로 흘러 가는데, 이 순간에 가능한 한 많은 펌프를 작동시켜야 합니다. x만큼의 석유가 넘치면 min(도달 가능한 펌프 개수, x)개의 펌프를 작동시킬 수 있습니다.
3. 그 다음 순간에는 도달 가능한 모든 펌프를 작동시킬 수 있습니다.
4. 1번으로 돌아갑니다.

2번과 3번은 O(1)에 구현할 수 있습니다. 가장 시간이 오래 걸리는 부분은 1번인데, 채워야 되는 서브트리의 크기를 미리 DP로 계산해 놓으면 이것도 O(1)에 구현할 수 있습니다. 그리고 이 모든 과정은 O(logN)번 반복되므로, 특정 펌프에서 시작할 때 다 채우는 데 걸리는 시간은 O(logN)만에 계산할 수 있습니다.

모든 펌프에 대해 시간을 계산하면 됩니다.

18861 가슴 속에 무엇인가

만약 그래프가 포레스트임이 보장된다면, 간선 추가, 삭제, 경로 최솟값을 구하는 쿼리가 됩니다.

포레스트가 아니라면 어떨까요? 트리에 간선 하나를 추가해 봅시다. 그러면 사이클이 정확히 하나 만들어집니다. 그 사이클의 간선 중 가중치가 가장 작은 것을 봅시다. (여러 개면 아무거나 선택합니다.) 그러면 그 간선은 더 이상 쓸모가 없습니다. 3번 쿼리의 경우 그 간선을 쓰는 대신 사이클 반대 방향으로 돌아서 가면 되며, 2번 쿼리의 경우 사이클의 다른 간선들이 제거되기 전에 자신이 먼저 제거되기 때문입니다.

따라서 새로운 간선을 추가하기 전에, 가중치가 가장 작은 그 간선을 먼저 제거하면, 결과에 영향을 주지 않으면서 포레스트를 유지시킬 수 있습니다. 결국 이것도 경로 최솟값 쿼리가 됩니다. 이 모든 것은 링크-컷 트리로 구현할 수 있습니다. 신난다!

18862 아쉬움이 남지만

음... 사실 이 글을 네이버 블로그에 2년 전에 썼는데요, 이거랑 그 다음 두 문제는 풀이를 안 썼습니다. 이 문제는 풀이가 정확히 기억나지 않아서 쓰려면 다시 풀어야 합니다. 죄송합니다...

18863 풀 한 포기 친구 얼굴

격자의 각 칸마다 (물론 도착점은 제외하고) 어떤 명령을 내릴 수 있는지 판별하면 정점 NM개, 간선 10NM개 이하의 그래프가 만들어집니다. 문제는 출발점에서 유한 개의 간선을 타고 도착점으로 오는 방법의 수를 구하는 것입니다.

우선 특정 칸에서 특정 명령을 내릴 수 있는지 판별합시다. 각 명령을 전처리하면서 "이 명령을 수행하는 동안, 명령을 시작한 위치를 기준으로 이동하는 최소/최대 x/y좌표"를 구하면, 특정 칸에서 이 명령을 내릴 때 격자를 벗어나는 경우가 존재하는지 O(1) 만에 판별할 수 있습니다. 예를 들어 명령이 EWN이라면 최소/최대 x좌표는 0과 1, 최소/최대 y좌표는 -1과 0입니다.

이제 그래프가 주어졌을 때, (1) 시작점에서 도달할 수 있으면서 (2) 거기서부터 도착점으로 갈 수 있는 칸을 구합니다. 이 두 조건 중 하나라도 만족하지 않는 칸은 욱제가 아예 도달할 수 없거나, 욱제를 (N, M)으로 못 보내서 욱제의 훈련을 끝낼 수 없습니다. (1)은 그대로 그래프 순회를 돌리면 구할 수 있고, (2)는 모든 간선의 방향을 뒤집은 다음 도착점에서 그래프 순회를 돌리면 구할 수 있습니다.

이렇게 정점을 쳐낸 후, 그래프에 사이클이 남아있으면 답은 -1이고, 아니면 위상정렬 후 통상적인 DP로 답을 구할 수 있습니다.

18864 모든 것이 새롭다

예제 1은 불가능한 퍼즐로 알려진 매우 유명한 퍼즐입니다. 왜 불가능할까요?

퍼즐의 각 조각마다 그 조각이 (조각이 없을 경우, 빈 칸이) 원래 어디로 와야 되는지를 계산하면, 퍼즐 전체를 하나의 순열로 나타낼 수 있습니다. 조각 하나를 움직이는 것은 조각과 빈 칸을 서로 바꾸는 것이므로 순열에 또 다른 순열 (a b)를 곱하는 것과 같습니다. (a b)는 홀순열이므로, 조각 하나를 움직일 때마다 순열의 홀짝성이 바뀝니다. 그런데 빈 칸이 맨 처음 상태와 마지막 상태에서 위치가 같기 때문에 조각은 짝수 번 움직여야 하고, 따라서 맨 처음 상태와 마지막 상태는 홀짝성이 같습니다. 그런데 실제로는 맨 처음 상태가 홀순열이고, 마지막 상태가 짝순열이기 때문에 이 퍼즐은 맞출 수 없습니다.

이를 일반화하면 문제를 풀 수 있습니다. 일단 여섯 차원 중 다섯 개의 크기가 1이면 예외처리를 해야 합니다.

이제 맨 처음 상태의 홀짝성을 확인합니다. 마지막 상태는 무조건 짝순열입니다. 따라서 (맨 처음 상태가 홀순열)과 (빈 칸이 홀수 번 움직여야 함)이 동치가 아니면 이 퍼즐은 맞출 수 없습니다. 반대로 동치이면 이 퍼즐은 맞출 수 있는데, 이건 증명하기 조금 까다롭습니다. 한번에 한 레이어씩 맞추면 되던 걸로 기억합니다.

18865 이제 다시 시작이다

한 스피커에 대해, 볼륨을 점차 증가시키면 훈련소 내부에서 소리가 들리는 영역이 다음과 같이 변합니다.

1. a초까지는 들리는 영역이 없습니다.
2. a초부터 b초까지는 한 변의 길이가 V-a인 직각이등변삼각형이 됩니다.
3. b초부터 c초까지는 한 변의 길이가 V-a인 직각이등변삼각형에서, 위쪽 또는 오른쪽 일부분을 제거한 형태가 됩니다. 단, 둘 중 한 부분만 제거됩니다. b=c일 수도 있습니다.
4. c초부터 d초까지는 위쪽과 오른쪽을 둘 다 제거한 형태가 됩니다.
5. d초부터는 직사각형이 되고 영역이 더 이상 변하지 않습니다.

이제 영역의 넓이가 어떻게 변하는지 생각해 봅시다. 1번의 경우 따로 해야 될 일이 없습니다. 2번의 경우, a초부터 시작하는 이차함수를 만들 수 있습니다.

3번의 경우, V-a 크기의 직각이등변삼각형의 넓이에서 제거된 부분의 넓이를 빼면 됩니다. V-a 삼각형의 넓이는 2번에서 이미 추가되었기 때문에 그대로 쓰면 되고, 제거된 부분은 직각이등변삼각형이므로 이차함수로 나타낼 수 있습니다. 4번도 마찬가지입니다. 5번의 경우 두 "제거된 부분"이 겹친 것이라고 생각할 수 있습니다. 따라서 겹친 부분의 넓이를 다시 더해줘야 합니다. 이 겹친 부분도 직각이등변삼각형이므로 이차함수로 나타낼 수 있습니다.

이걸 구현하려면 이런 자료구조가 필요합니다.

1. 특정 시간 t부터 정의되는 이차함수를 추가한다.
2. 특정 시간 t에서 이차함수들의 합을 구한다.

이건 펜윅 트리를 3개 만들어서 풀 수 있습니다. 각 펜윅 트리는 이차함수의 이차항의 계수, 일차항의 계수, 상수항을 각각 저장하면 됩니다.

18866 젊은 날의 생이여

1~K년이 젊은 날이 될 수 있는지 판별해 봅시다.

먼저, K년까지의 행복도 중 최솟값은 이후의 행복도 중 최댓값보다 커야 합니다. 그걸 판별하려면 행복도 중 누락된 값을 아예 "없는 데이터"로 취급해도 무방합니다. 어차피 K년까지의 행복도 중 누락된 값은 매우 크게 잡아야 하고, 이후의 행복도 중 누락된 값은 매우 낮게 잡아야 하기 때문입니다. 마찬가지로, K년까지의 피로도 중 최댓값이 이후의 피로도 중 최솟값보다 낮아야 합니다.

따라서 "첫 x년의 최소 행복도", "첫 x년의 최대 피로도", "마지막 x년의 최대 행복도", "마지막 x년의 최소 피로도"를 모두 구하면 됩니다. DP로 풀 수 있습니다.

18867 편지 꼭 해다오

제한이 많이 널널하기 때문에, 여러 가지 방법으로 풀 수 있습니다.

가장 짧은 답안을 찾고 싶다면 냅색을 풀면 됩니다. [a-zA-Z0-9]에 있는 글자만 사용할 때는 5글자가 가장 짧습니다.