TopCoder SRM 654 Div1 Easy: SquareScore

それなりに早く、一発で通せたのでうれしい

問題

N(≦ 1000)文字からなる文字列を当てられる。文字列は英小文字と"?"からなっている。各"?"はランダムにアルファベットに置き換えられるが、i番目のアルファベットに置き換えられる確率はP[i]である。含まれるアルファベットの種類が1種類だけの部分文字列の数をこの文字列のスコアとする。文字列のスコアの期待値を答えよ。
Div2Easyの発展問題。

解法

文字列のi番目から範囲を広げていき、含まれる文字が"?"と他1種類以下の場合、その部分文字列はスコアに加わる可能性があるので確率計算を行う。2種類以上のアルファベットが含まれる場合はスコアになりえないのでループを脱出する。
部分文字列がすべて"?"からなる場合は、すべての"?"が任意のアルファベットに置き換えられる確率でスコアに加えられる。
アルファベットが含まれる場合は、すべての"?"がそのアルファベットに置き換えられる確率でスコアに加えられる。
確率の計算を毎回しているとTLE不可避なので、はじめに"?"の個数に応じた確率表を作っておく。

O(N²)。pythonだと計算時間がかなりきついが何とか通った。

alpha = "abcdefghijklmnopqrstuvwxyz"

def calcexpectation(self, p, s):
    n = len(s)
    m = len(p)
    prob = [[1.0] * m for j in xrange(n + 1)]
    for i in xrange(1, n + 1):
        for j in xrange(m):
            prob[i][j] = prob[i - 1][j] * (p[j] / 100.0)
    ans = 0
    for i in xrange(n):
        q = 0
        c = ""
        for j in xrange(i + 1, n + 1):
            if s[j - 1] == "?": q += 1
            else:
                if c == "": c = s[j - 1]
                elif c != s[j - 1]: break
            if c == "":
                for k in xrange(m):
                    ans += prob[q][k]
            else:
                ans += prob[q][alpha.index(c)]
    return ans