AOJ 2303 Marathon Match - すいバカ日誌

問題

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

問題概要

N 人のランナーがマラソンをする．コースの長さは L で，休憩所が途中に M 箇所存在する．i 人目のランナーは，どの休憩所でも全く同じ Pi パーセントの確率で休憩を取る．一度の休憩で Ti だけ時間を使う．また，それぞれのランナーは速度 Vi （一定）で走り続けるものとする．
このとき，i 人目のランナーが優勝する確率を求めなさい．ただし，複数人が同時に最初のゴール者となった場合，優勝したとはみなさない．

・制約
1 <= N <= 100
0 <= M <= 50
1 <= L <= 100000
0 <= Pi <= 100
0 <= Ti <= 100
0 <= Vi <= 100

解法

N, M が小さいので，愚直に確率を求めに行けばいい．具体的には， i 番目の人が j 回休憩したときに，優勝する確率を求め，それらを足していく．
このとき，j 回休憩する確率を求めないといけないが，これはパスカルの三角形の要領（普通にDP）で求めることができる．これは前計算しておけば良い．
i 番目の人が j 回休憩した時，t := L / Vi + Ti * j だけの時間がかかる．この時，k ( != i ) 番目の人が何回以上休憩すれば i 番目の人より遅くゴールするかを考えて，そのそれぞれの回数休憩する確率を足していけば，k 番目の人が i 番目の人より遅くゴールする確率が求まる．
これを i 番目以外の全てのランナーについて考え，掛け合わせれば，i 番目の人が優勝する確率を求めることができる．
ただし，Vk で割ったり，Tk で割ったりする場合があるので，Vk == 0 や Tk == 0 の場合は特別な処理をしないといけない．
また，同時にゴールした場合を省く必要があることもわすれない．

・反省
（ちゃんと考慮してたのに，最後に述べた点で2回WAくらいました．小数に対する処理が甘かった．そもそも何回以上休憩すればオッケーかを求める必要はなくて，とりあえず全部試してオーバーしてたら無視すれば Tk で割ったりする必要は無い．無駄なことをしてしまった．）

計算量は O(N^2M^2) となる．

ソースコード

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;

constexpr double eps = 1e-10;

int main() {
    int N, M, L;
    cin >> N >> M >> L;
    vector<vector<vector<double>>> cmb(N, vector<vector<double>>(M+1, vector<double>(M+1)));
    for(int i=0; i<N; ++i) {
        cmb[i][0][0] = 1;
    }
    vector<double> P(N), T(N), V(N);
    for(int i=0; i<N; ++i) {
        cin >> P[i] >> T[i] >> V[i];
        P[i] /= 100;
    }
    for(int i=0; i<N; ++i) {
        for(int j=1; j<=M; ++j) {
            for(int k=0; k<=j; ++k) {
                cmb[i][j][k] = cmb[i][j-1][k] * (1 - P[i]) + (k-1 >= 0 ? cmb[i][j-1][k-1] * P[i] : 0);
            }
        }
    }
    for(int i=0; i<N; ++i) {
        if(V[i] == 0) {
            cout << 0 << endl;
            continue;
        }
        double res = 0;
        for(int j=0; j<=M; ++j) {
            double t = L / V[i] + T[i] * j;
            double p = cmb[i][M][j];
            for(int k=0; k<N; ++k) {
                if(i == k || V[k] == 0) {
                    continue;
                }
                double tt = L / V[k];
                if(T[k] == 0 && tt - t <= 0) {
                    p = 0;
                    break;
                }
                int cnt = (T[k] == 0 ? 0 : ceil(max(0.0, t - tt) / T[k]));
                if(tt + T[k] * cnt - t < eps) {
                    cnt += 1;
                } 
                double pp = 0;
                for(int l=cnt; l<=M; ++l) {
                    pp += cmb[k][M][l];
                }
                p *= pp;
            }
            res += p;
        }
        cout << fixed << setprecision(10) << res << endl;
    }
}