Facebook Hacker Cup 2016 Round 1 Yachtzee
Yattaze。
解法
ある区間 [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; }