高校への数学12月号(高数オリンピック)

(n-1)人目までの得票結果に対して、n人目の得票結果を反映させる、というのがミソです。これを一気にn人の得票パターンを網羅的に計算させようものなら、n=8くらいからPCのメモリが不足してしまい強制終了になります。実際、自分は最初にそのように素朴なコードを組んで検算していました。方針を転換して一度外部CSVに吐き出し、bash側でuniq処理をかけて再度Rubyで読み込むという操作をしてようやくn=9のときの計算結果を出すことができましたが、実行には150分ほどかかってしまいました。帰納的に処理するやり方では1秒もかかりません。やり方の工夫次第では計算量を大幅に削減できるものだと気付かされる一例になりました。
なお、解析的に計算すると、(1)は 、(2)は となり、Rubyスクリプト中では解析解との比較を実施しています。

# -*- coding: utf-8 -*-
module Define
  module_function
  def make_array(ylist)
    xlist = Array.new
    xlist[0] = ylist.count("A")
    xlist[1] = ylist.count("B")
    xlist[2] = ylist.count("C")
    xlist[3] = ylist.count("D")
    return xlist
  end
  # 決め打ちで9回計算を前提とする
  def calc_answer(vlist)
    clist = Array.new
    rlist = Array.new
    for aa in vlist
      xx = Define::make_array(aa)
      rlist.push(xx)
    end
    rlist.uniq!
    clist[0] = rlist.length
    
    # 2回目以降は帰納的に計算できる
    for ii in 2..9
      ylist = Array.new
      for bb in vlist
        xx = Define::make_array(bb)
        for rr in rlist
          yy = [rr,xx].transpose.map{|ary| ary.inject(:+)}
          ylist.push(yy)
        end
        ylist.uniq!
      end
      clist[ii-1] = ylist.length
      rlist = ylist
    end
    return clist
  end
end

if __FILE__ == $0 then
  # --- Question 1 --- #
  vlist1 = ["A","B","C","D"].repeated_combination(2).to_a
  p Define::calc_answer(vlist1)
  p (1..9).to_a.map{|ii| (ii+1)*(2*ii+1)*(2*ii+3)/3}

  # --- Question 2 --- #
  vlist2 = ["A","B","C","D"].combination(2).to_a
  p Define::calc_answer(vlist2)
  p (1..9).to_a.map{|ii| (ii+1)*(2*ii*(ii+2)+3)/3}
end

途中でやっている Array#transpose.map{|ary| ary.inject(:+)} は配列の要素どうしの和を取りたいがための操作。
qiita.com