2022.07.31 PS

jjang36524가 만든 셋을 4시간으로 잡고 풀었다.

점수는 138점으로 처참하였다. 결과는 0 100 0 38 이었다.

A번 같은 경우는 솔직히 좀 더 집중했더라면 0점 초과의 점수를 받지 않았을까 싶다.

 

그렇게 위로함을 뒤로하고 A 업솔빙, D는 이미 풀었던 문제를 복습하고 나서 풀이만 떠올렸다.

 

B(12763). 지각하면 안돼

처음엔 그냥 쉬운 다익스트라 문제인 줄 알았는데 크게 데였고, dp로 접근하여 다시 맞았다.

 

dp(i,j) = 지금 i호관에 있고 남은 돈이 j일때 답

 

이걸 가지고 식을 잘 세우면 된다

 

코드를 너무 더럽게 짠 것 같다...
코드

 

A(11941). 핀볼

문제에서 각 끝에서 온 공은 모두 특정 한 곳으로 떨어진다는 중요한 관찰 하나를 해야 한다.

 

그렇다면 여기서 우리는 비용이 최소가 되는 특정 한 곳을 찾아야 한다.

 

이는 dp로 할 수 있다.

 

dpL(x) = 가장 왼쪽에서 지점 x까지 갈 때 드는 최소 비용

dpR(x) = 가장 오른쪽에서 지점 x까지 갈 때 드는 최소 비용

 

답은 min(dpL(x)+dpR(x)+(헤당 고깔을 설치하는데 드는 비용))이다.

각 dp값을 식으로 계산하면 O(M^2)의 시간복잡도가 나오는데, 식이 어떤 특정 범위에서 dp값들의 최솟값이므로 세그먼트 트리를 이용해서 최적화를 하면 이 문제를 풀 수 있다.

 

그리고 N의 범위가 10^9 이하이기에, 좌표압축을 해놓자.

 

코드

 

D를 풀기 전 : BOJ 3392  화성 지도

기존의 나이브한 평면 스위핑을 세그로 바꿔 최적화한 것이다.

 

세그의 각 노드는 그 지점에서 포함하는 평면의 갯수이고 우리가 구하고자 하는건 평면을 포함하는 노드의 갯수이다.

D(17423). 민원이 흘러넘쳐

함수를 하나 정의하자.

 

f(x) = 볼륨이 x일때, 민원이 들어오는가?

 

이 함수의 개형은 어느 한 지점에서 0=>1로 바뀌고, 나머지는 연속하다는걸 알 수 있다.

 

고로 우리는 Parametric Search를 통해 만족하는 최대 x를 구할 수 있다.

 

이제 판별만 남았는데, 이는 위 화성 지도 세그먼트 트리를 이용해서 할 수 있다.

 

위 세그의 각 노드에는 그 지점에서 포함하는 평면의 갯수이고 겹쳐져 있다는 뜻은 2개 이상의 평면이 그 지점에 포함되어 있다는 것이다.

 

고로 이를 이용하여 확인해주면 O(N log^2 N)만에 풀 수 있다.

 

아직 구현은 안했다.