[2024-02-19~] 문제 풀기 (ABC341G/ARC130F,133F/EduCF105D,111D/BOJ23719)

https://atcoder.jp/contests/abc341/tasks/abc341_g

G - Highest Ratio

풀이: 문제를 결국 어떤식으로 바꿀 수 있냐면 누적합을 $S$라고 하면, $\frac{S_j - S_i}{j-i}$가 최대가 되는 $j$를 모든 $i = 0, \cdots, N-1$에 대해서 구해야 한다. 생각하기 편하게 수열을 뒤집어서 생각하면, $i$번째 단계에서는 $(0, S_0); \cdots; (i-1, S_{i-1})$에 대해 선을 그었을 때 기울기가 가장 큰 선분을 찾아야 한다. 이는 $(0, S_0); \cdots; (i-1, S_{i-1})$ 점을 이용해서 convex한 윗쪽 hull을 관리해준다음에 $S_i$에서 접선을 긋는 것이라고 생각할 수 있다.

hull을 $x$좌표 순으로 Incremental하게 구하는 방법은 Monotone Chain을 사용하면 쉽다. 접선은 convex hull에 $(i, S_i)$까지 포함 시킨 후에 가장 마지막 선분이 접선이 된다.

 

코드: https://atcoder.jp/contests/abc341/submissions/50433537

---

https://atcoder.jp/contests/abc130/tasks/abc130_f

F - Minimum Bounding Box

풀이: 볼록함수와 오목함수에 대해서는 다음 성질이 성립한다.

• $f(x) = ax+b$는 볼록함수이다.
• 볼록함수 $f, g$에 대해 $\max(f, g)$는 볼록함수이다.
• 오목함수 $f, g$에 대해 $\min(f, g)$는 오목함수이다.
• 볼록/오목함수 $f, g$에 대해 $f+g$는 볼록/오목함수이다.
• $f(x)$가 볼록/오목함수이면, $-f(x)$는 오목/볼록함수이다.

또한, piecewise linear 함수(구간에 따라 선형인 함수)는 다음 성질이 성립한다.

• $f(x) = ax+b$는 piecewise linear이다.
• piecewise linear $f, g$에 대해 $f+g; -f; \min(f, g); \max(f, g)$ 모두 piecewise linear이다.

이제 이 관찰을 기반으로 시간에 따른 함수 $(x_{max} - x_{min}) \times (y_{max} - y_{min})$의 성질을 찾아보자.

• $x_{max}$와 $y_{max}$는 볼록하고 piecewise linear 함수의 $\max$이므로 볼록이고 piecewise linear이다.
• $x_{min}$과 $y_{min}$은 오목하고 piecewise linear 함수의 $\min$이므로 오목이고 piecewise linear이다. 그래서 $-x_{min}$과 $-y_{min}$은 볼록함수이다.
• $x_{max} - x_{min}$과 $y_{max} - y_{min}$은 두 볼록하고 piecewise linear 함수의 합이므로 볼록하고 piecewise linear이다.

이제 $(x_{max} - x_{min}) \times (y_{max} - y_{min})$를 살펴보자.

• 두 함수가 최솟값이 되는 $t_{min}$을 공유하면 $t < t_{min}$인 곳에서는 함수가 단조감소하고, $t<t_{max}$인 곳에서는 함수가 단조증가한다.
• 두 함수가 최솟값이 되는 $t$를 공유하지 않을 때, 일반성을 잃지 않고 $(x_{max} - x_{min})$이 증가하기 시작하는 시점을 $t_1$, $(y_{max} - y_{min})$ 감소하기 끝난 시점을 $t_2$라고 하자. $t_1$과 $t_2$사이에서의 $(x_{max} - x_{min}) \times (y_{max} - y_{min})$는 볼록한 $2$차 함수이기 때문에, 여기서의 최솟값을 기준으로 왼쪽은 함수가 감소하고, 오른쪽은 함수가 증가한다.

즉, 어떤 $t$를 기준으로 왼쪽에서는 함수가 감소하고 오른쪽에서는 함수가 증가하기 때문에 삼분탐색을 쓸 수 있다.

 

코드: https://atcoder.jp/contests/abc130/submissions/50433767

---

• https://atcoder.jp/contests/abc133/tasks/abc133_f

 

• https://codeforces.com/contest/1494/problem/D

 

• https://codeforces.com/contest/1550/problem/D

 

• https://www.acmicpc.net/problem/23719