CODE FESTIVAL 2016 Relay : G - 超能力 / Magician

まだまだいけます。
http://cf16-relay-open.contest.atcoder.jp/tasks/relay_g

問題

N個のカップが並んでおり、1番のカップに玉が入っている。
このカップ群に以下の処理を計Q回行う。
i回目ではA[i]個目とB[i]個目のカップを中の玉ごと入れ替える。

途中、玉の位置を左右どちらか隣のカップに移す処理を1回だけ行えるとする。
最終的に玉が来る可能性があるカップは何個あるか求めよ。

解法

カップ番号を処理に応じてswapしていく。
その際玉の入っているカップの位置も追っておき、毎回両隣のカップ番号に玉を移せることを覚えていけばよい。

int N,Q;
int A[101010],B[101010];
int D[101010];
int yes[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) D[i]=i;
	yes[0]=1;
	yes[1]=1;
	int cur=0;
	FOR(i,Q) {
		cin>>A[i]>>B[i];
		A[i]--,B[i]--;
		if(A[i]==cur) cur=B[i];
		else if(B[i]==cur) cur=A[i];
		swap(D[A[i]],D[B[i]]);
		if(cur) yes[D[cur-1]]=1;
		if(cur<N-1) yes[D[cur+1]]=1;
	}
	
	cout<<count(yes,yes+N,1)<<endl;
}

まとめ

本番はもっと面倒な手を取ってしまった。