오늘의 PS (14) - 220620

랜덤 디펜스를 다시 시작한다. 범위는 동아리 부원들도 같이 하라고 G3~P2정도로 내렸는데, 일단 오늘은 나밖에 안하긴 했다.

 

16724 - 피리 부는 사나이

 

Functional Graph에서 사이클의 개수를 구하면 된다. 며칠 전에 앳코더에 비슷한 문제가 나와서 구현도 어렵지 않게 할 수 있었다.

 

2632 - 피자판매

 

각 피자에서 \(O(N^2)\)개의 합을 누적합을 통해 뽑아준 후, 이분 탐색으로 만족하는 쌍의 개수를 찾을 수 있다. 시간 복잡도는 \(O(N^2logN)\)이다.

 

23089 - 사탕나무

 

내 풀이는 정해보다 살짝 어려운 것 같다. \(DP[x][k]\)를 \(x\)번 노드의 자손들 중 \(k\)만큼 떨어진 노드들의 개수로 정의하자. 이는 DFS를 하는 과정에서 최근 내 \(k\)개의 조상 번호를 들고 다니면 구할 수 있다. 이를 가지고 한번 더 DFS를 잘 돌려주면 정답을 구할 수 있는데, 정해는 더 간단한 것 같다.

 

17403 - 가장 높고 넓은 성

 

컨벡스 헐을 계속 구하면 된다. 예외 처리를 조금 해주어야 하긴 하는데, 별로 어렵지 않다.

 

14866 - 산만한 고양이

 

어떤 정점을 지웠을 때 사이클이 없어진다는 것은 남은 컴포넌트들이 모두 트리임과 동치이다. 이는 \(x\)번 정점을 지웠을 때 나누어지는 컴포넌트의 개수를 \(C_x\), 차수를 \(D_x\)라 할 때 \(N-1-C_x = M-D_x\)임과 동치이다. \(C_x\)는 단절점을 구하는 과정을 응용하면 구할 수 있다.