BOJ 23018 Increasing Sequence Card Game

문제 링크입니다.

문제 요약

길이 N의 순열에서, 맨 앞에서부터 그리디하게(뽑을 수 있으면 무조건) 뽑아서 얻는 증가 수열의 길이의 기댓값을 구하세요.

N이 작을 때는

$E_i :=$ 길이가 $i$인 순열에서의 기댓값으로 정의합니다. $E_1 = 1$입니다.

$E_{i-1}$로부터 $E_i$의 값을 유도하기 위해, 길이가 $i-1$인 순열에 원소 하나를 끼워 넣는 상황을 생각합니다. 쉬운 유도를 위해 $2$부터 $i$까지의 원소로 구성된 순열에 $1$을 끼워 넣는다고 생각합시다. 그러면 전체 순열 중 증가 수열에 $1$이 포함되는 경우의 수는, $1$이 순열의 맨 앞에 끼워넣어져야만 하므로, 모든 경우의 수의 $1 \over i$입니다. 따라서 $E_i = \sum_{k=1}^{i} {1 \over k}$입니다. 따라서 $\mathcal {O}(N)$에 $E_N$까지의 값을 전처리할 수 있습니다.

N이 클 때는

$\int {1 \over x} \ dx =\ln (\vert x \vert) + C$ 입니다. 이로부터 $N$이 충분히 크면 $\Sigma {1 \over k}$가 $\ln N + C$에 수렴할 것이라 예측할 수 있습니다. 이는 실제로 그러하고, 상수 $C$에 해당하는 값은 오일러-마스케로니 상수로 알려져 있으며, 그 값은 약 $0.5772156649$ 정도입니다. $N$의 구간을 나눠서, $N$이 작은 경우는 전처리한 값을, $N$이 큰 경우는 $\ln N +C$를 출력함으로써 실수 오차 범위 내에서 답을 구할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll mod = 1e9+7;
const long double euler = 0.57721566490;

long double d[1010101];

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	for(int i = 1; i <= 1000000; i++) d[i] = d[i-1] + (long double)1/i;
	int T; cin >> T; for(int t = 1; t <= T; t++){
		ll n; cin >> n;
		cout << "Case #" << t << ": ";
		cout << fixed << setprecision(12);
		if(n <= 1000000) cout << d[n];
		else cout << log(n)+euler;
		cout << '\n';
	}
}