ABC341 G - Highest Ratio

Competitive Programming C++ AtCoder Algorithms

2024-02-18

공식 에디토리얼

문제 링크
https://atcoder.jp/contests/abc341/tasks/abc341_g

원문 링크
https://atcoder.jp/contests/abc341/editorial/9326

2차원 평면 위에 점 \(0, 1, 2, …, N\)의 \(N + 1\)개의 점이 있다고 생각해봅시다.
여기서 점 \(0\)의 좌표는 \((x_0, y_0) = (0, 0)\), 점 \(i\)의 좌표는 \((x_i, y_i) = (i, A_1 + A_2 + … + A_i)\)입니다.
이 때 \(A_L, A_{L + 1}, …, A_R\)의 평균은 점 \(L - 1\)과 점 \(R\)을 잇는 직선의 기울기로 나타낼 수 있습니다.

\(k(1 \leq k \leq N)\)를 고정하고 수열 \(A\)의 \(k\)번째 항부터 \(r\)번째 항까지\((k \leq r \leq N)\)의 평균값으로 가능한 최댓값을 구하는 것을 생각해봅시다.
점 \(k - 1 , k, k + 1, …, N\)의 볼록 껍질을 구합니다. 점 \(k - 1 , k, k + 1, …, N\)이 모두 한 직선 위에 존재할 때, \(A_k = A_{k + 1} = … = A_N\)이며, \(r\)의 값과 상관없이 평균이 \(A_k\)가 됩니다.
그렇지 않을 때, 볼록 껍질은 유한한 넓이를 가진 영역이 됩니다. \(x\)좌표가 가장 작은 유일한 점인 점 \(k - 1\)은 볼록 껍질의 경계 위에 존재하게 됩니다.

점\(k - 1\)의 시계 방향의 다음 점이 점 \(p\)일 때, 문제의 답은 \(\frac{y_p - y_{k - 1}}{x_p - x_{k - 1}}\)이 됩니다.

왜냐하면, 점 \(k - 1\)부터 반시계 방향의 다음 점을 점 \(q\)라고 할 때, 볼록 껍질에 포함되는 점 \(i(k \leq i \leq N)\)와 점 \(k - 1\)을 잇는 직선의 기울기는 볼록 껍질의 정의로부터 (점 \(q\)와 점 \(k - 1\)을 잇는 직선의 기울기) 이상 (점 \(p\)와 점 \(k - 1\)을 잇는 직선의 기울기) 이하가 되고, 구하는 값은 점 \(i(k \leq i \leq N)\)과 점 \(k - 1\)을 잇는 직선의 기울기의 최댓값과 같으므로, 점 \(p\)와 점 \(k - 1\)을 이은 직선의 기울기인 \(\frac{y_p - y_{k - 1}}{x_p - x_{k - 1}}\)가 되기 때문입니다.

따라서 결국 각각의 \(k\)에 대해서 점 \(k - 1, k + 1, …, N\)의 볼록 껍질을 구했을 때 점 \(k - 1\)의 시계 방향의 다음 점, 바꿔 말하면 위쪽 볼록 껍질을 구성하는 점들 중에서 점 \(k - 1\) 바로 옆의 점을 알아내면 됩니다.

각각의 \(k\)에 대해 볼록 껍질을 처음부터 구하는 것은 시간 제한에 걸리지만, 점 \(N, N - 1, …, 0\)의 순서대로 점을 추가해 가면서 위쪽 볼록 껍질을 구해가는 것으로, 점 \(k - 1\)을 추가한 시점에서의 위쪽 볼록 껍질의 점들 중 점 \(k - 1\)과 그 \(1\)개 앞의 점을 잇는 직선의 기울기를 구하는 과정을 반복하면, 점 \(0, 1, …, N\)로만 구성된 점들의 집합으로 위쪽 볼록 껍질을 \(1\)번 구하는 데에 드는 계산량과 같은 계산량에 풀 수 있습니다.

점의 좌표를 구한 시점에서 이미 \(x\)좌표에 대해 정렬된 상태로 점의 정보를 얻을 수 있으므로, 그라함 스캔 등의 알고리즘을 이용하면 전체 \(O(N)\)에 답을 구할 수 있습니다.

기하 싫어…

안그래도 G는 아직 무리인 타선이지만 이번엔 심지어 기하였다… 그것도 아이디어가 필요한.

이번 ABC는 그래도 E까지 풀어냈고 F는 지문만 읽고 포기했지만, 다음엔 더 나은 결과가 있겠지.