AtCoder ARC #128 (大和証券プログラミングコンテスト2021) : C - Max Dot

ほぼレート通りの結果。
https://atcoder.jp/contests/arc128/tasks/arc128_c

問題

整数列Aが与えられる。
ここで、以下の実数列Xを作ったとする。

• Xの和はS
• Xは昇順で、0以上M以下

AとXの内積の最大値を答えよ。

解法

最終的にXがどうなるかというと、先頭何要素かが0、その後何要素かが等しい値で、残りがMになる。
(そうでない場合、少しXの配分をずらすことで、総和を減らさずに上記の形に持ち込める)
そこで、0とMの個数を総当たりしてみるとよい。

int N,M,S;
int A[5050];
ll TS[5050];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>S;
	FOR(i,N) {
		cin>>A[i];
	}
	reverse(A,A+N);
	double ma=0;
	
	FOR(i,N) {
		TS[i+1]=TS[i]+A[i];
	}
	double ret=0;
	FOR(x,N+1) for(y=0;x+y<=N;y++) {
		if(x*M>S) continue;
		double lef=min(S-x*M,y*M);
		double a=TS[x]*M;
		
		if(y) {
			a+=lef/y*(TS[x+y]-TS[x]);
		}
		ret=max(ret,a);
		
	}
	
	_P("%.12lf\n",ret);
}

まとめ

これは最終的に思いつけて良かったね。