No.309 シャイな人たち (1)

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / タグ : / 解いたユーザー数 22
作問者 : LayCurseLayCurse

2 ProblemId : 846 / 出題時の順位表

Note

この問題はAdvent Calendar Contest Advent Calendar 2015の2日目の問題として作られました。

問題文

匿名希望さんが講演している時,倉敷市が何県の都市か分かる人挙手と言ったところ,$3$~$4$ 割の人しか手を挙げないという事件がありました.
倉敷市といえば,白壁が綺麗な美観地区に大原美術館もある,倉敷うどんのふるいちもある,チボリ公園は潰れてショッピングモールになりました.
とにかく,観光的にも人気スポットで,気候もとても住みやすいことで有名であります.
知名度がこんなに低い訳はないのですが,残念ながら聴衆は競技プログラミング勢であり,シャイな人が多かったため,知っていても手を挙げなかったと思われます.

それを確かめるために簡単なモデルで実験してみましょう.
シャイな人は,周りの人が手を挙げてなければ手を挙げづらいという心理が働くと考えられるので,それをモデル化したものです.
$R$ 行 $C$ 列の席があり,全ての席が聴衆で埋まっているとします.
講演は上で行われているとして,上から $i$ 行目,左から $j$ 列目の人を $(i,j)$ と書きます.
人 $(i,j)$ が倉敷市が何県の都市か知っている確率を $P_{i,j} / 100$,つまり,$P_{i,j}\%$ とし,各人が倉敷市が何県か知ってるかどうかは独立の事象とします.
また,各人 $(i,j)$ に対して,その人のシャイ度に対するパラメータ $S_{i,j} \in \{0,1,2,3,4\}$ が与えられます.

聴衆が手を挙げるかどうかは以下のメカニズムによって決定されることにしましょう.
最初,全ての人が持つポイントは $0$ で,自分が持つポイントが $4$ 以上になった瞬間に手を挙げ,挙げ続けます.
もし,人 $(i,j)$ が倉敷市が何県の都市か知っている場合は,その人は $4-S_{i,j}$ ポイントを得ます.
人 $(i,j)$ は自分の前 $(i-1,j)$,左 $(i,j-1)$,右 $(i,j+1)$ の人のそれぞれが手を挙げた瞬間に,その人 $(i,j)$ は $1$ ポイントを得ます.
つまり,前,左右の人の全てが手を挙げた場合,合計で $3$ ポイントが得られます.
前,左右に人がいない場合は,その分のポイントは得られないことに注意してください.

さて,このとき,最終的に何人の人が手を挙げるのか,期待値を求めるプログラムを書いてください.

入力

$R$ $C$

$P_{1,1}$ $P_{1,2}$ $\cdots$ $P_{1,C}$
$P_{2,1}$ $P_{2,2}$ $\cdots$ $P_{2,C}$
$\quad \vdots$
$P_{R,1}$ $P_{R,2}$ $\cdots$ $P_{R,C}$

$S_{1,1}$ $S_{1,2}$ $\cdots$ $S_{1,C}$
$S_{2,1}$ $S_{2,2}$ $\cdots$ $S_{2,C}$
$\quad \vdots$
$S_{R,1}$ $S_{R,2}$ $\cdots$ $S_{R,C}$

$1 \leq R, C \leq 11$
$0 \leq P_{i,j} \leq 100$,$P_{i,j} \in \mathbb{Z}$
$S_{i,j} \in \{0,1,2,3,4\}$

出力

手を挙げる人数の期待値を $1$ 行で出力してください.
誤差は,相対誤差または絶対誤差が $10^{-8}$ 以下であれば正答と見なされます.

サンプル

サンプル1
入力
1 2

50 50

1 0
出力
0.75

$(1,1)$ は知っている,$(1,2)$ も知っている場合は,$(1,1)$ は $4-1=3$ ポイントを,$(1,2)$ は $4-0=4$ ポイントを得ます.
よって,$(1,2)$ は手を挙げ,それを見た $(1,1)$ は $1$ ポイントを得,合計 $4$ ポイントになるために,手を挙げます.
$(1,1)$ は知らない,$(1,2)$ は知っている場合は,$(1,2)$ のみが手を挙げます.
$(1,2)$ は知らない場合は,$(1,1)$ がどうであれ,両者とも手を上げることはありません.
それぞれ知っている確率は $1/2$ で,$4$ つの場合は等確率に起こるので,$2 \times (1/4) + 1 \times (1/4) + 0 \times (1/4) + 0 \times (1/4) = 3/4$ が答えになります.

サンプル2
入力
2 2

50 50
50 50

0 1
2 0
出力
1.375

$(1,1)$ および $(2,2)$ は知っていれば,手を挙げます.
$(1,2)$ は自分が知っていて,かつ,$(1,1)$ が手を挙げれば手を挙げます.
$(2,1)$ は自分が知っていて,かつ,$(1,1)$ と $(2,2)$ の両方共が手を挙げれば手を挙げます.
よって,$(1,1)$ および $(2,2)$ が手を挙げる確率は $1/2$ で,$(1,2)$ が手を挙げる確率は $1/4$ で,$(2,2)$ が手を挙げる確率は $1/8$ です.
期待値の線形性より,答えは $1/2 + 1/2 + 1/4 + 1/8 = 1.375$ となります.

サンプル3
入力
10 10

100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100

1 2 3 4 1 2 3 4 1 2
3 4 1 2 3 4 1 2 3 4
1 2 3 4 1 2 3 4 1 2
3 4 1 2 3 4 1 2 3 4
1 2 3 4 1 2 3 4 1 2
3 4 1 2 3 4 1 2 3 4
1 2 3 4 1 2 3 4 1 2
3 4 1 2 3 4 1 2 3 4
1 2 3 4 1 2 3 4 1 2
3 4 1 2 3 4 1 2 3 4
出力
0

みんな知ってるのに….

提出ページヘ