AtCoder AGC #006 : C - Rabbit Exercise

これはよく解けたな。
http://agc006.contest.atcoder.jp/tasks/agc006_c

問題

1次元の座標上でN個のウサギがいる。
初期状態でi番のウサギは座標A[i]にいる。

ウサギが1セットジャンプすることを考える。
1セットはM回からなり、各セットiではジャンプするウサギA[i]が指定される。
指定されたウサギはA[i]-1かA[i]+1のどちらかのウサギを等確率で選択し、そのウサギと対称な座標に移動する。

Kセットのジャンプを行った後の各ウサギの座標の期待値を求めよ。

解法

１回ジャンプを行った後のウサギA[i]の位置の期待値はX[A[i]+1]+X[A[i]-1]-X[A[i]]となる。
これはよく考えると、X[A[i]-1]～X[A[i]]の距離とX[A[i]]～X[A[i]+1]の距離をswapしたことに等しい。

これに気が付くとあとは簡単。
D[i]=X[i+1]-X[i]となる数列Dを考える。
1セット分のジャンプ後にD[i]の要素がどうswapされるかを求めれば、ダブリングの要領でMセット分のジャンプ後にDがなるかを求めることができる。
あとは求めたDからXを復元しよう。

int N;
ll X[101010];
int M;
ll K;
int A[62][101010];
int B[101010],C[101010];

void doswap(int a[101010],int b[101010],int c[101010]) {
	int i;
	FOR(i,N-1) c[i]=b[a[i]];
}

void solve() {
	int i,j,k,l,r,x,y;
	
	cin>>N;
	FOR(i,N) cin>>X[i];
	FOR(i,N-1) A[0][i]=B[i]=i;
	cin>>M>>K;
	FOR(i,M) {
		cin>>x;
		swap(A[0][x-2],A[0][x-1]);
	}
	
	for(i=0;i<=60;i++) {
		if(K&(1L<<i)) {
			doswap(B,A[i],C);
			swap(B,C);
		}
		doswap(A[i],A[i],A[i+1]);
	}
	
	ll s=X[0];
	FOR(i,N) {
		cout<<s<<endl;
		s+=X[B[i]+1]-X[B[i]];
	}
	
}

まとめ

よくこういう問題設定考えられるな。