Eau de Cologne
[2024-02-19~] 문제 풀기 (ABC341G/ARC130F,133F/EduCF105D,111D/BOJ23719)
https://atcoder.jp/contests/abc341/tasks/abc341_g G - Highest Ratio AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 풀이: 문제를 결국 어떤식으로 바꿀 수 있냐면 누적합을 $S$라고 하면, $\frac{S_j - S_i}{j-i}$가 최대가 되는 $j$를 모든 $i = 0, \cdots, N-1$에 대해서 구해야 한다. 생각하기 편하게 수열을 뒤집어서 생각하면, $i$번째 단계에서는 $(0, S_0); \cdots; (i-1, S_{i-1})$에 대해 선을 그었을 때 ..
rkgk
2024. 2. 19. 02:13