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