[2020-09-07] Codeforces Round 503 (Div.1)

최대한 1일 1 virtual을 도는 걸 목표로 하고 있다. 얼마나 할 수 있을진 모르겠지만.. 대회를 계속 안 쳤더니 너무 감이 떨어져서 최대한 감을 끌어올리기 위해 열심히 하는중.

 

거하게 조졌다. A도 실제 대회였더라면 systest failed. 어처구니 없는 코딩 실수도 실수고 충분히 풀만한 문제의 풀이도 빠르게 / 정확하게 생각하지 못하게 된 것 같다. 시간 제한이 걸린 상황에서 빡세게 고민해서 푸는 훈련을 좀 많이 해야 할 필요가 있을 것 같다.

A. Elections

K표 초과를 받는게 목표일 때 그걸 달성하기 위한 최소 비용을 모든 K에 대해 구해주는 것으로도 쉽게 해결할 수 있다. 시간 복잡도는 O(N^2logN). 어처구니 없게도 반복문에서 n을 써야하는데 m을 써서 틀렸고(systest fail) 이걸 한참 못 찾았다. 그 앞에도 여러가지 하면 안 되는 코딩 실수를 했고.. 여기서 멘탈이 나가서 B 풀 때도 영향을 끼친 것 같다.

B.  The Hat

딱 봐도 이분탐색을 잘하라는 문제다. 근데 뭘 어떻게 이분탐색해야하는지를 잡는데 시간이 오래 걸렸다. n / 2가 홀수면 무조건 -1이고, 그 외에는 항상 답을 구할 수 있다. 이 부분까지는 일종의 중간값 정리 느낌으로 쉽게 유도할 수 있는데, 그 다음에 정확한 식 유도에서 한참을 헤맸다. x번 위치의 값을 A(x)이라고 했을 때 B(k) = A(k + n /2) - A(k) 로 바꿔서 쓰면 유도가 간단하다. 이걸 끝날 때까지 제대로 못 세웠다.. 왜 그랬는지 모르겠다. 거의 근처까지 왔는데 식 변환에서 애를 너무 많이 먹었다. B(k)를 저렇게 유도하고 나면, 어떤 구간 l, r에 대해 B(l), B(r)을 잡고 그 중간 위치 m에 대해 B(m)을 구하고 나면 이들간의 부호 관계를 통해 구간을 어디로 좁혀야 하는지 유도할 수 있다. l과 m이 부호가 다르면 l,m 사이로, m과 r이 부호가 다르면 m, r 사이로 구간을 좁히면 된다.