Expected Number of Restriction Sites

https://rosalind.info/problems/eval/

ROSALIND | Expected Number of Restriction Sites

Problem

Say that you place a number of bets on your favorite sports teams. If their chances of winning are 0.3, 0.8, and 0.6, then you should expect on average to win 0.3 + 0.8 + 0.6 = 1.7 of your bets (of course, you can never win exactly 1.7!)

More generally, if we have a collection of events A1,A2,…,AnA1,A2,…,An, then the expected number of events occurring is Pr(A1)+Pr(A2)+⋯+Pr(An)Pr(A1)+Pr(A2)+⋯+Pr(An) (consult the note following the problem for a precise explanation of this fact). In this problem, we extend the idea of finding an expected number of events to finding the expected number of times that a given string occurs as a substring of a random string.

Given: A positive integer nn (n≤1,000,000n≤1,000,000), a DNA string ss of even length at most 10, and an array AA of length at most 20, containing numbers between 0 and 1.

Return: An array BB having the same length as AA in which B[i]B[i] represents the expected number of times that ss will appear as a substring of a random DNA string tt of length nn, where tt is formed with GC-content A[i]A[i] (see “Introduction to Random Strings”).

Sample Dataset

10
AG
0.25 0.5 0.75

Sample Output

0.422 0.563 0.422

 

 이 문제는 주어진 GC 비율로 랜덤한 서열을 만들 때, 그 서열이 2번째에 주어진 서열을 몇 개나 가지고 있을지에 대한 '기댓값'을 구하는 문제이다. 기댓값 혹은 평균은 각 사건에 그 사건의 확률을 곱해 다 더하면 구해진다. 그러므로 이 문제도 GC비율을 통해 주어진 서열일 확률에 서열이 있을 자리의 개수를 곱하면 된다. 전자는 GC비율을 이용해서 구하고 후자는 랜덤한 문자열의 길이에 주어진 문자열의 길이를 빼고 +1을 하면 구해진다.

n=int(input())
s=input()
A=list(map(float,input().split()))
B=[]

for i in A:
    pA=(1-i)/2
    pC=i/2
    p=1
    for j in s:
        if j=='A' or j=='T':
            p*=pA
        elif j=='C' or j=='G':
            p*=pC

    B.append(str(p*(n-len(s)+1)))
fi=open(r'파일경로','w')
fi.write(' '.join(B))