AOJ 2303 - Marathon Match

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2303

概要

N 人の人がマラソンをする． 途中 M 箇所に休憩所があり，i 番目の人は確率 P[i] で休憩を T[i] だけとる． i 番目の人は一定の速度 V[i] で走る． マラソンの長さは L である．

このとき，i 番目の人が優勝する確率をそれぞれ出力する． ただし，2人以上同時に最初にゴールしたときは，優勝者はいないことにする．

制約

解法

ps[i][j] = i 番目の人が j 回休憩をとる確率

という表と，

ts[i][j] = i 番目の人が j 回休憩をとったときにかかる時間

という表を作って計算する．

i 番目の人が優勝するのは，

Σ_j Π_k P(ts[k][l] < ts[i][j])

で求められる．

P(ts[k][l] < ts[i][j]) を計算するとき，ps[i][j] の累積和を予め計算しておくと二分探索により log M で計算でき， 全体として O(N * M * N * log M) で計算できる．

コーナーケースとして

V[i] = 0 (i = 1 ... N)

がある．これはひどい… 

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <vector>
 4 #include <algorithm>
 5 #include <cmath>
 6 using namespace std;
 7 static const double EPS = 1e-7;
 8 
 9 struct runner {
10   int p, t, v;
11 };
12 
13 int main()
14 {
15   static double comb[55][55];
16   for (int i = 0; i <= 50; i++) {
17     comb[i][0] = 1.0;
18   }
19   for (int i = 1; i <= 50; i++) {
20     for (int j = 1; j <= i; j++) {
21       comb[i][j] = comb[i-1][j-1] + comb[i-1][j];
22     }
23   }
24 
25   int N, M, L;
26   cin >> N >> M >> L;
27   vector<runner> v;
28   bool all_zero = true;
29   for (int i = 0; i < N; i++) {
30     runner r;
31     cin >> r.p >> r.t >> r.v;
32     v.push_back(r);
33     if (r.v != 0) {
34       all_zero = false;
35     }
36   }
37 
38   if (all_zero) {
39     for (int i = 0; i < N; i++) {
40       cout << "0.0000000" << endl;
41     }
42     return 0;
43   }
44 
45   vector<vector<double> > ps(N, vector<double>(M+1));
46   vector<vector<double> > ps_integral(N, vector<double>(M+1));
47   vector<vector<double> > ts(N, vector<double>(M+1));
48   for (int i = 0; i < N; i++) {
49     for (int j = 0; j <= M; j++) {
50       ps[i][j] = pow(v[i].p/100.0, j) * pow((100-v[i].p)/100.0, M-j) * comb[M][j];
51       if (j == 0) {
52         ps_integral[i][j] = ps[i][j];
53       } else {
54         ps_integral[i][j] = ps_integral[i][j-1] + ps[i][j];
55       }
56       ts[i][j] = double(L)/v[i].v + v[i].t*j;
57     }
58   }
59 
60   for (int i = 0; i < N; i++) {
61     double ans = 0.0;
62     for (int j = 0; j <= M; j++) {
63       double p = 1.0;
64       for (int k = 0; k < N; k++) {
65         if (k != i) {
66           int l = lower_bound(ts[k].begin(), ts[k].end(), ts[i][j]+EPS) - ts[k].begin();
67           if (l != 0) {
68             p *= (1.0 - ps_integral[k][l-1]);
69           }
70         }
71       }
72       ans += ps[i][j] * p;
73     }
74     printf("%.6f\n", ans + EPS);
75   }
76   return 0;
77 }
aoj/2303.cc