• home
  • about
  • 全ての投稿
  • ソフトウェア・ハードウェアの設定のまとめ
  • 分析関連のまとめ
  • ヘルスケア関連のまとめ
  • 生涯学習関連のまとめ

期待値の独立性

date: 2021-06-30 excerpt: 期待値の独立性について

tag: algorithm期待値の独立性


期待値の独立性について

例; 転置数

問題

  • 競プロ典型 90問; 066 - Various Arrays

解説

  • 要素を各々独立に考える必要がある

解答

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)

例; サイコロ

問題

  • AtCoder Beginner Contest 154; D - Dice in Line

解説

  • サイコロ同士は独立である

解答

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)

例; ポアソン分布

問題

  • AtCoder Beginner Contest 194; D - Journey

解説

  • 厳密には独立ではないが、確率の公式から導くことができる

解答

N=int(input())
 
a = 0
for i in range(1,N):
    a += 1/((N-i)/N)
print(a)


algorithm期待値の独立性 Share Tweet