문제는 다들 아실거라 믿고...

Small 의 경우에는 ?가 최대 4개이기 때문에 K^(number of ?) 번 돌려서 구했습니다. 코딩이 많이 복잡하진 않아요.

Large 코드는 정리하지 않아서 많이 지저분합니다 ㅠ

소스코드 링크

일단 아이디어는 전체 점수의 기대값 = sum (각 칸을 반드시 포함하는 점수의 기대값) 이 됩니다. 즉, 각 칸을 반드시 포함하는 점수의 기대값을 각각 계산할 수 있으면 되지요.

y 0 0 w 0 0 z
0 y 0 w 0 z 0
0 0 y w z 0 0
x x x # x x x
0 0 z w y 0 0
0 z 0 w 0 y 0
z 0 0 w 0 0 y

www#www, xxx#xxx, yyy#yyy, zzz#zzz 이렇게 4개의 스트링이 #를 반드시 포함하는 점수의 기대값에 영향을 주게 됩니다.

여기에서 #가 ?일 때와 ?가 아닐때로 나눌 수 있어요.

i) #가 고정된 숫자일 때

위에서 얘기한 4개의 스트링을 각각 T1, T2, T3, T4라고 합니다. 우선 우리가 S4 점을 받을 확률은

P4 = 1 - { P(T1에서 S4를 못 받을 확률) * P(T2에서 S4를 못 받을 확률) * P(T3에서 S4를 못 받을 확률) * P(T4에서 S4를 못 받을 확률) }

가 됩니다. 길이 7짜리 string에서 S4를 받을 수 있는 확률은 미리 pre-calculation을 이용해서 계산해 둡니다. ( 어차피 11^7 정도의 경우의 수가 존재하지만 실제로는 그것보다 경우가 적습니다. 데이터에 포함된 스트링은 얼마 없으니까요. )

S3 점을 받을 확률을 계산해 봅시다. 이전에 사용했던 T1, T2, T3, T4는 길이 7짜리 string이었다면, 여기에서는 왼쪽 오른쪽 끝을 제거한 길이 5짜리 스트링만 가지고 pre-calculation을 해도 됩니다. (이 쪽이 경우의 수가 더 적기 때문이지요.)

P3 = (1 - P4) - { P(T1에서 S3를 못 받을 확률) * P(T2에서 S3를 못 받을 확률) * P(T3에서 S3를 못 받을 확률) * P(T4에서 S3를 못 받을 확률) }

같은 방법으로 계산하면 P2는 아래와 같이 됩니다.

P2 = (1 - P3 - P4) - { P(T1에서 S2를 못 받을 확률) * P(T2에서 S2를 못 받을 확률) * P(T3에서 S2를 못 받을 확률) * P(T4에서 S2를 못 받을 확률) }

이렇게 P4, P3, P2를 구했으면 고정된 숫자일 때 *를 포함하는 기대값은 S4 * P4 + S3 * P3 + S2 * P2 가 됨을 알 수 있습니다.

ii) #가 고정된 숫자가 아닐 때

#는 4개의 스트링에 공통으로 사용됩니다. 따라서 #를 1~K의 숫자를 하나하나 대입해서 위에서 계산한 과정을 수행합니다. 그리고 가능한 기대값의 평균을 구해주면 됩니다.
코드 재사용을 하면 간단한 코드가 나오는데, 대회중에 작성한 코드라 복사-붙여넣기를 사용했네요 ㅠ.ㅠ;;