2

私はこのTopCoderの問題を解決しようとしました：http ：//community.topcoder.com/stat？c = problem_statement＆pm = 10863＆rd = 14150

しかし、私の解決策は良くなく、その理由がわかりません。

私はそこで与えられた解決策を理解しました（ダウンページ：LotteryPyaterochkaを探してください）：http ：//apps.topcoder.com/wiki/display/tc/SRM+466

だから、私の問題を要約すると：

私たちは特別な種類の宝くじをしています：

この宝くじの各チケットは、N行5列の長方形のグリッドであり、各セルには1〜5*Nの整数が含まれています。1つのチケット内のすべての整数は異なります。

宝くじの主催者は、それぞれ1から5*Nまでの5つの異なる整数をランダムに選択します。5つの整数の可能なサブセットはそれぞれ、選択される確率が同じです。これらの整数は当選番号と呼ばれます。チケットは、少なくとも3つの当選番号を含む行がある場合にのみ、当選者と見なされます。

当選番号を知りたい（つまり、同じ行に少なくとも3つの当選番号がある）

だから、私は次のステップで立ち往生しました：

「当選行」に表示される5つの数字を選択する方法の数。

topCoderソリューションは言う：

（「勝者の行」に表示される5つの数字を選択する方法）=

（＃「当選行」に表示されるx個の当選番号を選択する方法）*（＃5-x「非当選番号」を選択する方法'）=

（5はxを選択）*（（5N-5）は（5-x）を選択）

この行の当選番号の数は少なくとも3であるため、xは3、4、または5になります。したがって、（「当選行」に表示される5つの番号を選択する方法）=

（5は3を選択）*（（5N-5）は2を選択）+（5は4を選択）*（（5N-5）は1を選択）+（5は5を選択）*（（5N-5）は0を選択））

そして私が言うこと：

（「勝者の行」に表示される5つの数字を選択する方法）=

（5つの当選番号のうち3つの番号）*（5N-5の非当選番号から選択する行を完成させるための2つの番号+以前に選択されなかった2つの当選番号）=

（5Nは3を選択）*（（5N-3）2を選択）

N = 10の場合、私の方法は次のようになります。（5は3を選択）*（47は2を選択）= 10810

そして、トップコーダーの方法は次のようになります：（（5は3を選択）（45は2を選択）+（5は4を選択）（45は1を選択）+（5は5を選択）*（45は0を選択））= 10126

なぜ私の方法が間違っているのですか？

ありがとう

4

1 に答える 1

2

当選番号が 1、2、3、4、および 5 であるとします。次に、当選行に 5 つの番号すべてを含むチケットを見てみましょう。

次のカウントに含まれているため、メソッドはそのチケットを何度もカウントします。

1 2 3 + two other numbers
1 2 4 + two other numbers
1 2 5 + two other numbers
1 3 4 + two other numbers
...

当選番号が 4 つのチケットでも同じことが起こります。

これが、これらのケースを別々にカウントする必要がある理由です。

于 2013-03-23T12:23:11.040 に答える