wvogel日記

自分用の技術備忘録が多めです.

気分転換

久しぶりに書きます。
なんとかして時間をつくらないと、何にも手をつけられない状態です。


明日は解析学の試験ですが、
一段落したのでcodeforcesの問題を解いてみました

問題はこちら

単純に、combinationを使ってやればいけそうです。


combinator::nCkなど、組み合わせを計算する式
boysT ::(男の人数、男の選び方)のタプルのリストを生成
girls ::(男の人数、男の選び方)から、女子の選び方を計算
myFilter ::boysTのうち、女子の人数が条件からはずれるものを弾く
answer ::girls,boysTから組み合わせ総数を計算

以下にソースコード

combinator x 0 = 1
combinator x y = product [1..x]
                    `div` (product [1..y] * product [1..x-y])

answer :: [Integer] -> Integer
answer [n,m,k] = sum.map girls $ myFilter boysT
  where
  
    myFilter xs = filter ((>=k).(+m).fst) xs
    boysT = zip [4..n] $ map (n `combinator`) [4..n]
    girls (x,y) = if k == x then 0 
                            else y *( m `combinator` (k-x))

main = getLine >>= print.answer.map read.take 3.words

Accepted!