4월 2주차 정리

4.2 ~ 4.11 동안 푼 문제 정리

 

산만한 고양이

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

DFS 스패닝 트리를 만들고 Tree DP 느낌으로 서브트리 내부의 Back Edge들을 잘 카운트하고 케이스 분류하면 각 정점의 자식들을 확인하면서 사이클을 제거할 수 있는지 판단 가능하다.

 

The Bridege on the River Kawaii

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

처음 보면 좀 무서운데, $V<10$ 이라 그냥 Dynamic connectivity 10번 돌리면 된다.

 

수열과 쿼리 37

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

두유노세그

 

트리의 외심

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

두 점의 중심 3개를 모두 찾고 셋 중 하나라도 되는지 테스트 하면 된다. 증명은 안해봤는데 맞았습니다!

 

구간 합 최대? 2

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

식을 정리하면 쿼리는 $U \times K_{i} + V$ 에 대한 연속합을 구하는 것과 같다.

 

Pilots

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

슬라이딩 윈도우

 

작은 새

글을 따로 썼다. https://jjaewon.tistory.com/11

 

백설공주와 난쟁이

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

답이 있다고 가정하고 아무거나 하나 고르면 확률은 50%고, 적당히 여러번 골라보면 상당히 높은 확률로 답을 구할 수 있다.

 

JOI 국가의 행사

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

다익스트라로 각 정점에서 가장 가까운 축제장과의 거리를 전처리한다. 각 정점을 거리의 내림차순으로 정렬하고 PBS.

 

Line Friends

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

한번 이동할때 오른쪽 끝이 가장 먼 선분으로 이동하는게 최적이다. 그러면 Sparse table로 $2^{i}$ 번 이동했을때 좌표를 전처리하면 쿼리를 계산할 수 있다. 나는 Binary lifting이 갑자기 헷갈려서 그냥 뇌비우고 로그제곱 이분탐색했다. LCA 구하는때 같이 Binary lifting 하면 로그에 계산할 수 있다.

 

최단거리와 쿼리

맞왜틀