Learning Algorithms

アルゴリズムの勉強メモ

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;
}