ABC_194_D - Journey

[zeikar]

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

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
	int n;
	cin >> n;

	long double ans = 0;
	for (int i = 1; i < n; i++)
	{
		ans += (long double)n / (n - i);
	}

	cout << fixed << setprecision(12) << ans << endl;
}