TopCoder SRM 650 Div2 Med: TaroFillingAStringDiv2

何度も見たことがあるような問題。

問題はこちら。

問題

AとBと?からなる文字列Sが与えられる。?はAかBに置き換えないといけない。文字列にはスコアが定義されており、S[i] == S[i + 1] となるiの個数がこの文字列のスコアとなる。文字列のスコアが最小になるように?を置き換えたときの、そのスコアを答えよ。

解法

すべてが?のときはAとBに交互に置き換えてやればスコアを0にできる。

それ以外のときは、まずスコアを0にできる区間を置き換えていく。たとえばA???Aという区間があるときABABAと置き換えてやればこの区間のスコアは0にできる。同一文字で奇数個の?をはさんでいる区間はスコア0になるように置き換えることができる。
それ以外の部分の?は左か右の文字と異なる文字で置き換えていけばいい。A???Bという区間があるとき、ABABBとAABABという置き換えが可能だがどちらも、スコアは同じである。よって置き換えはどちらでもよい。

最後に、上記の置き換えで出来上がった文字列のスコアを計算すればよい。

def getNumber(self, S):
    N = len(S)
    if "A" not in S and "B" not in S: return 0

    for i in xrange(N, 0, -2):
        S = S.replace("A" + "?" * i + "A", "A" + "".join("BA"[j % 2] for j in xrange(i)) + "A")
        S = S.replace("B" + "?" * i + "B", "B" + "".join("AB"[j % 2] for j in xrange(i)) + "B")
    for loop in xrange(50):
        S = S.replace("A?", "AB").replace("?A", "BA")
        S = S.replace("B?", "BA").replace("?B", "AB")
    ans = 0
    for i in xrange(1, N):
        if S[i - 1] == S[i]:
            ans += 1
    return ans

まとめ

本番だと変な詰まり方してしまいそう