yukicoder No.210 探し物はどこですか?
問題
No.210 探し物はどこですか? - yukicoder
部屋が個あり,そのどこかにメガネがある.
番目の部屋にある確率がでその部屋を見た時に見つけられる確率がである.
メガネを見つけるまでの部屋を見る回数の期待値を最小にする問題.
解法
回目に番目の部屋を見た時にメガネが見つかる確率はになる.毎回部屋を選ぶときはこの確率が一番大きい部屋を選べば期待値が最小になる.シュミレーションをして求める期待値に近づけていく.優先度付きキューを使って部屋を選ぶと良い.
#include <iostream> #include <vector> #include <algorithm> #include <queue> using namespace std; #define RREP(i,s,e) for (i = s; i >= e; i--) #define rrep(i,n) RREP(i,(int)(n)-1,0) #define REP(i,s,e) for (i = s; i <= e; i++) #define rep(i,n) REP(i,0,(int)(n)-1) #define INF 100000000 typedef long long ll; int main() { int i, N; double P[1000], Q[1000]; double ans = 0; priority_queue<pair<double,int>> q; cin >> N; rep (i,N) { cin >> P[i]; P[i] /= 1000; } rep (i,N) { cin >> Q[i]; Q[i] /= 100; } rep (i,N) q.push(make_pair(P[i]*Q[i],i)); for (i = 1;; i++) { double x = q.top().first; int y = q.top().second; q.pop(); ans += i * x; q.push(make_pair(x*(1-Q[y]),y)); if (i * x < 0.00001) break; } cout << ans << endl; return 0; }
難しかった.
確率の苦手意識を払拭したい.