DOJ logoDOJ
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
問題募集ログイン新規登録
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
解説

Sum of Adjacent Minimums

問題に戻る

解説

다음 값을 생각하자.

M=max⁡1≤l<r≤Nr−lCl+Cl+1+⋯+Cr.M=\max_{1\leq l<r\leq N}\dfrac{r-l}{C_l+C_{l+1}+\cdots+C_r}.M=1≤l<r≤Nmax​Cl​+Cl+1​+⋯+Cr​.

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

직관

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

0,⋯ ,0,H,H,⋯ ,H,0,⋯ ,00,\cdots,0,H,H,\cdots,H,0,\cdots,00,⋯,0,H,H,⋯,H,0,⋯,0

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

증명

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

Solution written by GPT5.6

r−l
​
[l,r][l,r]
[l,r]
C1R1+C2R2+⋯+CNRN=XC_1R_1+C_2R_2+\cdots+C_NR_N=XC1​R1​+C2​R2​+⋯+CN​RN​=X
H=XCl+Cl+1+⋯+CrH=\dfrac{X}{C_l+C_{l+1}+\cdots+C_r}H=Cl​+Cl+1​+⋯+Cr​X​
(r−l)H=Xr−lCl+Cl+1+⋯+Cr(r-l)H=X\dfrac{r-l}{C_l+C_{l+1}+\cdots+C_r}(r−l)H=XCl​+Cl+1​+⋯+Cr​r−l​

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

N
​
ttt
Ri≥tR_i\geq tRi​≥t
iii

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

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

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

∫0∞K(t) dt≤M∫0∞∑1≤i≤NRi≥tCi dt=M∑i=1NCiRi=MX\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}∫0∞​K(t)dt​≤M∫0∞​1≤i≤NR

를 얻는다.

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

Ri=XCl+Cl+1+⋯+CrR_i=\dfrac{X}{C_l+C_{l+1}+\cdots+C_r}Ri​=Cl​+Cl+1​+⋯+Cr​X​

로 두고, 나머지 RiR_iRi​를 000으로 둔다. 그러면 조건을 만족하며 목적함수의 값은 XMXMXM이다.

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

i
​
≥
t
​
∑
​
Ci​
d
t
=Mi=1∑N​Ci​Ri​
=MX
​