Atcoder Grand Contest 007 C. Pushing Balls
Atcoder Grand Contest 007 C. Pushing Balls
C: Pushing Balls - AtCoder Grand Contest 007 | AtCoder
感想
難しいよ
解法
解説動画がわかりやすい。各ボールの距離に関する数列を書いて実験すると、その次のステップ(の期待値)の数列も同様に等差数列になることが証明される。
等差数列になることが証明できれば、あとは今の数列の長さ$\ N_{now}\ $と初項$\ d_{now}\ $と公差$\ x_{now}\ $より次のそれらを計算していけば良い。計算のたびに、その移動の総和の期待値、すなわち(等差数列の総和) / (項数)を足していけば答えになる。
具体的に計算すると、$\ N_{next} = N_{now} - 2,\ d_{next} = \cfrac {(N + 2) d_{now} + 5x_{now}} {N_{now}},\ x_{next} = \cfrac {(N + 4)x_{now}} {N_{now}}\ $となるので、そのように書く。
実装
#include "bits/stdc++.h" using namespace std; double calc(double n, double d, double x) { if (n == 0) return 0; double res = n * (2.0 * d + (n - 1) * x) / (2.0 * n); res += calc(n - 2, ((n + 2) * d + 5 * x) / n, (n + 4) * x / n); return res; } int main() { double n, d, x; scanf("%lf%lf%lf", &n, &d, &x); double ans = calc(2 * n, d, x); printf("%.15lf\n", ans); return 0; }