You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
일단, 성공 확률을 p 라고 할 때, 성공할 때까지 수행 할 때의 시도 횟수는 확률의 역수(1/p)가 된다. 라는 사실을 알아야 풀 수 있는 문제.
증명은 에디토리얼을 참고하면 되고 직관적으로 보자면 확률 1/3 짜리가 있다고 할 때 성공의 기댓값은 역수인 3회가 된다.
이를 이용해보자면 처음은 1개를 골랐으므로 나머지는 n-1개이다. n개 전부를 고르려면 나머지 중에 하나를 골라야 되고 고르는 확률은 n-1 / n 이다. 이에 따른 기댓값은 역수인 n / n-1 이다.
이제 또 다른 나머지에서 골라야 하므로 기댓값은 n / n-2 이 되고 이를 계속해서 더해나가면 된다.
Source Code
#include<iostream>
#include<iomanip>usingnamespacestd;intmain() {
int n;
cin >> n;
longdouble ans = 0;
for (int i = 1; i < n; i++)
{
ans += (longdouble)n / (n - i);
}
cout << fixed << setprecision(12) << ans << endl;
}
The text was updated successfully, but these errors were encountered:
Problem link
https://atcoder.jp/contests/abc194/tasks/abc194_d
Problem Summary
n개의 정점으로 이루어진 그래프가 있다.
현재는 그래프의 1번에 있는데 1/n 확률로 다른 정점을 선택할 수 있다. 이때 모든 정점을 선택하게 되는 시도 횟수의 기댓값을 구하는 문제.
Solution
https://blog.hamayanhamayan.com/entry/2021/03/07/000733
위 블로그를 참고함.
일단,
성공 확률을 p 라고 할 때, 성공할 때까지 수행 할 때의 시도 횟수는 확률의 역수(1/p)가 된다.
라는 사실을 알아야 풀 수 있는 문제.증명은 에디토리얼을 참고하면 되고 직관적으로 보자면 확률 1/3 짜리가 있다고 할 때 성공의 기댓값은 역수인 3회가 된다.
이를 이용해보자면 처음은 1개를 골랐으므로 나머지는 n-1개이다. n개 전부를 고르려면 나머지 중에 하나를 골라야 되고 고르는 확률은 n-1 / n 이다. 이에 따른 기댓값은 역수인 n / n-1 이다.
이제 또 다른 나머지에서 골라야 하므로 기댓값은 n / n-2 이 되고 이를 계속해서 더해나가면 된다.
Source Code
The text was updated successfully, but these errors were encountered: