# 求める期待値 expectation_value = 0 class Person attr_accessor :p, :s def to_s "(p=#@p, s=#@s)" end end # seats に person を格納する。 # person には p(倉敷市が何県の都市か知っている確率)、s(シャイ度) を入れておく def get_data seats = [] r, c = gets.split.map(&:to_i) r.times{ seats.push Array.new(c){ Person.new } } gets r.times{|i| seats[i].zip(gets.split.map(&:to_f)).each{|person,p| person.p = p/100 } } gets r.times{|i| seats[i].zip(gets.split.map(&:to_i)).each{|person,s| person.s = s } } return [seats, r, c] end seats, num_rows, num_cols = get_data # 手を挙げる人を求める def who_raise(row, bit_knows, prev_bit_raises=0) bit_raises = 0 num_raise = 0 points = row.each_with_index.map{|p,i| bit_knows[i]==1 ? 4-p.s : 0 } row.size.times{|i| points[i] += prev_bit_raises[i] } if prev_bit_raises != 0 changed = true while changed changed = false points.size.times{|i| if points[i] >= 4 points[i-1] += 1 if i-1 >= 0 points[i+1] += 1 if i+1 < points.size points[i] = 0 bit_raises |= 1 << i num_raise += 1 changed = true end } end return [bit_raises, num_raise] end # 最前列から順に処理していく # raise_probabilities は、ひとつ前の列における全て挙手の組み合わせの確率を格納する prev_raise_probabilities = [] raise_probabilities = [] num_rows.times{|r| row = seats[r] # 最前列の場合、ひとつ前の列が全くあげていないのと同じことである if r == 0 prev_raise_probabilities = Array.new(2**num_cols, 0.0) prev_raise_probabilities[0] = 1 end # 一列のそれぞれの人が知っているかどうかの組み合わせで処理を行う # 左からi人目が知っていれば bit_knows[i]==1、知らなければ bit_knows[i]==0 raise_probabilities = Array.new(1<