Codeforces #996 : Div2 D. Scarecrow

普段のDiv2 Dより難しめ？
https://codeforces.com/contest/2055/problem/D

問題

1次元の数直線上で、カラスが原点にいる。
また、カカシの座標A[i]がそれぞれ与えられる。
カラスの現在位置がXであるとき、Xより小さな座標のうち一番Xに近いカカシの位置をYとする。
X-Y≦Kの時、カラスはX=Y+Kに移動するとする。
各カカシを秒速1で左右に移動できるとき、カラスを座標Lに移動させるのにかかる最小時間を求めよ。

解法

一番原点に近いカカシは、とりあえず原点に動かそう。
今、原点に近いカカシからn個目までのカカシが、カラスの左側に移動状態とする。
すなわち、A[n]+K=Xである。この状態に至る時刻をTとする。
この時、A[n+1]はA[n]+Kに近づくように移動すればよい。

int T;
ll N,K,L;
ll A[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K>>L;
		K*=2;
		L*=2;
		ll pos=0,tim=0;
		ll ret=1LL<<30;
		FOR(i,N) {
			cin>>A[i];
			A[i]*=2;
			if(i==0) {
				pos=K;
				tim=A[0];
				ret=tim+(L-pos);
			}
			else {
				if(pos<A[i]-tim) {
					A[i]-=tim;
					assert((A[i]-pos)%2==0);
					tim+=(A[i]-pos)/2;
					pos=(pos+A[i])/2+K;
				}
				else if(A[i]-tim<=pos&&pos<=A[i]+tim) {
					pos+=K;
				}
				else {
					pos=max(pos,A[i]+tim+K);
				}
				
				if(pos>=L) ret=min(ret,tim);
				else ret=min(ret,tim+L-pos);
			}
		}
		cout<<ret<<endl;
	}
}

まとめ

今見ると余り難しく見えないが、本番結構時間かかってるな。