急行停車駅をどこにする?
締め切りが 2016/12/27 10:00 AM なので,その 1 分後に投稿されるように予約
設問
電車で移動するとき、距離が長くなると各駅停車よりも急行や特急といった電車を利用したくなります。
今回は急行と特急の停車駅を考えます。
全部で 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の整数で収まるような入力が与えられるものとします。
============================
ご大層な問題説明だが,数 I レベルの問題
同じもの a が p 個,b が q 個,c が r 個,… ,合計 n 個あるとき,これらを全部使って1列に並べる順列の総数は n!/(p!q!r!···) 通り というやつだ
n 個の駅の始発駅と終着駅は急行も特急も停まるので,場合の数には関係ない。
残りの n-2 個の駅は,特急も急行も停まるのは,b-2 個,急行だけが停まるのは a-b 個,特急も急行も停まらないのは n-a
上の公式から求めるのは (n-a)! / (b-2)! / (a-b)! / (n-a)!
f = function(n, a, b) {
both = b-2
express.only = a-b
dont.stop = n-a
N= (b-2) + (a-b) + (n-a)
cat(factorial(N) / factorial(both) / factorial(express.only) / factorial(dont.stop))
}
> f(26, 14, 7)
2141691552