AtCoder Grand Contest 006 C 「Rabbit Exercise」

問題文

C - Rabbit Exercise

 

i番目のうさぎの座標をx[i]とする。i番目のうさぎは等確率で2x[i+1]-x[i]または2x[i-1]-x[i]にジャンプする。よってi番目のうさぎだけがジャンプするとき、ジャンプしたあとにいる座標の期待値は1/2(2x[i+1]-x[i])+1/2(2x[i-1]-x[i])=x[i+1]+x[i-1]-x[i]である。

今k番目のジャンプのあとの各うさぎのいる座標の期待値E[k][i]がわかっているとする。k+1番目にジャンプするうさぎをr番目のうさぎとすると、期待値の線形性からE[k+1][r]=E[k][r+1]+E[k][r-1]-E[k][r],E[k+1][i]=E[k][i] (i≠rのとき)が成り立つ。よって、結局長さNの数列xが与えられて、x[a[i]]をx[a[i]+1]+x[a[i]-1]-x[a[i]]に置きかえることを繰り返したとき最終的に得られる数列を求めればいいことになる。

もちろんこのまま単純にシミュレーションするとO(MK)かかって間に合わないので、周期性をさがす。

ここでd[i]=x[i+1]-x[i]と置いてみる。そうするとx[a[i]]をx[a[i]+1]+x[a[i]-1]-x[a[i]]に置きかえるという操作は、

d[a[i]]←x[a[i]+1]-(x[a[i]+1]+x[a[i]-1]-x[a[i]])=x[a[i]]-x[a[i]-1]=d[a[i]-1]

d[a[i]-1]←(x[a[i]+1]+x[a[i]-1]-x[a[i]])-x[a[i]-1]=x[a[i]+1]-x[a[i]]=d[a[i]]

より、d[a[i]]とd[a[i]-1]をスワップするというより簡単な操作で言いかえられる!

こうなると1セットの体操はある置換で表せるので、その置換をK回行ったときのdを簡単に求められる。

 

差に注目するというテクニックが上手く活用できた。