Facebook Hacker Cup 2016 Round 1 Yachtzee

Yattaze。

問題

https://www.facebook.com/hackercup/problem/512731402225321/

解法

ある区間 [a, b] における余りが [c, d] となるとすると, あまりの期待値は (c+d)/2 で, 区間の幅 b-a と掛け算すると, (b-a)*(c+d)/2 となります。この掛け算した値のことを「期待値 x 幅」ということにします。

calc(x) = (x 以下の数での 期待値 x 幅 の合計値) とします。
すると, 答えは (calc(B) - calc(A)) / (B-A) と書けます。
例えば, 問題の Case 4 で, calc(B) = calc(20) を考えると,
区間 [0, 8] における 期待値 x 幅 は 8*4 = 32
区間 [8, 10] における 期待値 x 幅 は 2*1 = 2
区間 [10, 18] における 期待値 x 幅 は 8*4 = 32
区間 [18, 20] における 期待値 x 幅 は 2*1 = 2
で calc(20) = 68
calc(A) = calc(9) を考えると,
区間 [0, 8] における 期待値 x 幅 は 8*4 = 32
区間 [8, 9] における 期待値 x 幅 は 1*0.5 = 0.5
で calc(9) = 32+0.5 = 32.5
よって答えは (68-23.5)/(20-9) = 3.227272727
という感じです。

後は calc(x) が求められれば良いです。

sum = C[0] + C[1] + ... + C[N-1], total[i] = C[0] + C[1] + ... + C[i] とすると,
あまりの数が total[i] から total[i+1] の間になるような範囲は,
[total[i], total[i+1]], [sum+total[i], sum+total[i+1]], ...
と記述できます。

最後の区間が [n*sum+total[i], min(n*sum+total[i+1], x)] であるとすると, 最後の区間以外の n-1 個の区間については, 普通にあまりの期待値が C[i]/2, 幅が C[i] なので, 期待値 x 幅 は C[i]*C[i]/2 です。

最後の区間については, range = x-(n*sum+total[i]) として, 期待値 x 幅 は range*range/2 です。

これらを足し算した合計が calc(x) です。

const int MAXN = 100100;
int C[MAXN];
int N, A, B;

double calc(int A) {
    ll sum = 0, sub = 0;
    for (int i = 0; i < N; i++) sum += C[i];
    double ans = 0;
    for (int i = 0; i < N; i++) {
        ll nsub = sub+C[i];
        ll cnt = (A-nsub)/sum;
        if (cnt*sum+nsub < A) cnt++;
        if (cnt*sum+sub > A) cnt--;
        if (cnt*sum+sub <= A && A <= cnt*sum+nsub) {
            ll range = A-(cnt*sum+sub);
            ans += 0.5*range*range;
            cnt--;
        }
        ans += 0.5*C[i]*(cnt+1)*C[i];
        sub = nsub;
    }
    return ans;
}

void solve(int T) {
    cin >> N >> A >> B;
    for (int i = 0; i < N; i++) {
        scanf("%d", C+i);
    }
    double ans = 0;
    ans += calc(B);
    ans -= calc(A);
    ans /= B-A;
    printf("Case #%d: %.9lf\n", T, ans);
}

int main() {
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        solve(t);
    }
    return 0;
}