PS 문제 풀이 [2021.8]

JAG Practice Contest 2020 D. Surround the Castle

성을 둘러싸는 것은 격자에서 상하좌우로 이동하며 사이클을 만드는 것으로 볼 수 있으므로, 성을 둘러싸는 최단 경로를 찾는 방식으로 접근합니다. 성을 둘러싸는 경로만을 생각해야 하는데, 이는 성에서 반직선을 하나 그어 그 선을 홀수 번 지나는 경로만을 생각하면 됩니다. (반직선을 그어 다각형 내부에 있는지 판별하는 것과 비슷한 방식) 그러므로 반직선을 홀수 번 지난 상태와 짝수 번 지난 상태를 구별하여 다익스트라를 돌리면 문제를 해결할 수 있습니다. 다익스트라의 시작점을 잡아야 하는데, \(R\)의 범위가 작으므로 성의 위쪽이나 아래쪽을 전부 해보면 됩니다.

 

BOI 2021 A. A Difficult(y) Choice

먼저 이분 탐색을 통해 \(A\) 이하인 수와 \(A\) 초과인 수들을 나눕니다. 나눈 집합을 각각 \(P, Q\)라고 합시다.

 

• \(Q\)에서 선택한 수가 있는 경우

\(Q\)에서 두 개 이상의 수를 선택하면 \(2A\)를 초과하므로 한 개만 선택해야 합니다. 나머지 수를 \(P\)에서 선택하여 \(2A\) 이하가 된다면 가능합니다. \(Q\)의 최소값과 \(P\)에서 가장 적은 \(K-1\)개의 수를 더하여 \(2A\) 이하라면 이 방법을 출력하면 됩니다.

 

• \(P\)에서만 선택하는 경우

가장 적은 \(K\)개의 수의 합이 \(2A\) 초과이거나 가장 큰 \(K\)개의 수의 합이 \(A\) 미만이라면 불가능합니다. 그렇지 않다면, 항상 가능합니다. 모든 \(i (0 \le i \le K)\)에 대해 가장 적은 수 \(i\)개, 가장 큰 수 \(K-i\)개를 선택하는 경우를 시도해보면 됩니다. (모든 수가 \(A\) 이하이므로 수를 하나 빼고 넣어도 합이 \(A\) 이상 변하지 않기 때문에 항상 찾을 수 있음)

 

알아야 하는 수는 \(P\)의 최소/최대 \(K\)개, \(Q\)의 최소값 뿐이므로 이분 탐색을 포함해 skim을 40번 이내로 호출하여 답을 구할 수 있습니다.

 

JOI 2020/2021 Spring Training Camp 1-3. Food Court

1번부터 N번까지 상점을 스위핑하면서 쿼리의 답을 오프라인으로 계산합니다. 모든 1, 2번 쿼리에 대해 L번 상점을 볼 때 그 쿼리를 활성화시키고, R+1번 상점을 볼 때 그 쿼리를 비활성화시킵니다. 현재 보는 상점에 3번 쿼리가 있을 때, 그 3번 쿼리가 들어온 '시간'까지 활성화된 쿼리들을 생각하여 답을 구해야 합니다. 일단 그 상점에 있는 사람 수만 구해봅시다.

 

2번 쿼리에서 \(K\)가 상점에 있는 사람보다 많을 수도 있기 때문에 단순히 이전까지의 사람 변화량을 더하기만 해서는 답을 구할 수 없습니다. 하지만 사람 수가 0보다 작아지려 할 때, 0이라는 '하한' 자체를 변경시키면 가능합니다. 예를 들어, 현재 하한이 0이고 상점에 2명이 있을 때 4명이 나간다면 하한을 -2명으로 바꾸고 사람 수는 -2명이라고 치면 됩니다. (사람 수가 하한이라는 '벽'을 밀고 아래로 내려간다고 생각할 수 있습니다.)

 

이렇게 생각하면 3번 쿼리의 답은 3번 쿼리가 들어온 시간에서 (상점의 사람 수) - (상점의 하한)이라고 생각할 수 있고, 이는 (3번 쿼리까지의 사람 변화량의 합) - (3번 쿼리까지 상점에 있었던 사람 수의 최솟값)이 됩니다. 이를 '시간'에 대한 세그먼트 트리로 구현하면 그 상점의 있는 사람 수를 계산할 수 있습니다.

 

이제 3번 쿼리에서 그룹 번호를 구해봅시다. 상점의 있는 사람 수를 구했으므로, 서비스를 제공할 사람이 온 뒤에 상점에 온 사람의 수를 구할 수 있습니다. 이 사람 수를 \(P\)라 하면, 서비스를 제공할 사람이 들어오는 시점은 그 시점부터 3번 쿼리의 시점까지 상점에 들어온 사람의 수가 \(P\)보다 큰 마지막 시점이 됩니다. 이제 이 시점을 이분 탐색으로 찾으면 그룹 번호를 알 수 있습니다.

 

JOI 2020/2021 Spring Training Camp 4-3. Worst Reporter 4

문제에서 조건이 '\(i\)의 레이팅이 \(A_i\) 이상이다'로 주어지는데, 레이팅을 뒤집어서 '\(i\)의 레이팅이 \(A_i\) 이하이다'로 바꿉니다. 이 편이 더 생각하기 간단합니다.

 

모든 조건에 대해 \(i\)에서 \(A_i\)로 간선을 이은 그래프를 생각해 보면, 한 컴포넌트는 사이클 하나와 그 사이클에 트리들이 붙어있는 형태를 이룹니다. 사이클에 있는 사람들의 레이팅은 모두 같아야 하므로, 사이클을 한 정점으로 보면 전체 그래프는 포레스트와 같은 형태를 이룹니다. 사이클이 합쳐진 정점의 처리는 나중에 생각하고, 먼저 일반적인 트리에 대하여 문제를 풀어봅시다.

 

트리에서 만족해야 하는 조건은 부모의 레이팅이 자식의 레이팅보다 높아야 합니다. 다음과 같이 DP 배열을 정의합니다.

• \(D[n][k] = n\)번 정점을 루트로 하는 서브트리에서 \(n\)번 정점의 레이팅을 \(k\)이하로 하는 비용의 최솟값

이 DP 테이블을 그냥 계산하기에는 레이팅의 범위가 너무 넓습니다. 그러므로 DP 테이블의 값이 변하는 지점만을 std::map과 같은 자료구조로 저장합니다. 정점 \(DP[n]\)의 값을 저장할 map을 \(M[n]\)이라고 합시다. 여기서 map에는 '값의 변화량'을 저장합니다. 즉, \(D[n][k - 1]\)과 \(D[n][k]\)의 값이 다르다면, \(M[n][k] = D[n][k] - D[n][k - 1]\)와 같은 형태로 저장되어 있어야 합니다.

 

정점 \(n\)의 DP 테이블을 계산한다고 합시다. 이제 두 서브트리의 DP 테이블을 합치는 것은 매우 간단합니다. 한쪽 map에 다른쪽 map의 값들을 모두 더해주기만 하면 됩니다. 정점 \(n\)의 서브트리를 모두 합친 뒤, 정점 \(n\)의 비용도 DP 테이블에 반영시켜야 합니다. 비용은 레이팅이 \(H[n]\)이 아니라면 \(C[n]\) 만큼 더해지게 됩니다. 변화량으로 보면 map의 처음 값이 \(C[n]\) 만큼 증가하고, \(H[n]\)에서 \(C[n]\) 만큼 감소하게 됩니다. \(H[n]\) 초과의 값에 대해서는 그냥 \(C[n]\) 만큼 증가시켜버리면 레이팅을 \(H[n]\)으로 유지시키는 경우가 더 이득이 되는 경우에 변화량이 양수가 될 수도 있습니다. 따라서 변화량이 음수가 될 때까지 map에서 순서대로 값들을 제거 한 뒤 \(C[n]\)을 증가시켜주면 됩니다. (아래 그림 참고)

위의 방식으로 그냥 계산하면 \(O(N^2lgN)\)이 되지만, 서브트리를 합칠 때 큰 서브트리의 map에 다른 map들을 합쳐 주면 \(O(Nlg^2N)\)이 되어 시간 내에 계산할 수 있습니다. (Small to Large)

 

 

이제 사이클이 합쳐진 정점에 대해 처리해야 합니다. 이 정점의 레이팅의 후보는 사이클에 포함된 정점들의 원래 레이팅 값들과 레이팅의 최댓값 \(=10^9\) 뿐입니다. 레이팅을 정하면 미리 채워둔 DP 테이블을 통해 전체 트리의 비용도 쉽게 알 수 있습니다. 모든 트리에 대해 비용의 최솟값을 계산하여 더하면 답을 구할 수 있습니다.