AtCoder ARC #072 : E - Alice in linear land

この回はEもFも解けず仕舞い。
http://arc072.contest.atcoder.jp/tasks/arc072_c

問題

初期状態でプレイヤーは目的地よりD遠い場所にいる。
この状態でN回整数を入力する。
入力した数字の分、目的地に対して移動する。ただし移動後目的地を通り過ぎて移動前以上の距離になってしまうようなら移動しない。

入力予定のN回分の整数D[i]が与えられる。
i番目の整数を任意に変更できるとき、プレイヤーの目的地への到達を阻止できるか答えよ。

解法

まず整数変更をしない場合、目的地にたどり着くか判定しておこう。
何もしなくても到達する場合は妨害する必要がない。
また、i回目の整数を変更する場合、それ以前に到達してしまっている場合は妨害できない。

i回目の整数入力の前の目的地までの距離をX[i]とする。
整数を変更しても、X[i]より遠い場所に移動することはない。
逆に、X[i]より近い任意の位置に移動させることができる。
よって距離が1～X[i]の間に、その後の入力で目的地に到達できないような場所があるかどうかを判定すればよい。
そのような場所のうち、距離が最小の値をNG[i]とする。NG[i]≦X[i]なら、阻止できる。

NG[i]は後ろから求めていくことができる。
阻止する側はNG[i]をできるだけ大きくしたいので、NG[i+1]がわかっている状態で、X[i]の適用前にNG[i]がどんな位置を取れるかを考える。

• NG[i+1]≦X[i]/2の場合、NG[i]≦X[i]/2の場合X[i]の入力によって移動しないのでNG[i]=NG[i+1]
• NG[i+1]＞X[i]/2の場合、X[i]の入力によってNG[i+1]に到達するのは、入力前にX[i]より遠い位置にいたとき(近い場合にそのような場所に移動することはない)なのでNG[i]=NG[i+1]+X[i]

int N,D;
ll Q;
ll X[505050];
ll L[505050];
int QQ[505050];
ll NG[501010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>D;
	L[0]=D;
	FOR(i,N) {
		cin>>X[i];
		L[i+1]=min(L[i],abs(L[i]-X[i]));
	}
	
	cin>>Q;
	FOR(i,Q) cin>>QQ[i];
	
	NG[N]=1;
	for(i=N-1;i>=0;i--) {
		if(NG[i+1]<=X[i]/2) NG[i]=NG[i+1];
		else NG[i]=NG[i+1]+X[i];
	}
	
	FOR(i,Q) {
		x = QQ[i];
		if(L[x-1]==0 || NG[x]>L[x-1]) cout<<"NO"<<endl;
		else cout<<"YES"<<endl;
	}
	
}

まとめ

この巻き戻しややこしい。