Algoogle

Algorithm for Programming Contest

SRM 607 Div1

Category: TopCoder Tag: dp

Easy


PalindromicSubstringsDiv1

回文は真ん中からよむといいらしい.
dp[l][r] := l から r までのsubstringが回文である確率.
S[l] == S[r] ならdp[l+1][r-1]の確率で回文
どっちかだけ’?’なら dp[l+1][r-1] / 26 の確率で回文
どっちも’?’なら dp[l+1][r-1] * 26 / 26^2の確率で回文
それ以外では回文にならない
あとはそれぞれのsubstringが回文になる期待値を足し合わせればいい

コード


(607div1easy.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class PalindromicSubstringsDiv1 {
public:
    double expectedPalindromes( vector <string> S1, vector <string> S2 ) {
        string S ="";
        rep(i,S1.size()) S += S1[i];
        rep(i,S2.size()) S += S2[i];
        double dp[5010][5010] = {};
        int n = S.size();
        for(int i = 0; i < n; i++)
            dp[i][i] = dp[i+1][i] = 1.0;
        double ans = n;
        for(int w = 2; w <= n; w++)
            for(int l = 0; l + w <= n; l++){
                int r = l + w - 1;
                if(S[l] != '?' && S[l] == S[r])
                    dp[l][r] = dp[l+1][r-1];
                else if(S[l] == '?' || S[r] == '?')
                    dp[l][r] = dp[l+1][r-1] / 26;
                ans += dp[l][r];
            }
        return ans;
    }
};

Comments