|
まるケン |
|
「すでに座っている人の隣にならない座席が空いている場合には、そちらを選ぶ」
これを ルール１と呼ぶことにします。 ルール１を守れなくなるまでに座れる人数は、座り方によって変わります。 例えば、6席の場合、上手に座れば3人まで座れますが、イとオに座るともう一杯。 N席に座れる最大数は、(N+1)÷2。6席なら3だし、7席、8席なら4人まで座れます。 逆に、9席の場合は、うまく座れば5人座れますが、 イ、オ、ク と座ってしまうと、3人しか座れないこともあります。 これは、N席なら(N+2)/3人と表すことができます。 つまり、9席の場合、最小3人から最大5人の3通りのパターンがあることになります。 今回のアプローチは、N席の場合に、N/３から(N+1)/2 人座れるパターンが、 それぞれの人数に対して何パターンあるかを求めようという作戦です。 さてさて、ここからが Ruby のスクリプト。 掲示板向けに、スペース2つを全角スペースに置き換えています。 # 階乗を求めるのに、Hashを使ってみました。 # 関数にしちゃうと、同じ値でも毎回同じ処理を実行するのに比べ、 # Hashだと、過去に計算したことのある数値なら、 # ほぼ即座に答えが返るんじゃないか？という期待を込めてです。 $f = Hash.new{|h,k|h[k]=k<2?1:h[k-1]*k} # nCm n個の中からm個を選ぶときの選び方の数 def ncomb(n, m) return $f[n] / $f[n-m] / $f[m] end # n個の席にm人が、隣に空席をあける条件で座るとき、座り方は何パターンあるか？ def npat(n, m) e = n - m # 空席の総数 z = m - 1 # 隣に空席をあけなければならない、必須の空席数（3人座るならその間の2か所） j = e - z # あけ足りない空席の数 k = m + 1 # あけ足りない空席を配置させられる箇所の数（両端と座っている席と席の間） s = ncomb(k, j) # k箇所から空席を配置するj個を選ぶ選び方 return s end def sol_1277(n) min = (n+2) / 3 max = (n+1) / 2 (min..max).each do |m| r = npat(n, m) # ルール１に従って座る座り方の総数：m人座るなら m!通り # ルール１後のに座る座り方の総数:残りn-m人なので(n-m)!通り # このパターンがr通りあるので、、、 $n += $f[m] * $f[n-m] * r end end (1..100).each do |n| $n = 0 sol_1277(n) p [n, $n] end |
|
おうち
12月17日（日） 16:44:35
52991 |