2020/05/04 ~ 2020/05/10

2020/05/04

드디어 클래스 9를 달성했다. 오늘은 학교 수업이랑 정과세2 남은 문제들 때문에 딱히 PS를 많이 할 시간은 없었다.

https://www.acmicpc.net/problem/13927

13927번: 수열과 쿼리 14

전에 풀었던 https://www.acmicpc.net/problem/14898 문제의 약간 응용이다.

이제 중복 제거 집합에서의 K번째 수를 구해야 하니, 원래의 K번째 수 문제 풀이를 그대로 이용하면 된다. 원래 K번째 수 문제에서는 PST에서 $A_i$ 이하의 수들의 개수를 쿼리로 하는 이분탐색을 진행했고, 이 과정에서 직사각형 쿼리가 나왔다. 여기서도 $l<=i<=r$, $A_i<=X$ 인 서로 다른 수들의 개수를 세야 한다. 서로 다른 수들의 수를 세니, 조건 $P_i<l$만 더 붙여주면 된다. 이 상황은 각 $i$에 대해 $(i, A_i, P_i)$를 삼차원 상에 플로팅 하고 직육면체 쿼리를 날리는 꼴이다. 이는 K번째 수 문제와 비슷하게 PST의 각 노드에 Dynamic Segment Tree를 넣어 2D Segment Tree를 구성하면 된다. 시간복잡도를 줄이기 위해, 이번에도 세그먼트 트리 위에서의 이분탐색을 이용하면 전체 시간복잡도는 $O(Qlog^2N)$가 된다.

 

https://www.acmicpc.net/problem/4012

4012번: 컨벤션 센터

 

2020/05/05

다른것들보다 트리 DP문제들이 좀 재미있는 것 같다. 복잡한 아이디어나 관찰보다는 자료구조랑 큰거작은거 등의 트릭을 이용한 최적화 문제들이 더 재미있다.

https://www.acmicpc.net/problem/2584

2584번: 트리분할

 

 

https://www.acmicpc.net/problem/16231

16231번: 내가 그린 라이언 그림

풀이는 간단하지만 구현은 꽤 복잡한 큰거 작은거 문제이다. 일단 비용이 $M$이하가 되도록 가장 많은 노드들을 선택하려면 가장 비용이 싼 것부터 골라 나가면 될 것이다. 각 노드의 깊이를 $dep(u)$라 하면 서브트리의 루트 v에서의 u의비용은 $dep(u)-dep(v)+C[A[i]]$ 가 된다. 저 식이 최소가 되려면 이는 $dep(v)$의 대소와는 무관하다. 즉, $dep(v)+C[A[i]]$의 가장 작은거부터 더해서 $x$개를 더했을 때 $M+dep(v)x$를 넘지 않도록 하는 최대의 $x$가 답이다. 그렇다면 이제 리프에서부터 올라오면서 각 색에 대한 unordered_map 에 PQ를 관리하며 삽입 / 삭제 / 가장 작은 x개의 합 쿼리를 처리할 수 있으면 되고, 이는 Dynamic Segment Tree 에 구간 속의 원소들의 합 / 개수를 관리하면 해결할 수 있다. 따라서 답을 이분탐색해주면 큰거 작은거에서 $O(log^2N)$, 이분탐색과 세그먼트 트리에서 $O(log^2N)$이 나오고, 전체 시간 복잡도는 $O(Nlog^2N)$가 된다.

 

2020/05/07

어제 오늘 다양한 트리 디피, 트리에서의 그리디 관찰등 이용한 많은 문제들을 풀려고 시도했지만 마음대로 잘 풀리지 않았다. 내가 평소에 너무 자료구조나 최적화같은 문제들만 풀다 보니, 관찰 스타일 문제들에서 확실히 딸리는 것을 다시 한번 느낄 수 있었고, 남은 이번주 동안은 풀이를 참고해서라도 오늘 시도했던 문제들 모두 해결해야겠다. 이런저런 풀이를 보면서 현타가 와서 오늘도 문제를 많이 풀지는 못했고, CHT문제 몇개 푼 것 밖에 없다.

https://www.acmicpc.net/problem/15958

15958번: 프로도의 100일 준비

L자 모양의 가운데 선 하나를 그으면 양쪽으로 두 직사각형으로 분할할 수 있고, 그 분할 선은 히스토그램의 존재하는 x좌표중 하나임을 관찰할 수 있다. 이로부터 한 선을 오른쪽 변으로 하는 최대 직사각형의 크기를 구하는 문제로 바뀌고, 이를 양쪽으로 해준 다음에 값을 더해주면 된다. 이제 오른쪽 변을 고정시키면 후보가 되는 왼쪽 위 점들은 x가 증가함에 따라 y도 증가하는 꼴이고, 식을 세워보면 $y_i(x-x_i)$가 되어 CHT를 적용할 수 있다. $x_i$가 증가함을 이용하여 단순한 CHT를 이용할 수 있고, 오른쪽 변을 한단계 이동시키면 스택에서 점들이 빠지고, 추가되는 꼴이기 때문에 Harbingers 문제에서 이용했던 복구 가능한 CHT를 구현하면 된다.

 

https://www.acmicpc.net/problem/18571

18571번: Calculating Average

일단 구간의 평균은 $\frac{S_r-S_l}{r-l}$로 표현할 수 있고, $i$를 포함한다는 조건은 $l<i<=r$이다. 이제 답을 이분탐색하면 $\frac{S_r-S_l}{r-l}>=k$의 부등식이 참인지 확인하면 되고, 이는 $S_r-kr>=S_l-kl$과 동치이다. 그렇다면 이는 $\max_{i<=r}S_r-kr>=\min_{l<i}S_l-kl$을 확인하면 된다. $k$는 이분탐색의 변수이니 $S_i-ix$의 일차함수를 관리하는 CHT로 해결할 수 있고, 나는 뒤쪽부터 채워 넣은 후, 복구 가능한 CHT를 이용하여 앞쪽은 하나씩 업데이트, 뒤쪽은 하나씩 복구하면서 CHT에 쿼리를 날려 해결하였다.

 

2020/05/08

https://www.acmicpc.net/problem/9539

9539번: Escape

 

https://www.acmicpc.net/problem/16216

16216번: 우산

 

2020/05/09

https://www.acmicpc.net/problem/1763

1763번: 트리 색칠

 

https://www.acmicpc.net/problem/12752

12752번: 도시들

 

https://www.acmicpc.net/problem/17231

17231번: 이건 버그야!

만약 상대의 공격점이 주어져 있다면, 문제에서 주어진 점화식을 그대로 이용해서 답을 구할 수 있다. 하지만 루트를 여러번 잡고 주어진 DP를 돌리자니 시간이 너무 많이 걸린다. 이런 스타일 문제에서 dp의 정의를 그 노드를 루트로 하는 서브트리에서의 DP1, 전체 트리에서 그 서브트리를 제거한 것에서의 DP2의 두가지를 잡고 계산하면 된다. 이제 마지막으로 내가 선택하면 상대는 꼭 자기 기지에서 출발한다는 보장이 없기 때문에($mod 2^{32}$) 마지막으로 위의 dp1, dp2와 정의가 같은데 그 집합 내에서 점수의 최댓값을 저장하는 dp3, dp4를 새로 만들고 전처리해주면 상대가 기지를 $u$에 잡았을 때의 답을 모두 $O(N)$안에 구해줄 수 있다.

2020/05/10

https://www.acmicpc.net/problem/17955

17955번: Max or Min

 

https://www.acmicpc.net/problem/18855

18855번: Treatment Project

 

https://www.acmicpc.net/problem/10089

10089번: Profit

이 문제는 학교 정과세2에서 나왔던 문제로 그냥 코드만 조금 바꿔서 제출했다. 일단 문제를 잘 해석하면 한 쿼리의 요구를 만족시키기 위해서는 선택하는 두 정점 u, v가 x, y를 완전히 포함하도록 해야 한다. 이 조건은 x, y경로의 모든 간선들을 다 끊은 뒤 x에 매달린 서브트리, y에 매달린 서브트리에 u, v가 속해야한다는 뜻이다. 이는 결국 u, v에 오일러투어를 했을 때 특정 범위로 나오고, 두 범위 조건을 and한것이니 교집합, 즉 직사각형이 된다. 결론적으로 문제는 여러개의 가중치가 있는 직사각형에 겹친 부분의 합의 최댓값을 구하는 문제이고, 이는 lazy maximum segment tree를 이용하여 해결할 수 있다. 시간복잡도는 $O(NlogN)$