SRM466 Div1 Medium(500) LotteryPyaterochka

TopCoder

LotteryPyaterochka

1〜5がwinning numbersと仮定しても結果は変らない。1〜5の全ての並べ方のうち、少なくとも3つが同じ行に含まれる場合が何通りか考える。

1〜5の全ての並べ方は5NC5。
5つ全部が同じ行に含まれる場合は、どの列かでN通り、1〜5の並べ方が5!通り。
4つが同じ行に含まれる場合は、4つが含まれる行と1つが含まれる行の選び方がN(N-1)通り、それぞれの行で1〜5がどの位置にあるかの選び方が5通りずつ、1〜5の並べ方が5!通り。
3つが同じ行に2つが別の行に含まれる場合は、行の選び方がN(N-1)通り、行内での1〜5の位置が5C3と5C2、1〜5の並べ方が5!通り。
3つが同じ行に2つがそれぞれ別々の行に含まれる場合は、行の選び方がN(N-1)(N-2)/2通り、行内での1〜5の位置が5C3と5C1、1〜5の並べ方が5!通り。

class LotteryPyaterochka
{
public:
    double chanceToWin( int N );
};

double LotteryPyaterochka::chanceToWin( int N )
{
    double n = N;

    return 120 * ( n + n*(n-1)*5*5 + n*(n-1)*10*10 + n*(n-1)*(n-2)/2*10*5*5 )
            / ( (5*n)*(5*n-1)*(5*n-2)*(5*n-3)*(5*n-4) );
}