kmjp's blog

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

Codeforces #476 Div2 D. Single-use Stones

またしょうもないミスで上位を逃す…。
http://codeforces.com/contest/965/problem/D

問題

Wの幅の川がある。
蛙は1回で最大L以下の距離ジャンプできる。
川の途中いくつか石があり、1つの石ごとに蛙が1体乗れる。1度蛙が乗った石は以後他の蛙は乗れない。

各位置の石の数が与えられたとき、川を渡り切れる蛙は最大何体か。

解法

各位置xに石がA[x]個あるとき、[(x-L),(x-1)]の範囲にいる蛙は最大A[x]個までこの位置に止まることができる。
当然ながらできるだけ手前にいる蛙をこの石に乗せた方が、総数を最大化できる。
よって各位置の蛙の数をmap等で管理し、範囲内で手前にいる順で蛙を位置xに動かそう。

int W,L;
ll A[101010];
ll num[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>W>>L;
	for(i=1;i<W;i++) cin>>A[i];
	A[W]=1LL<<30;
	num[0]=1LL<<30;
	
	int pre=0;
	for(i=1;i<=W;i++) {
		if(pre<i-L) pre++;
		while(pre<i && A[i]>0) {
			x=min(num[pre],A[i]);
			num[pre]-=x;
			A[i]-=x;
			num[i]+=x;
			if(num[pre]==0) pre++;
		}
	}
	cout<<num[W]<<endl;
}

まとめ

まぁこれはすんなり。