期待値の独立性について
例; 転置数
問題
解説
- 要素を各々独立に考える必要がある
解答
import itertools
N = int(input())
LR = []
for n in range(N):
l,r=map(int,input().split())
LR.append( (l,r) )
exps = 0
for (l0, r0), (l1, r1) in itertools.combinations(LR, 2):
is_tenchi = 0
total = 0
for i in range(l0, r0+1):
for j in range(l1, r1+1):
if i > j:
is_tenchi += 1
total += 1
exps += is_tenchi / total
print(exps)
例; サイコロ
問題
解説
- サイコロ同士は独立である
解答
import itertools
N, K = map(int, input().split())
A = list(map(int, input().split()))
# サイコロは独立なのですべてを独立に期待値を計算する
B = []
for a in A:
b = (1 / a) * (1 / 2 * a * (a + 1))
B.append(b)
if N == K:
ans = sum(B)
else:
ans = 0
ACC = list(itertools.accumulate(B))
# 累積和から差分を取ることで計算
for i in range(0, len(ACC) - K):
ans = max(ans, ACC[i + K] - ACC[i])
print(ans)
例; ポアソン分布
問題
解説
- 厳密には独立ではないが、確率の公式から導くことができる
解答
N=int(input())
a = 0
for i in range(1,N):
a += 1/((N-i)/N)
print(a)