CodeIQ MAGAZINECodeIQ MAGAZINE

数学の問題をプログラミングで解こう!「ペア・ドロップ」問題解説

2017.12.25 Category:CodeIQ問題解説・リーダーボード Tag: ,

  • 4
  • このエントリーをはてなブックマークに追加

「数学の問題をプログラミングで解こう!」シリーズ。
ババ抜きの要領でカードを捨てていったときの手元に残る枚数の確率についてでした。最初に何を固定して考えるかがポイントです。

みなさんはうまくできましたか?
ぜひ出題者のKawazoeさんによる本記事で解法をチェックしてください!
by CodeIQ運営事務局

問題のおさらい

n を自然数とします。1 から n までの自然数が 1 つずつ書かれた n 枚のカードが 2 組あります。

これら 2n 枚のカードをよく混ぜ、A と B の 2 人に n 枚ずつ配ります。

A と B は、それぞれ自分の持ち札の中に番号が一致するカードがあればその 2 枚を捨てます。

捨てられるカードを全て捨てた後の A の持っているカードの枚数が k である確率を F(n, k) とします。

例えば F(1, 0)=0, F(1, 1)=1, F(2, 0)=1/3, F(2, 1)=0, F(2, 2)=2/3, F(4, 2)=24/35 です。

標準入力から、自然数 nk (1 ≦ kn ≦ 100)が半角空白区切りで与えられます。
標準出力に 106×F(n, k) の整数部分の値を出力するプログラムを書いてください。

方針:何枚目のカードが残るかをはじめに固定

確率の求め方にはいろいろなやり方があります。ここではそのうちの一つを紹介します。A に配られたカードのうち、何枚目のカードが手元に残るかをはじめに固定してその確率を求め、そして全てのあり得る組み合わせについて確率を足し合わせる、という方針で求めます。

はじめに、A の 1~n 枚目のカードのうち、何枚目のカードが手元に残るかを固定します。ここでは話を分かりやすくするために、1~k 枚目のカードが手元に残ると仮定しましょう。後の (k+1)~n 枚目のカードが捨てられます。

さて、このような残り方をするには、各カードの数字はどうなっていないといけないでしょうか? 以下、n=13, k=5 の場合を例に、1~5 枚目が手元に残り、6~13 枚目が捨てられる確率を計算します。

まず 1 枚目についてです。これが手元に残るためには、この数字とペアのカードが B の方に配られてないといけません。そうなる確率は 13/25 です。

次に 2 枚目です。1 枚目と同じく、この数字とペアのカードが B の方に配られてないといけません。1 枚目の条件が満たされたときにそうなる確率は 12/23 です。

以降、同様にして、3 枚目、4 枚目、5 枚目に対する確率は、11/21、10/19、9/17 と求められます。

次は 6 枚目です。ここから先は、捨てられる確率を考えます。このカードが捨てられるためには、この数字とペアのカードが同じ A の方に配られてないといけません。そうなる確率は 7/15 です。

7 枚目についても、6 枚目と同様、この数字とペアのカードが A の方に配られてないといけません。そうなる確率は 5/13 です。(もし▲が 7 枚目にある場合は次の 8 枚目について考えます。)

以降、同様にして、8 枚目、9枚目に対する確率は、3/11、1/9 と求められます。

以上の確率をすべて掛け合わせたものが、はじめに固定した組みあわせでカードが残る確率となります。

最後に、全てのあり得る組み合わせについて確率を足し合わせます。あり得る組み合わせは全部で 12C5 通りで、そのすべてで上記の確率は等しいです。よって、求めるべき答えは次のようになります。

実装

ここまでできれば、あとは一般形を考えてから、コードにしていきましょう。上の式をじっと見ると、前半部分では、分数の分子を 1 ずつ減らし、分母を 2 ずつ減らせばよさそうです。さらに後半部分では、分母・分子とも 2 ずつ減らせばよさそうです。nCk の計算は定義通り行えば大丈夫です。

コード例(Python)は以下です。nk の差が奇数の場合は 0 を返しています。

def f(n, k):
    if (n-k)%2 != 0: return 0.0
    answer, p, q = 1.0, n+1, 2*n+1
    for i in range(k):
        p, q = p-1, q-2
        answer = answer*p/q
    for i in range((n-k)/2):
        p, q = p-2, q-2
        answer = answer*p/q
    for i in range(k):
        answer = answer*(n-i)/(i+1)
    return answer

n, k = map(int, raw_input().split())
print int(1000000 * f(n, k))

みんなのコード

本問の挑戦者で、コードを公開して頂いた方のコードをでまとめました。(随時追加していきます。)こちらもぜひチェックしてください。

CodeIQ「ペア・ドロップ」問題 みんなのコード

CodeIQ運営事務局より

Kawazoeさん、ありがとうございました!
現在、Kawazoeさんの最新問題が出題中です。
ぜひ挑戦してみてくださいね!

  • 4
  • このエントリーをはてなブックマークに追加

■関連記事

数学の問題をプログラミングで解こう!「LCM・パレード」問題解説... 問題のおさらい 自然数 a, b に対し、a と b の最小公倍数を LCM(a, b) と定義します。 例えば、LCM(6, 8)=24 です。 さらに、自然数 n, k に対し、n 以下の全ての自然数 m に対する LCM(k, m)÷k の値の和を F(n, k)と定義します。 例えば ...
【謎解きプログラム】正しいコードは?【仮想くじ引き】解答と解説... 【謎解きプログラム】正しいコードは?【仮想くじ引き】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間...
【謎解きプログラム】どう防ぐ?【無限ループ】解答と解説... 【謎解きプログラム】どう防ぐ?【無限ループ】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間以内に謎...
数学の問題をプログラミングで解こう!「タワー・ビルディング」問題解説... 問題のおさらい A を一辺が 1 の立方体のブロックとし、B を縦が 1、横が 1、高さが 2 の直方体のブロックとします。 (下は横から見た図です。) 自然数 n, a, b に対し、A を最大 a 個、B を最大 b 個使って、縦が 1、横が 1、高さが n の直方体の塔を作ります。 こ...
【謎解きプログラム】正しいコードは?【一人すごろく】解答と解説... 【謎解きプログラム】正しいコードは?【一人すごろく】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間...
【謎解きプログラム】中身はどうなる?【出し入れ】解答と解説... 【謎解きプログラム】中身はどうなる?【出し入れ】 本問題は、表題のテーマで、プログラムにちなんだ謎を解くというものでした。 それでは以下、各問題とその解答を見ていきましょう。 問題のオープニング ある日、出社すると、あなたのPCのログイン画面に、謎の挑戦状が表示されていた。 「24時間以内...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

CodeIQ(コードアイキュー)とは、自分の実力を知りたいITエンジニア向けの、実務スキル評価サービスです。

CodeIQご利用にあたって
関連サイト
codeiq

リクルートへ