066.md

066 - Various Arrays (★5)

解答

#include <iostream> // std::fixed
#include <vector>
#include <iomanip> // std::setprecision()

double CalcExpected(int L0, int R0, int L1, int R1)
{
	// 転倒数の個数
	int count = 0;

	// i: 現在の値
	for (int i = L0; i <= R0; ++i)
	{
		// k: 次の値
		for (int k = L1; k <= R1; ++k)
		{
			if (i > k)
			{
				++count;
			}
		}
	}

	// 期待値を返す
	return static_cast<double>(count) / ((R0 - L0 + 1) * (R1 - L1 + 1));
}

int main()
{
	// 長さ N の数列
	int N;
	std::cin >> N;

	// 数列の各要素は L[i] 以上 R[i] 以下のランダムな整数
	std::vector<int> L(N), R(N);
	for (int i = 0; i < N; ++i)
	{
		std::cin >> L[i] >> R[i];
	}
	
	// 期待値の合計
	double result = 0.0;
	
	for (int i = 0; i < N; ++i)
	{
		for (int k = i + 1; k < N; ++k)
		{
			result += CalcExpected(L[i], R[i], L[k], R[k]);
		}
	}

	// 小数点以下 10 桁まで表示
	std::cout << std::fixed << std::setprecision(10) << result << '\n';
}