解説

Sum of Adjacent Minimums

解説

다음 값을 생각하자.

M=\max_{1\leq l<r\leq N}\dfrac{r-l}{C_l+C_{l+1}+\cdots+C_r}.

정답은 $XM$ 이다. 따라서 누적합을 사용해 모든 구간 $[l,r]$ 을 확인하면 $O(N^2)$ 에 해결할 수 있다.

직관

처음부터 어떤 최적해가 다음과 같은 꼴이라고 예상해 보자.

0,\cdots,0,H,H,\cdots,H,0,\cdots,0

양수인 부분이 구간 이라면, 조건 에 의해 로 정해진다. 이때 목적함수의 값은 다음과 같다.

증명

임의의 가능한 $R_1,R_2,\cdots,R_N$ 을 고정하자. 음이 아닌 실수 에 대해 인 인덱스 만 남겨 보자. 남은 인덱스들은 서로 겹치지 않는 여러 연속 구간으로 나뉜다.

Solution written by GPT5.6

r−l

[l, r]

C_1R_1+C_2R_2+\cdots+C_NR_N=X

H=\dfrac{X}{C_l+C_{l+1}+\cdots+C_r}

(r-l)H=X\dfrac{r-l}{C_l+C_{l+1}+\cdots+C_r}

따라서 이러한 꼴의 해만 생각한다면 얻을 수 있는 최댓값은 $XM$ 이다.

N

t

R_i\geq t

i

그중 하나가 $[l,r]$ 이라면, 이 구간에서 서로 이웃하게 남아 있는 인덱스 쌍은 $r-l$ 개이다. $M$ 의 정의에 의해 $(r-l)\leq M(C_l+C_{l+1}+\cdots+C_r)$ 가 성립한다.

모든 연속 구간에 대해 더하면, 높이 $t$ 에서 동시에 남아 있는 이웃한 인덱스 쌍의 수는 $M\displaystyle\sum_{\substack{1\leq i\leq N\\R_i\geq t}} C_i$ 이하이다.

높이 $t$ 에서 동시에 남아 있는 이웃한 인덱스 쌍의 수를 $K(t)$ 라고 하자. 각 $(i,i+1)$ 은 $0\leq t\leq\min(R_i,R_{i+1})$ 인 동안 정확히 하나씩 세어지므로, 목적함수의 값은 $\int_0^\infty K(t)\,dt$ 이다. 따라서 위 부등식을 $t\geq 0$ 에 대해 적분하면

\begin{aligned} \int_0^\infty K(t)\,dt &\leq M\int_0^\infty \displaystyle\sum_{\substack{1\leq i\leq N\\R_i\geq t}} C_i\,dt \\ &=M\sum_{i=1}^{N}C_iR_i \\ &=MX \end{aligned}

를 얻는다.

이제 $M$ 을 만드는 구간 $[l,r]$ 을 하나 고르자. $l\leq i\leq r$ 인 모든 $i$ 에 대해

R_i=\dfrac{X}{C_l+C_{l+1}+\cdots+C_r}

로 두고, 나머지 $R_i$ 를 $0$ 으로 둔다. 그러면 조건을 만족하며 목적함수의 값은 $XM$ 이다.

따라서 $XM$ 이 정확한 최댓값이다.

i

≥

t

∑

Ci

d

t

=Mi=1∑NCiRi

=MX