[Codeforces] Round #503 (Div. 1)

http://codeforces.com/contest/1019

문제도 그럭저럭 괜찮고 또 잘 풀어내서 좋았습니다.

A - Elections (Code)

내가 k+1개 이상의 표를 받고, 다른 모든 party가 k개 이하의 표를 받기 위해 필요한 cost를 $O(NlgN)$에 구할 수 있습니다. 이제 $k = 1 to N/2+1$에 대해 비용을 확인해 최솟값을 택하면 됩니다.

B - The hat (Code)

N이 4의 배수가 아니면 나와 내 partner가 가진 값의 기우성이 일치하지 않으므로 쌍이 존재하지 않음을 쉽게 보일 수 있습니다. N이 4의 배수면 EVT와 비슷한 아이디어로 생각해봅시다. 일반성을 잃지않고 A[1] < A[N/2+1]이라고 하면, 1에서 N/2+1로 갈 때는 값이 증가하고 N/2+1에서 1로 갈 때는 값이 감소하므로 반드시 중간에 일치하는 구간이 존재합니다. 이제 Binary Search로 중간을 계속 찍으면서 값이 일치하는 구간을 절반으로 줄여나가면 됩니다.

C, D도 문제를 해결하지는 못했지만 굉장히 좋은 문제라는 생각이 들었습니다.