yukicoder No.210 探し物はどこですか？

これは面白い問題だなぁ。

問題

No.210 探し物はどこですか？ - yukicoder

解法

実際に最適な動きをシミュレーションする。具体的には,

・現時点で一番ある確率が高い部屋に探しに行く。今までに部屋iにx回通っていたとすると,その部屋でものを見つける確率は

で求めることができる。

実際の実装では,いちいちこの値を求める必要はなく,priority_queueに値を詰め込んでいき,ある値を取り出したら(1-q[i])を掛け算して再びpushすれば良い。

以下ソースコード

double p[1111], q[1111];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        p[i] /= 1000.;
    }
    for (int i = 0; i < n; i++) {
        cin >> q[i];
        q[i] /= 100.;
    }
    priority_queue<pair<double, int> > que;
    for (int i = 0; i < n; i++) {
        que.push(make_pair(p[i]*q[i], i));
    }
    double ans = 0;
    for (int i = 1; i < 1000000; i++) {
        auto now = que.top(); que.pop();
        ans += now.first * i;
        double next = now.first * (1-q[now.second]);
        que.push(make_pair(next, now.second));
    }
    printf("%.10lf\n", ans);
    return 0;
}