Codeforces #174 Div1. B. Cow Program

段々難しくなってきた。
http://codeforces.com/contest/283/problem/B

問題

N個の要素からなる数列A[2]～A[N]が与えられる。
ここで、以下の処理を行う。

1. 初期値X=1・Y=0として以下を実行する。途中X<1またはX>Nになったら終了。
2. XおよびYにA[X]を同時に足す。
3. XからA[X]を引くことと、YにA[X]を足すことを同時に行う。
4. 1に示す条件を満たす限り、2に戻る

A[1]を1～Nで変化させる場合、終了時のYの値を答える。
終了しない場合は-1を答える。

解法

まず事前処理として、A[2]～A[N]の各要素について、ステップ2を行う場合と3を行う場合についてDFSでそこから処理終了までのYの増加分を求める。
途中(ステップ3によるA[1]への到達を含め)ループが発生したら終了しない。

あとは、A[1]を1～Nにしたときの最初のステップ2を実行し、X=1+A[1]、Y=A[1]になるので、あとは事前処理で求めたX=1+A[1]の時のステップ3によるYの増加分を加算すればよい。

int N;
ll A[200005];
ll T[200005][2];
int vis[200005][2];
int TL=0;

void dfs(int cur,int step) {
	int tar;
	ll r;
	
	vis[cur][step]=1<<20; //tmp
	
	if(step==0) tar=cur+A[cur];
	else tar=cur-A[cur];
	
	if(tar<=0 || tar>N) {
		vis[cur][step]=TL++;
		T[cur][step]=A[cur];
		return;
	}
	if(vis[tar][1-step]==0) dfs(tar,1-step);
	
	if(vis[tar][1-step]==1<<20) {
		// detect loop
		T[cur][step]=-1;
	}
	else {
		// assign another
		vis[cur][step] = vis[tar][1-step];
		
		if(T[tar][1-step]==-1) T[cur][step]=-1;
		else T[cur][step]=T[tar][1-step]+A[cur];
	}
}



void solve() {
	int f,r,i,j,k,l, x,y,ma,num,nt;
	char s[100];
	
	N=GETi();
	A[1]=1LL<<50;
	FOR(i,N-1) A[i+2]=GETi();
	
	vis[1][0]=1;
	vis[1][1]=1;
	TL=2;
	T[1][0]=-1;
	
	for(i=2;i<=N;i++) {
		if(!vis[i][0]) dfs(i,0);
		if(!vis[i][1]) dfs(i,1);
	}
	
	for(i=2;i<=N;i++) {
		ll r=T[i][1];
		
		if(r>=0) {
			r+=(i-1);
			while(r>=1LL<<50) r-=(1LL<<50)-(i-1);
		}
		cout << r << endl;
	}
	
	
	return;
}

まとめ

コード中では、「A[1]でステップ3を実行してX<1になった場合」を考慮してるけど、そのためにはステップ2を実行してA[1]に到達しなければならないがそのようなケースはない(ステップ2ではXが増加するため)ので考慮不要だったね。