プログラム解説：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 です。

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

例えば、(n, k)＝(2, 2) であれば 666666 と出力してください。
(n, k)＝(4, 2) であれば 685714 と出力してください。
なお、全てのテストケースで、 106×F(n, k) の値とその最寄りの整数は 10-3 以上離れていることが保証されています。

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

def combin(n,k)
	ret = 1

	n.downto(n-k+1){|i|
		ret *= i
	}

	k.downto(2){|i|
		ret /= i
	}

	return ret
end

def a051288(n, k)
	return (combin(n, 2*k) * 2**(n-2*k) * combin(2*k, k)).to_i
end

def a000984(n)
	return combin(2*n, n)
end

def solve(n, k)
	l = n - k
	return 0 if (l%2) == 1

	ret = Rational(a051288(n, l/2), a000984(n))
	return (ret * 1000000).to_i
end

# main
while line = gets
	line.strip!
	next if line.empty?

	n, k = line.split.map{|a| a.to_i}

	p solve(n, k)
end

解説

★★★の問題です。
この出題者の問題の場合よくあることですが、私には数学が足りないので自力では無理でOEIS行きでした。

考え方

OEIS行きなのですが、単純にOEISで答えを見つけることはできません。

まず、1..nの数字が2個ずつある2nの中からn個を選んだ時に、そこに含まれる同じ数のペアの数を総当たりで求めました。その数列は次の様になります。

		ペア数
		0	1	2
n	1	2	-	-
	2	4	2	-
	3	8	12	-
	4	16	48	6

これをOEISで調べるとA051288の数列でした。
問題は手札に残るカードの枚数で、この数列でわかるのは捨てたペアの数なのでそのまま使うことはできませんが、捨てたカードの枚数がわかれば手札の数もわかるので利用できます。

また、各行の和がパターン数の総和で、これを調べるとA000984でした。

つまり、A051288を残りの手札に対して求める様にしたものをA000984で割って1000000を掛けると答えになります。

main

入力値を数値にしてsolve()に渡し、結果を印字します。

combin(n, k)

n個の中からk個を選んだ場合の組み合わせ数を求めます。
_nC_kの公式通りです。

a051288(n, k)

A051288(n,k)を実装しただけです。

a000984(n)

A000984(n)を実装しただけです。

solve(n, k)

まず、入力値kは手札の残りなので、捨てたカードの枚数lを求めます。
lが奇数というパターンは無いのでlが奇数なら0を返します。
lの1/2がペアの数なのでa051288()の第二引数にはl/2を渡します。これでa051288()を使って捨てたペアの組み合わせ数を求めることができます。
後は分母をa000984()で計算して、結果を計算すればOKです。

私はRationalを使用していますが、これはデバッグのためです。retを印字すれば結果が分数で確認できるので問題の例を確認するためにRationalを利用しただけで、別に不要です。

雑感

最初、答えが分数（1000000倍する前）だしOEISでは探せないからやめようかと思っていましたが、分母と分子に分けて考えると絶対にOEISで見つかるな、ということで探したら予想通り見つかりました。
A000986の数列はともかく、A051288を自分で考えられる人はすごいと思います。

CodeIQ：ペア・ドロップ