최근들어 제대로 된 PS를 하기로 했다. 그냥 무지성으로 웰논 골플 문제를 푸는 것이 아닌, 깊은 생각을 요하는 문제를 풀어야겠다...
행렬식 dp문제다. 홀수 행렬과 짝수 행렬을 곱해준 행렬을 N제곱하면, 2N번 이동했을 떄의 경우의 수가 된다. 여기에서
식을 잘 건드리면
그냥 다익스트라 돌리면 된다. 다만 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은 이분 탐색으로 찾으면 되므로, 시간복잡도는
불가능한 경우를 생각해보자. 삼각형의 두 변은 색이 같고, 나머지 한 변은 다른 두 변과 다른 색이다. 이는 삼각형에서 두 변의 색이 다른 경우는 2가지임을 뜻한다. 즉, 지금 보고 있는 정점 u와 연결된 모든 간선을 확인했을 때, 각 색의 개수를 a, b라고 하자. 정점 u가 포함되는 '불가능한 삼각형'의 개수는 당연히 a * b다.
이들의 합을 2로 나눈 값을, nC3에서 빼주면 끝이다.
깊은 관찰이 필요했다. 어떤 정점을 부모 정점에 합치는 것을 생각해보자. 가중치가 최대인 정점을 먼저 부모로 합쳐주는 것은 적어도 손해는 아니다. 즉, 이러한 정점을 부모로 바로 합쳐주는 답이 존재하므로, 꼭 루트에서부터 내려오며 처리하지 않아도 된다. 이제 그룹
위 문제처럼 exchange argument를 이용해보자. 문제 i를 풀고 다음에 j를 푸는 경우,
잘린 간선을 최대한 이용해보자. 큐에 들어있는 정점들에서 어떤 정점 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 |