トップページに戻る    次の競技プログラミングの問題へ    前の競技プログラミングの問題へ

ABC-028-D 乱数生成

■■■問題■■■

2つの整数N、Kが与えられます。
1以上N以下の整数のなかからどれか1つ、等確率に選ぶ機械を考えます。
その機械を3回動かした時、選ばれた3つの数の中央値がKとなる確率を求めてください。

■■■入力■■■

N K

1 行目には整数 N(1 <= N <= 100万)、K(1 <= K <= N) が空白区切りで与えられる。

■■■出力■■■

出力の中央値がKとなる確率を出力せよ。出力は標準出力に行い、末尾に改行を入れること。
なお、想定解との絶対誤差または相対誤差が(10の-9乗)以下であれば、正解として扱われる。


C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3 2");
            //0.48148148148148148148
            //中央値が2となるのは、(1回目の出力,2回目の出力,3回目の出力)が
            //●(1, 2, 2)
            //●(1, 2, 3)
            //●(1, 3, 2)
            //●(2, 1, 2)
            //●(2, 1, 3)
            //●(2, 2, 1)
            //●(2, 2, 2)
            //●(2, 2, 3)
            //●(2, 3, 1)
            //●(2, 3, 2)
            //●(3, 1, 2)
            //●(3, 2, 1)
            //●(3, 2, 2)
            //となる場合で、このいずれかが出る確率は 13/27=0.481481481 です
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 1");
            //0.25925925925925925926
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("765 573");
            //0.00147697396984624371
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        decimal[] wkArr = InputList[0].Split(' ').Select(X => decimal.Parse(X)).ToArray();
        decimal N = wkArr[0];
        decimal K = wkArr[1];

        //Kが1個の場合は、3! * K未満の数の場合の数 * Kより大きい数の場合の数
        decimal wkCnt1 = 6 * (K - 1) * (N - K);

        //Kが2個の場合は、3C1 * (N - 1)
        decimal wkCnt2 = 3 * (N - 1);

        //Kが3個の場合は、1通り
        decimal wkCnt3 = 1;

        Console.WriteLine((wkCnt1 + wkCnt2 + wkCnt3) / (N * N * N));
    }
}


解説

Kが1個、2個、3個で場合分けしてます。