結果

問題 No.309 シャイな人たち (1)
コンテスト
ユーザー kura07
提出日時 2015-12-03 23:54:12
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 2,572 bytes
コンパイル時間 58 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 26,168 KB
最終ジャッジ日時 2024-09-14 08:33:26
合計ジャッジ時間 10,490 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff #
raw source code 

# 求める期待値
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<<num_cols, 0.0)
	prev_raise_probabilities.each_with_index.select{|p,b| p!=0 }.each{
		|prev_raise_probability,prev_bit_raises|
		(1<<num_cols).times{|bit_knows|
			probability = prev_raise_probability
			# bit_knows の組み合わせになる確率を計算する
			row.each_with_index{|p,i| probability *= bit_knows[i]==1 ? p.p : 1-p.p }
			# 手を挙げる人を求める
			bit_raises, num_raise = who_raise(row, bit_knows, prev_bit_raises)
			# 挙手の組み合わせの確率に加算する
			raise_probabilities[bit_raises] += probability
			# 期待値に加算する
			expectation_value += num_raise * probability
		}
		prev_raise_probabilities = raise_probabilities
	}
}

puts expectation_value
0