TCO19 Round3A Med: WaitingForBusAgain

問題概要

原文 → TopCoder Statistics - Problem Statement

種類のバスがあり、 番目のバスは 分おきに停留所に到着することがわかっている。

それぞれのバスについて、来る間隔だけはわかっているがどのタイミングからその間隔で来るかは一様にランダムである。より具体的に言えば、 番目のバスについてある一様乱数 があって、時刻 ( は整数) に停留所に到着する。これらの乱数はそれぞれのバスについて独立に定まる。

このとき、次に停留所に到着するバスのインデックスの期待値を求めよ。

解説

本番出たときは全くわからなかった。

Codeforces のブログに Writer が簡潔に解説を書いている ので、それの前半だけ読んでまたやってみた。

最も頻繁に来るもの、つまり が最も小さいものに着目し、これを とする。バスは 分以内に必ずなにか来るので、長さ のスリットの中にバスがどのように来るかを考えればよい。

まず、各バスについて 以内に到着する確率は である。また、 以内に到着するという条件のもとで考えたときに、( の範囲で) 時刻 に来る確率がどのようになるかを考えたとき、これは の値によらず一様な確率を持つ。このことから、 以内に到着するバスが 台存在するとき、そのうちのどれが最初に到着するかについて、すべて確率 である。

これらを考察すると、 番目のバスまで見て、そのうち 台のバスが 以内に到着するときの期待値 という DP ができる。期待値のテーブルと確率のテーブルを両方持つ必要がある。

ソースコード

struct WaitingForBusAgain {
    double expectedBus(vector<int> f) {
        int N = f.size();
        int mi = *min_element(f.begin(), f.end());

        vector< vector<double> > dp(N+1, vector<double>(N+1));
        vector< vector<double> > prob(N+1, vector<double>(N+1));
        prob[0][0] = 1.0;
        for(int i=0; i<N; i++) {
            double p = 1.0 * mi / f[i];
            for(int j=0; j<=i; j++) {
                if(prob[i][j] == 0) continue;
                
                // slit の中に入れる
                prob[i+1][j+1] += prob[i][j] * p;
                dp[i+1][j+1] += dp[i][j] * p * j / (j+1) + prob[i][j] * p * i / (j+1);

                // slit の中に入れない
                prob[i+1][j  ] += prob[i][j] * (1 - p);
                dp[i+1][j  ] += dp[i][j] * (1 - p);
            }
        }

        double ans = 0.0;
        for(int i=0; i<=N; i++) {
            ans += dp[N][i];
        }
        return ans;
    }
};

最初の言い換えがすべてな気はする、おもしろいね。