WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM607 Div1 Easy "PalindromicSubstringsDiv1"

問題

TopCoder Statistics - Problem Statement

マルコは回文となっている文字列がとても好きであり、特に回文となる部分文字列がたくさん含まれているものが好きである。例えば、彼は"aaa"という文字列がとても好きである。なぜならそれは、"a"という回文が3つ、"aa"という回文が2つ、"aaa"という回文が1つの、6つの回文となる部分文字列が含まれているからだ。

マルコは、小文字のアルファベットと'?'で構成されたSという文字列について考えている。String[] S1, S2が与えられるので、まず下記のようにしてSを得てほしい。

  • S1の全ての文字列を順番に結合してAという文字列を得る。
  • S2の全ての文字列を順番に結合してBという文字列を得る。
  • 最後にAとBを結合してSを得る

マルコが全てのSの中の'?'を、ランダムにアルファベットの小文字に置き換えた。回文となっている部分文字列の個数の期待値を返せ。

制約

1 <= Sの文字列長 <= 2500


考えたこと

Div2の簡単版の拡張ver。

Sのs番目からt番目の部分文字列S[s, t]を考える。

まず、1つ内側のS[s+1, t-1]の部分文字列が回文にならなければ、S[s, t]は回文にできない。それから、S[s]とS[t]が同じ文字でないと、S[s, t]は回文にできない。

よって、S[s, t]の部分文字列が回文となる期待値は、1つ内側の部分文字列S[s+1, t-1]が回文となる期待値と、文字S[s]とS[t]が同じとなる期待値をかけたものとなる。

例えば、sとtが下記だったとして、

abc??a?
 |  |  
 s  t

1つ内側はpとqになる。

abc??a?
  ||  
  pq

S[p, q]が回文となる確率は'?'が'c'にならなくてはならないので、1/26である。また、sとtが同じ文字になる確率は、これまた1/26である。よって、S[s, t]が回文となる確率は(1 / 26) * (1 / 26)で、1 / 26^2 となる。

さらに、S[s, t]の外側のS[a, b]は、

 abc??a?
 |    |  
 a    b

S[a] == S[b]なので、1 / 26^2 となる。


こうやって全ての部分文字列を試し、総和を求めればよい。

ソースコード

class PalindromicSubstringsDiv1 {

    public:

    double expectedPalindromes(vector <string> S1, vector <string> S2) {
        string S = "";
        for (int i = 0; i < S1.size(); i++){
            S += S1[i];
        }
        for (int i = 0; i < S2.size(); i++){
            S += S2[i];
        }

        int N = S.size();
        const double b = 1.0 / 26.0;
        double res = 0.0;
        for (int i = 0; i < N; i++){
            // 奇数
            double p = 1.0;
            for (int s = i; s >= 0; s--){
                int t = i + i - s;
                if (N <= t) break;
                // 1文字なら絶対回文
                if (s == t){
                    res += p;
                }
                // ? があれば1 / 26
                else if(S[s] == '?' || S[t] == '?'){
                    p *= b;
                    res += p;
                }
                // 文字が同じなら回文
                else if (S[s] == S[t]){
                    res += p;
                }
                // 違う文字ならこれより外側は絶対に回文を作れない
                else{
                    break;
                }
            }
            // 偶数
            p = 1.0;
            for (int s = i; s >= 0; s--){
                int t = i + i - s + 1;
                if (N <= t) break;
                if (S[s] == '?' || S[t] == '?'){
                    p *= b;
                    res += p;
                }else if (S[s] == S[t]){
                    res += p;
                }else{
                    break;
                }
            }
        }
        
        return res;
    }
};