2020 연세대학교 컴퓨터과학과 프로그래밍 경진대회 풀이

MST에 속하지 않은 가중치가 홀수인 간선 $(u, v)$을 본다면, $u$에서 $v$로 가는 MST 상의 경로에서 가중치가 짝수이면서 가장 큰 간선을 선택하면 됩니다.
MST에 속하지 않은 가중치가 짝수인 간선 $(u, v)$을 본다면, $u$에서 $v$로 가는 MST 상의 경로에서 가중치가 홀수이면서 가장 큰 간선을 선택하면 됩니다.

Sparse Table로 구현하면 경로 최대값 쿼리를 $O(\log N)$에 할 수 있습니다.

정답 코드

백준20133 모래시계 2

여사건을 구하는 것이 편합니다.

가운데에 들어갈 정점을 고정합시다.
정점 4개를 선택하는 경우는 $n-1 \choose 4$입니다. 정점 4개를 선택해서 만들어지는 두 삼각형이 겹치는 경우의 수를 구해야 합니다.

가운데 정점을 기준으로 나머지 정점을 각도 정렬합시다. 가운데 고정한 정점과 어떤 정점 $i$을 연결하는 직선의 왼쪽에 있는 정점의 개수를 $k_i$라고 합시다. (직선 위에 있는 정점 포함, $i$는 미포함)
정점 4개를 선택해서 만들어지는 두 삼각형이 겹치는 경우의 수는 $\sum { k_i \choose 3 }$입니다.

정답 코드

백준20134 소가 연세로를 건너간 이유

$k_1 = k_2 = 0$인 경우는 Inversion Counting 문제입니다.

$k_1 = 0, k_2 ≠ 0$인 경우를 생각해봅시다. 배열을 1씩 Rotate하는 상황입니다.
그림을 몇 번 그려보면, 앞에 있는 원소를 맨 뒤로 보낼 때 Inversion의 개수의 변화를 알 수 있습니다. 자신보다 앞에 나와야하는 원소의 개수만큼 감소하고, 뒤에 나와야하는 원소의 개수만큼 증가합니다.

$k_1 = 0$이고 $k_2 = 0 \ldots N-1$일 때의 합을 $S_0$라고 합시다. 마찬가지로, $k_2 = i$일 때의 합을 $S_i$라고 합시다.
잘 생각해보면 $S_i = S_0$이라는 것을 알 수 있습니다. 자세한 설명은 생략합니다.

그러므로 문제의 정답은 $S_0 \times N$이 됩니다.

정답 코드

백준20135 연세 마스크 공장

Circulation Problem입니다.
각 정점의 Supply는 $P_i$이고, Demand는 $-P_i$입니다.

먼저 간선의 lower_bound만큼 유량을 흘린 뒤, 유량을 흘리고 남은 그래프 위에서 Maximum Flow를 돌려서 각 간선에 흐르는 유량을 구하면 됩니다.

간선의 lower_bound만큼 유량을 흘리고 난 뒤 Supply와 Demand의 합이 다르면 답이 존재하지 않습니다.

정답 코드