AtCoder ABC #341 (トヨタ自動車プログラミングコンテスト2024#2) : G - Highest Ratio

もうちょいテキパキ解きたかったね。
https://atcoder.jp/contests/abc341/tasks/abc341_g

問題

N要素の整数列Aが与えられる。
各Kに対し以下を求めよ。

• K以上のindex Rを選び、A[K...R]の平均値の最大値を求めよ。

解法

S(x) = A[1]～A[x]のprefix sum
とすると、問題は(K,S(K))-(x,S(x))を結ぶ線分がの傾きが最大となるxを求める問題と言い換えられる。
この時のxをf(K)とする。

Kの大きい順にf(K)を求めよう。
初期値をf(K)=K+1と置き、可能な限り以下を行う。これは多角形の凸包を求める動きに近い。

• (K,S(K))-(f(K),S(f(K)))より(K,S(K))-(f(f(K)),S(f(f(K))))の方が傾きが大きいなら、f(K)=f(f(K))で上書きする。

int N;
ll A[1010101];
ll S[1010101];
int nex[1010101];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		S[i+1]=S[i]+A[i];
	}
	nex[N-1]=N;
	for(i=N-2;i>=0;i--) {
		x=i+1;
		while(x<N) {
			y=nex[x];
			if((S[y]-S[i])*(x-i)>=(S[x]-S[i])*(y-i)) {
				x=y;
			}
			else {
				break;
			}
		}
		nex[i]=x;
	}
	FOR(i,N) {
		_P("%.12lf\n",(S[nex[i]]-S[i])*1.0/(nex[i]-i));
	}
	
	
}

まとめ

Eまでは順調だったけど、FとGでそれぞれちょっと手間取ったのが残念。