Editorial

B

문제 요약:

파티에 온 사람은 케이크를 먹는데, 짝과 같이 1개를 먹는다.(짝이 없으면 먹을 수 없다)

케이크는 짝수 개 만들어진다. 따라서 짝수 개의 pair의 사람이 와야 한다.

개인마다 unhappiness가 있는데, 초대받지 못한 사람의 unhappiness의 총합을 최소화해야 한다.

문제 해설:

사람을 그래프의 node로 보고, pair를 두 사람 간의 edge로 보면 degree를 구할 수 있다.

주어진 pair의 개수가 짝수 개면 그냥 다 초대하면 그만이므로 0이다.

홀수 개일 때, 두 가지 선택을 할 수 있다.

홀수 degree를 가진 사람 하나를 제거하거나(홀수 개 빠지므로 짝수 개의 pair 남음)

서로 pair를 이루고 있는 짝수 degree를 가진 사람 둘을 제거하거나(a,b가 짝이고 a와 b의 degree를 각각 2p,2q라고 할 때 둘을 제거하게 되면 $2p-1, 2p-1, 1$(둘사이 pair)개의 edge가 각각 제거되게 되므로 홀수 개의 pair가 제거되므로 짝수 개 남음)

$O(n)$으로 전부 보면 된다.

의견:

대회 도중에는 그래프와 연관해서 무언가 생각해야 한다는 것을 떠올리지도 못했다. b에 이정도로 생각을 해야 하는 문제를 냈을지는 몰라서였을까?

D

문제 요약:

$x_i$위치에 $p_i$강도의 비가 내리는데, 비가 내리면 그 자리에는 $p_i$, 한칸뒤랑 한칸 앞은 $p_i-1$만큼, i칸 차이나는 칸에는 $p_i-i$만큼 물이 축적된다.

축적된 물의 양이 $m$보다 크게 되면 홍수가 난다.

모든 비의 정보에 대해 그 비를 제외한 나머지 비의 양으로도 홍수가 나는지 구하는 문제이다.

문제 해설:

difference array 개념을 사용해서 특정한 점들(기울기가 변하는 지점)에 대해 모든 비가 온 후에 물이 축적된 양을 구한다.

만약 어떤 좌표 $j$에서 $a_j$(물이 축적된 양) > $m$이라면 이 점은 어떤 비를 막아야 홍수를 막을 수 있을까?

$p_i- \lvert x_i-j \rvert \geq a_j - m$인 비 i가 존재한다면 홍수를 막을 수 있다.

넘치는 양보다 많은 양의 영향을 끼치는 비가 근처에 있다는 뜻이기 때문이다.

어떤 점에 대해, 색칠된 부분에 그만큼 내리는 비가 존재한다면 그 점에서는 홍수가 안 나게 된다.

그런데 문제는 어떤 비를 그치게 했을 때 (모든 점에서)홍수가 나지 않는지에 관심이 있다.

따라서 모든 홍수가 나는 점($a_j > m$인 점)에 대해,

그 점에서 홍수가 나지 않게 하는 비가 존재하는 구역( $(j,a_j-m)$에서 왼쪽으로 기울기 -1, 오른쪽으로 기울기 1을 가지는 구역들, 그림에서 점 좌우로 뻗은 직선)을 구해 전부 intersect하고,

pl getIntersect(pl p1, pl p2) {
    ll tx = max(p1.first + p1.second, p2.first + p2.second);
    ll ty = max(p1.second - p1.first, p2.second - p2.first);
    return { (tx - ty) / 2,(tx + ty) / 2 };
}

그 구역(모든 교집합)에서 그만큼 내리는 비가 존재한다면 그 비를 제거했을 때 모든 점에서 홍수가 나지 않게 된다고 할 수 있다.