오늘의 PS (15) - 220621~22

문제 풀이를 랜덤 디펜스에서 랜덤 + 그때그때 공부하고싶은 주제 기본 문제들로 바꿨다. 따라서 하루로는 글 쓸 거리가 좀 없을 수 있어서 이틀동안 푼 문제들에 대해 요약을 해 보려 한다.

 

13159 - 배열
3444 - Robotic Sort

 

어제는 스플레이 트리를 구현해보았다. 구현 자체가 크게 어려운 것 같지는 않은데 (명성에 비해), 이런걸 생각해낸 발상이 진짜 대단한 것 같다.

 

13209 - 검역소

 

이 문제와 아래 문제는 slah007 선배가 풀길래 따라 풀었다. 우선 파라메트릭을 박고 싶게 생겼으니 박은 후 생각하면, 나눌 간선을 DFS를 돌며 그리디하게 구해줄 수 있다. 이 때 정렬이 필요하기 때문에 전체 시간복잡도는 \(O(Nlog^2N)\) 정도가 된다.

 

15756 - Disruption

 

문제를 보고 HLD 레이지 세그를 박으면 된다는 것을 파악했으나, 코드 길이를 슥 둘러보니 절대 정해가 아닌 것 같길래 포기하고 열심히 정해를 찾아보았다. 해야 하는 관찰은, 어떤 간선을 쓸 수 있으려면 해당 간선의 두 정점 중 하나만 서브트리에 포함되어야 한다는 점이다. 간선의 집합을 각 서브트리에 대해 합칠 때 마다 등장 여부를 toggle 하는 방식으로 관리해주면 되는데, Small to Large를 씌우면 이를 효율적으로 수행할 수 있다.

 

10891 - Cactus? Not cactus?

1170 - 선인장의 개수

 

오늘은 선인장을 구현해보았다. 사실 진짜는 이 문제에 등장하는 버전이 아니라 간선 버전인 것 같긴 한데, 추후에 관련 문제를 풀어 볼 예정이다. 각 정점마다 해당 정점을 포함하는 단순 사이클의 개수를 구해주면 되는데, 이는 DFS Tree에서 다양한 방법으로 할 수 있는 것 같다.

 

16911 - 그래프와 쿼리

16912 - 트리와 쿼리 12
15316 - 현수시티

 

또 Offline Dynamic Connectivity도 공부해보았다. 원리나 구현 자체가 다른 D5보다 조금 어렵다고 생각해 D4를 박으려 했으나, 이미 D5로 정립된 것 같길래 그냥 납득해버렸다.

 

2215 - 원형 네트워크

랜덤 문제도 하나 풀었다. 내가 싫어하는 원형 문제인데, 다행히도 제한이 작아 제곱 풀이를 구상해볼 수 있다. 직선에서 같은 문제를 해결하는 것이 쉽다는 것에 착안해, 이 문제를 직선으로 펴 보려고 해보자. 끊을 수 있는 간선이 N개이고, 선분이 P개이니 구현에 따라 \(O(NP)\) 또는 \(O(NPlogP)\) 정도에 문제를 해결할 수 있다. 직선으로 끊을 수 있는 이유는, 답의 상한이 N-1이기 때문이다.

 

새로운 알고리즘 공부를 하다 보니 학교 랭킹 3등이 되었다. 올해 안에 1등 찍어야지