yukicoder : No.576 E869120 and Rings

これが解けないのは行かんなぁ…。
https://yukicoder.me/problems/no/576

問題

N個の宝石が円環状に並んでいる。
各石は青か赤で、それぞれの色は事前にわかっている。

この宝石のうち連続したK個以上を選ぶとき、青い宝石の割合の最大値を求めよ。

解法

青い宝石の割合とは、ようは赤い宝石を0、青い宝石を1とみなしたとき、選んだ宝石の値の平均値に一致する。
このように数が不定で平均値に関する問題では定番テクを使える。

解aを二分探索で求めよう。
平均値がa以上になる部分列を求めたい。
各宝石の値を0/1の２値でなく、a引いて(-a)と(1-a)の2値とみなそう。
元の宝石列で平均値がaを超えるというのは、a引いた後の値で平均値が0を超える、さらには合計が0を超えるのと同じである。
よって、以後合計だけ考えればよく、宝石の数で割ることを考えなくてよくなった。

後は宝石に対応する値の累積和を撮っておけば、L個目を部分列の開始位置とみなしたとき、(L+K-1)～(L+N-1)番目のいずれかを終端とする部分列のうち、合計が最大となる終端を求めば部分列の候補が求められる。
合計が最大となる終端はSegTreeやRMQで求めてもよいが、若干TLが厳しいのでスライド最小値を用いるとよい。

int N,K;
string S;
double B[1010101];

int ok(double v) {
	int i;
	FOR(i,N) B[i+1]=B[i]+S[i]-v;
	
	deque<pair<double,int>> D;
	for(i=1;i<=N/2;i++) {
		while(D.size() && D.back().first<B[i]) D.pop_back();
		D.push_back({B[i],i});
	}
	FOR(i,N/2) {
		while(D.size() && D.front().second<=i+K-1) D.pop_front();
		if(D.front().first>=B[i]) return 1;
		while(D.size() && D.back().first<B[i+N/2+1]) D.pop_back();
		D.push_back({B[i+N/2+1],i+N/2+1});
	}
	return 0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>S;
	int NB=0;
	
	N+=N;
	S+=S;
	FOR(i,N) {
		S[i]-='0';
	}
	
	double L=0,R=1;
	FOR(i,60) {
		double M=(L+R)/2;
		if(ok(M)) L=M;
		else R=M;
	}
	
	_P("%.12lf\n",(L+R)/2);
	
}

まとめ

数が不定で平均値に関する問題は、先に全要素から平均値を引いておく、というテクを覚えておこう。