ABC028 D問題（乱数生成）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）028 D問題をC++で解いてみました。ABC028は、2015年8月29日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 乱数生成（Difficulty : 920（参考値））

問題の詳細は、リンク先をご覧ください。

ABC028 D問題 乱数生成

場合分けして、それぞれの確率を求めます。AtCoder Problems による Difficulty は 920（参考値）でした。

解答案

C++ プログラム例（ABC028D）

3つの数字を取り、その真ん中が $k$ になる場合は、以下です。

• $a < k < b$ となる場合、6通りあります（10行目）。
• $a < k = b$ となる場合、3通りあります（11行目）。
• $a = k < b$ となる場合、3通りあります（12行目）。
• $a = k = b$ となる場合、1通りあります（13行目）。

以下が、C++プログラムです。

#include <bits/stdc++.h>
using namespace std;

int main()
{
	double n, k;
	cin >> n >> k;

	double result = 0.0;
	result += (k - 1) / n * 1 / n * (n - k) / n * 6.0;
	result += (k - 1) / n * 1 / n * 1 / n * 3.0;
	result += 1 / n * 1 / n * (n - k) / n * 3.0;
	result += 1 / n * 1 / n * 1 / n;

	cout << fixed << setprecision(12);
	cout << result << endl;

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

最後に

場合分けを丁寧に行うことがポイントでした。

引き続き ABC の問題を紹介していきます。