kmjp's blog

競技プログラミング参加記です

Codeforces #645 Div2 E. Are You Fired?

なんかえらく苦戦してるな。
http://codeforces.com/contest/1358/problem/E

問題

N要素の整数列Aが与えられる。
うち後半半分は同じ値Xであることがわかっている。

Aのうち任意の位置のK要素の連続部分列の総和が正であるようなKを1つ求めよ。

解法

  • Aの総和が正ならK=Nが解となる。
  • そうでない場合、X≧0の場合前半のマイナスが大きすぎるので解はない。
  • 残りはAの総和が0以下でXも負の場合である。

その場合、各左端について右端をどこまで伸ばせるかを考えよう。
L(i) := i番目の要素を左端とする部分列のうち、総和が正を満たせる最長の長さ
R(i) := min(L(0),....,L(i))
とする。Xは負なので、L(i)は上限がある。

あとは、i+R(i)≧NとできるR(i)があればそれが解となる。

int N;
ll A[505050];
ll X;
ll S[505050];
int ML[505050];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,(N+1)/2) cin>>A[i];
	cin>>X;
	FOR(i,N-(N+1)/2) A[(N+1)/2+i]=X;
	
	FOR(i,N) S[i+1]=S[i]+A[i];
	
	if(S[N]>0) {
		cout<<N<<endl;
		return;
	}
	if(X<0) {
		int len=(N+1)/2;
		for(i=0;i<(N+1)/2;i++) {
			if(S[i+len]-S[i]<=0) break;
			int mlen=min((ll)N-i,len+(S[i+len]-S[i]-1)/(-X));
			ML[i]=mlen;
			if(i) ML[i]=min(ML[i],ML[i-1]);
			if(i+ML[i]>=N) {
				cout<<ML[i]<<endl;
				return;
			}
			
			
		}
	}
	
	cout<<-1<<endl;
	
}

まとめ

最終的なコードは短いけど、途中結構コーナーケースで苦労した。