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

오늘도 대차게 망했다. B는 내가 잘 아는 유형이고 비슷한 문제도 몇 번 풀어봤는데, 풀이를 빠르게 못 떠올린 것 / 자잘한 구현 실수 여러 번 한 것 / 엄밀하게 풀이를 검증하지 못한 것 세 가지의 실수를 저질렀다. 근데 이 세 가지 실수가 버추어 세 번 치는 동안 세 번 내내 다 나왔다.. 미칠 노릇. A는 그럭저럭 잘 푼 것 같은데 B에서 삽질한게 너무 뼈아프다.

A. The Beatles

그냥 모든 경우의 수를 다 해주면 된다. 시작점이 a 혹은 k - a 둘 중 하나라고 고정하고 보면, 한 번 이동한 다음에 있을 수 있는 위치는 모든 x * k 에 대해 x * k - b 위치거나 x * k + b 위치거나 둘 중 하나다. 이 각각의 위치에 대해 다시 시작점에서 시계 방향으로 돌거나 반 시계 방향으로 돌거나 둘 중 하나의 선택이 가능하므로, 이 모든 경우에 대해 필요한 최소 움직임 수를 구해주면 답이 된다.

B. Lynyrd Skynyrd

a[l] 을 맨 왼쪽 끝으로 하는 p의 cyclic shift를 생각해보자. 이 cyclic shift를 모두 포함하는 최소 위치를 ed[l] 이라고 하면, 주어진 l ~ r 구간에 대해 min(ed[l], ... ed[r])이 r 이하라면 1, 아니면 0을 출력하면 된다. 이 때 ed[l]은 binary lifting을 써서 구할 수 있다. nxt[i] = p의 cyclic shift에서 a[i] 다음 값이 나오는 가장 가까운 오른쪽 좌표 라고 정의하면, nxt의 binary lifting 테이블을 O(MlogM) 시간에 전처리할 수 있다. 이렇게 전처리하면 각각의 l에 대해 모든 ed[l] 역시 O(MlogM)에 구할 수 있다. l ~ r 구간에 대해 min(ed[l], ... ed[r])은 오른쪽 끝에서부터 psum을 계산해도 되고, 세그트리를 써도 된다. 나는 구현이 귀찮아서 세그트리 썼다. O(N + MlogM) 또는 O(N + (M+Q)logM) 정도 시간 복잡도에 해결 가능.

C. U2

 기하다. 대충 convex hull을 쓰는 문제일 거 같다는 생각은 했는데, 2차 함수라서 그걸 적용할 수 있는 방법을 도저히 유도할 수가 없었다. 그 외에 y가 제일 높은 점부터 정렬한 후 후보를 제거한다든가 하는 여러 방법들을 생각했는데, 어떻게 해도 특정 점 위에 있는 모든 후보 점을 지우는 방법을 유도할 수가 없어서 실패했다.

 

 그래서 풀이를 봤는데, 상상 초월... y = x^2 + bx + c 꼴에서 x^2항을 옮기면 y - x^2 = bx + c 가 된다. 이러면 주어진 좌표에 대해 (x, y) 를 (x, y - x^2) 으로 바꿔서 생각하면, 주어진 포물선들의 상하 관계를 직선의 상하 관계로 볼 수 있다. 그래서 이렇게 변환한 후 변환한 점들에 대해 convex hull의 위 껍질을 구해서 그 껍질에 포함된 line segment의 개수를 구하면 답이 된다. 어제도 오늘도 주어진 수식을 적절히 변환해서 해결하는 문제에서 당했는데, 역시나 이런 쪽에서 내 수학적인 센스가 많이 부족하다는 생각이 든다. 직선이 아닌 함수도 직선으로 적절히 변환이 가능할 수 있다는 점도 기억해두자.