AtCoder AGC #007 : C - Pushing Balls

AGCは問題の消化に手間取っている。
http://agc007.contest.atcoder.jp/tasks/agc007_c

問題

N+1個の穴とN個のボールが数直線上に交互に並んでいる。
左端の穴とその次のボールの間の間隔はTであり、以後ボールと穴の間隔はDずつ等差数列の要領で増加していく。
N個のボールを順にランダムで選び、左右どちらかランダムでボールが穴に落ちるまで動かす、という処理を繰り返す。
ボールの総移動距離の期待値を求めよ。

解法

この問題はボールと穴の間隔が不均等であるが、(細かい説明は解説動画を参照してもらうとして)すべて等しく平均値を取ると考えても解は変わらない。

以下を考える。
F(x) := 残りx個のボールと、(x+1)個の穴が残っており、総長(最初と最後のボールの距離)が1でボールと穴が均等な間隔で並ぶ場合のボールの移動量期待値。
求めるのは、元の総長にF(N)を掛けた値である。

F(x)は、最も外側のボールがさらに外側に転がるケースと、それ以外のケースを考える。
前者のケースでは、残りの穴に関する総長が短くなり、それ以外は総長が維持される(逆に、穴とボールの距離を再度均等化すると距離が延びる)。
よっての関係になることがわかる。
あとはF(x)を順次求めればよい。

int N,D,X;
ll T;
double F[402020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>D>>X;
	FOR(i,2*N) T += D, D += X;
	for(x=1;x<=N;x++) F[x] = 1.0/(2*x) + ((x-1.0)/x)*(1+1.0/x)*F[x-1];
	_P("%.12lf\n",T*F[N]);
}

まとめ

推測でも距離を均等に均してよいと気づけば解は近い。