최근들어 제대로 된 PS를 하기로 했다. 그냥 무지성으로 웰논 골플 문제를 푸는 것이 아닌, 깊은 생각을 요하는 문제를 풀어야겠다...
행렬식 dp문제다. 홀수 행렬과 짝수 행렬을 곱해준 행렬을 N제곱하면, 2N번 이동했을 떄의 경우의 수가 된다. 여기에서 \(2k+1\)꼴로 이동하기 위해서는, k제곱한 행렬에 홀수 행렬을 곱해주면 된다.
식을 잘 건드리면 \(\frac{y_i}{x_i}\)에 대한 cht를 할 수 있다.
그냥 다익스트라 돌리면 된다. 다만 b+kp (k는 자연수)에 동일한 p값을 가진 도게가 있다면 이보다 더 큰 b + (k+1)p부터는 볼 필요가 없다. b - kp에서도 동일.
한 정점을 5개로 쪼개고, a5 -> a4 -> a3 -> a2 -> a1 처럼 거리 1의 단방향 간선을 만들어주자. b to a의 거리가 4라면, b1 -> a4에 거리 1 간선을 추가해주면, b1 to a1의 거리는 4가 된다. 이제 행렬 거듭제곱을 해주면 끝이다.
무지성으로 골플 안 풀기로 했는데 무지성 hld가 여기에 있었네..
Half Plane Intersection을 배우고 풀은 문제인데... 일단 풀이는.. 각 변을 벡터로 보고, r만큼 안쪽으로 평행이동 했을 때의 반평면 교집합이 존재하는지를 알 수 있다. 그리고 이 r은 이분 탐색으로 찾으면 되므로, 시간복잡도는 \(O(NlgNlgX)\)가 된다. \(X\)는 좌표의 범위다.
\(dp[l][r]\) = (구간 \([l, r]\)에서의 최솟값) 으로 정의 하자. 구간을 어떤 인덱스 i에서 끊는 경우에는 \([l,i-1]\)과 \([i+1,r]\)로 나뉘게 된다. 이때 구간 내의 수들과, 구간 밖의 수들에서 각각 하나씩 뽑아, 이 두 정점의 cost를 dp에 다 더해줄 것이다. 행렬이 이미 주어졌으므로 2차원 누적합을 사용하면 빠르다.
불가능한 경우를 생각해보자. 삼각형의 두 변은 색이 같고, 나머지 한 변은 다른 두 변과 다른 색이다. 이는 삼각형에서 두 변의 색이 다른 경우는 2가지임을 뜻한다. 즉, 지금 보고 있는 정점 u와 연결된 모든 간선을 확인했을 때, 각 색의 개수를 a, b라고 하자. 정점 u가 포함되는 '불가능한 삼각형'의 개수는 당연히 a * b다.
이들의 합을 2로 나눈 값을, nC3에서 빼주면 끝이다.
깊은 관찰이 필요했다. 어떤 정점을 부모 정점에 합치는 것을 생각해보자. 가중치가 최대인 정점을 먼저 부모로 합쳐주는 것은 적어도 손해는 아니다. 즉, 이러한 정점을 부모로 바로 합쳐주는 답이 존재하므로, 꼭 루트에서부터 내려오며 처리하지 않아도 된다. 이제 그룹 \(i\)와 그룹 \(j\)의 부모 그룹을 \(p\)라고 해보자. 그리고 \(f_k=(그룹 k까지 색칠한 횟수)\)라고 하자. \(i\)를 먼저 부모에 합치고, 다음에 \(j\)를 부모에 합친다면, 비용은 \(c_{i}f_{p} + c_{j}(f_{p}+f_{i})\)가 된다. 이 반대는, \(c_{j}f_{p} + c_{i}(f_{p}+f_{j})\)가 되는데, 식을 정리하면 \(c_i / f_i\)가 큰 것부터 합치는 것이 이득임을 알 수 있다. 어떤 그룹 i가 담당하는 \(c_i\)와 \(f_i\)를 부모 그룹과 union-find를 이용하여 합치면 된다. \(O(N^2)\)에 구현해도 충분히 AC받는다. 우선순위 큐 등을 사용하여 \(O(NlogN)\)으로 줄일 수 있다.
위 문제처럼 exchange argument를 이용해보자. 문제 i를 풀고 다음에 j를 푸는 경우, \(M_i - R_{i}P_i + M_j - (R_i+R_j)P_j\)점을 얻는다. 점수를 최대한 많이 얻어야 하므로, 식을 정리하면 \(R_i / P_i\)가 작은 것부터 푸는 것이 이득임을 알 수 있다. 이것을 정렬한 상태에서, 냅색을 해주면 된다. \(O(NT)\)
잘린 간선을 최대한 이용해보자. 큐에 들어있는 정점들에서 어떤 정점 v로 갈 수 없는 경우는, v에서 큐에 들어있는 정점들로 가는 '불가능한 간선'의 개수가 queue_size와 동일할 때이다. v로 가는 것이 가능하다면 새로운 큐에 넣어주고, 이 새로운 큐에서 bfs를 이어서 돌려주면 된다.
suapc는 그냥 멱살잡히고 끌려갔다.
코드포스 때문에 이건가 싶으면 무지성으로 구현하는 습관이 생겨버린 것 같다. 부계로 해서 좀 생각하는 코포를 해야겠다....
'백준 문제풀이' 카테고리의 다른 글
| 9/12 ~ 9/18 PS (+ 앳코더 민트) (0) | 2022.09.19 |
|---|---|
| 9/5 ~ 9/11 PS (0) | 2022.09.11 |
| 8/23 ~ 8/28 PS (0) | 2022.08.29 |
| 8/15 ~ 8/20 PS (1000 Solve) (8) | 2022.08.20 |
| 8/8 ~ 8/14 PS (0) | 2022.08.14 |