読者です 読者をやめる 読者になる 読者になる

AOJ 2303 Marathon Match

問題概要

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