結果
問題 |
No.309 シャイな人たち (1)
|
ユーザー |
![]() |
提出日時 | 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
ソースコード
# 求める期待値 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