プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問をやる。今回は、Q09:つりあわない男女。

タイトルが日経ほげほげの婚活イジリねたコラムっぽい。

Q: 男性20人、女性10人が到着順に並んだ場合、どこで区切っても２つのグループの男女の人数が同じにならないような到着順は何通りあるか。

val man = 20
val woman = 10
val end = Seq((19,10),(20,9))

def count(x:Int, y:Int):Int = {
  if(x < 0 || y < 0) 0
  else if(x == 0 && y == 0) 1
  else if(x != y && man - x != woman - y) count(x-1,y) + count(x,y-1)
  else 0
}

end.foldLeft(0){(z,n) => z + count(n._1, n._2)}

基本的な考え方は本の解説と同じだけど、到着順の組み合わせの求め方が違う。

この辺りの考え方は、kazu-yamamotoさんの再帰ドリル、特に再帰のこころがわかりやすくて参考になる。