kmjp's blog

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

Codeforces #307 Div2 C. GukiZ hates Boxes

いつもより簡単目なDiv2かと思ったら、CもEもしょうもないミスで落とした。
http://codeforces.com/contest/551/problem/C

問題

M人でN個の箱の山を片付けたい。
N個の山は1列に並んでおり、左からi個目の山にはA[i]個積まれている。
M人は左端の山のさらに左にいる。

時間1当たり、各人は一つ右の山に移動するか、目の前の山の箱を1個取り除ける。
最短でどれだけの時間ですべての箱を取り除けるか。

解法

二分探索で求めていく。
各人は一番右にある箱が残された山に移動し、その過程で残された時間右側から順に箱を取り除いていけば良い。

1個も箱がない山もあるので、コーナーケースに注意。

int N,M;
ll A[101010];
ll B[101010];

bool ok(ll V) {
	int i;
	memmove(B,A,sizeof(B));
	
	int cur=N-1;
	FOR(i,M) {
		ll v=V;
		while(cur>=0 && B[cur]==0) cur--;
		if(cur<0) return true;
		v-=(cur+1);
		if(v<0) return false;
		while(cur>=0 && v>0) {
			if(B[cur]>v) {
				B[cur]-=v;
				break;
			}
			v-=B[cur--];
		}
	}
	while(cur>=0 && B[cur]==0) cur--;
	return cur<0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	ll ret=(1LL<<60)-1;
	for(i=59;i>=0;i--) if(ok(ret-(1LL<<i))) ret -= 1LL<<i;
	cout<<ret<<endl;
}

まとめ

1個も箱がない山の処理をミスってWAした。

広告を非表示にする