BOJ 14571 - 모래시계

June 19, 2023

모래시계의 중심이 되는 점 $u$ 를 고려한다.

이걸 단순히 구하면 시간초과기 때문에 테크닉이 필요하다.

여기서 $u$ 와 연결되어있고 그 둘도 연결되어있는 쌍 $(a,b),~(a<b)$ 들을 모두 고려한다.

쌍들의 집합에서 $a$ 가 나오는 횟수를 $c_a$ 라고 할 때, $(a,b)$ 와 서로 다른 어떠한 $(c,d)$ 의 개수를 빠르게 셀 수 있다.

모든 쌍의 개수를 $m$ 이라고 하면 $m-c_a-c_b+1$ 이 그것이다. (포함 배제의 원리)

총 정답에서 $2$ 를 나눠준 것이 정답이 된다.

You may also enjoy