CodeIQ：急行停車駅をどこにする？

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「急行停車駅をどこにする？」（CodeIQ）を参照してください。

問題の概要

問題を引用します。
電車で移動するとき、距離が長くなると各駅停車よりも急行や特急といった電車を利用したくなります。
今回は急行と特急の停車駅を考えます。

全部で n 個の駅があり、そのうち急行の停車駅が a 個、特急の停車駅を b 個とします。
なお、特急の停車駅には必ず急行が停車するものとします。
駅が環状につながっていることはなく、開始駅と終了駅は急行、特急のいずれも停車します。

与えられる n, a, b には n > a > b > 1 の関係があるものとします。
このような停車駅の配置が何通りあるかを求めてください。

例えば、n = 4, a = 3, b = 2 のとき、以下の2通りがあります。
駅急行停車駅特急停車駅
A〇〇
B〇×
C××
D〇〇
駅急行停車駅特急停車駅
A〇〇
B××
C〇×
D〇〇

【入出力サンプル】
標準入力
4 3 2

標準出力
2

なお、出力内容が32bitの整数で収まるような入力が与えられるものとします。

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

def C(n,r)
	if r == 0 then return 1 end

	ret = 1
	n.downto(n-r+1){|i| ret *= i}
	r.downto(2){|i| ret /= i}
	return ret
end

def solve(n,a,b)
	xn = n-2
	xa = a-2
	xb = b-2

	t = C(xn, xb)
	e = C(xn-xb, xa-xb)

	return t*e
end

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

	n, a, b = line.split.map{|v| v.to_i}
	p solve(n,a,b)
end

解説

この出題者の問題の中では1、2を争う簡単さだったと思います（2016.12.13現在）。
プログラミングの問題というより高校数学の問題です。

考え方

まず、最初と最後の駅には必ず止まるので実際に考えるべき箇所はそれ以外になります。
特急が止まる駅のパターンは最初と最後の駅以外の駅数から特急の停車駅数-2（最初と最後の駅を除いたもの）を選ぶ組み合わせ数です。
急行だけが停車できる駅数は（急行停車駅数-特急停車駅数）なので、急行だけが停車できる駅のパターンは（全駅数-特急停車駅数）から（急行停車駅数-特急停車駅数）を選ぶ組み合わせ数です。

なので、
n-2Cb-2 * n-bCa-b
が答えになります。

main

入力値を数値に変換し、solve()に渡します。
solve()が結果を返すのでそれを印字して終わります。

solve(n)

考え方に書いた通りの計算をして結果を返します。
私の実装ではn、a、b全部から最初と最後の駅数2を引いてから計算していますが18行目のC(n,r)の引数に与えられた-2は相殺するので考え方と同じになります。

C(n, r)

組み合わせ数を計算します。
nCrの公式通りです。

雑感

いろんな問題でnCrの関数を書いています。別に難しいわけでもないので構わないのですが、nPrと合わせて標準関数にあったら便利なのに。