Yukicoder No.210 探し物はどこですか?

,

http://yukicoder.me/problems/no/210

解説を$3$つ全部見ても分からなかった。いずさんに教えてもらった。感謝。

solution

見つかるかどうかは不確定にしても、捜索を行う順番は最初から確定させられる。 その時々で最も見つかる確率の高い部屋を探すのがよい。 $i$番目の部屋を$k$回目($k \ge 1$)に捜索したときにメガネが見つかる確率$P(i,k) = p_iq_i{(1 - q_i)}^{k-1}$である。 よってこの値の大きい部屋$i$から順に捜索する。 十分に収束したら打ち切り。

proof / persuasion

以下の疑問に対する説得。

$P(i,k) = p_iq_i{(1 - q_i)}^{k-1}$は正しそうだけど、$k-1$回目に部屋$i$を探索して見つからなかったという知識があるのだから、部屋$i$にメガネがある確率$p_i$の部分にも補正があってよさそう。

まず標本空間$\Omega$を考える。 メガネは有限の時間内に見つかるとして、いつどこで見つかったかを考えている。 $\omega_{i,k}$を、$i$番目の部屋を$k$回目($k \ge 1$)に捜索したときにメガネが見つかった、という標本として、$\Omega = \{ \omega_{i,k} \mid i, k \}$とできる。

$\Sigma_k q_i{(1 - q_i)}^{k-1} = 1$により$\Sigma_i \Sigma_k P(i,k) = 1$が言える。 つまり上の$\omega_{i,k}$は全ての取りえる結果をきちんと切っている。 (だから事象でもなくて標本空間と言えるし、$P(X = \omega_{i,k}) = P(i,k)$が$\Omega$上の確率になる。) これにより$P(X = \omega_{i,k} \lor X = \omega_{i,k+1}) = P(X = \omega_{i,k}) + P(X = \omega_{i,k+1})$である。$\omega_{i,k}$と$\omega_{i,k+1}$は別の標本なのだから無関係。一般に$\omega_A \ne \omega_B$で同様のものが成り立つ。

探索失敗の知識に関しては実際に効いてくる。 何らかの部屋$i$を$k$回目に捜索して失敗したという知識$X \ne \omega_A$があったとする。 これにより他の捜索が成功$X = \omega_B$することに関する確率/尤度は、$P(X = \omega_B \mid X \ne \omega_A) = \frac{P(X \ne \omega_A \mid X = \omega_B) P(X = \omega_B)}{P(X \ne \omega_A)} = \frac{1}{1 - P(\omega_A)} \cdot P(\omega_B)$として更新される。 ここで$\omega_B$に関する制約は$\omega_B \ne \omega_A$のみである、つまり全ての事象に一様に影響する。 これは優先度の決定の際の比較において無視してよい影響である。

implementation

#include <cstdio>
#include <vector>
#include <queue>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
int main() {
    // input
    int n; scanf("%d", &n);
    vector<int> p(n); repeat (i,n) scanf("%d", &p[i]);
    vector<int> q(n); repeat (i,n) scanf("%d", &q[i]);
    // compute
    vector<long double> r(n); repeat (i,n) r[i] = (p[i] / 1000.) * (q[i] / 100.);
    auto cmp = [&](int i, int j) { return r[i] < r[j]; };
    priority_queue<int, vector<int>, decltype(cmp)> que(cmp);
    repeat (i,n) que.push(i);
    long double ans = 0;
    const long double eps = 1e-16;
    for (int k = 1; ; ++ k) {
        int i = que.top(); que.pop();
        if (r[i] < eps) break;
        ans += k * r[i];
        r[i] *= 1 - q[i] / 100.;
        que.push(i);
    }
    // output
    printf("%.6Lf\n", ans);
    return 0;
}