SRM607

開始に遅れてなければミドルもとけたはず。悔しい。

250

長さ最大5000の文字列の回文である部分列の個数の期待値を求める問題。 文字列の中に？があってそれは確率1/26ずつで各文字になる。

詰まった点

家に帰るのが遅かった。 入力がみじん切りにされているのに意味があると思ってしまった。(入力の長さ限界の問題なのかな) コピペをするときに変更箇所が2か所あることに気付かなかった。 Visual StudioのCコンパイラがフリーズした。 1/26と書いたら、0になってしまうことを忘れていた。 以上、反省。

//250.cpp

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#define LOG(x,a,b) 
using namespace std;
class PalindromicSubstringsDiv1{
public:
      double expectedPalindromes(vector <string> S1, vector <string> S2){
            string S;
            for(string s1:S1)
                  S+=s1;
            for(string s2:S2)
                  S+=s2;
            int n=S.size();
            double e=0;
            for(int i=0;i<=n-1;i++){
                  double crep=1;
                  e+=crep;
                  LOG(crep,i,i)
                  for(int j=1;j<=min(i,n-1-i);j++){
                        if(S[i-j]=='?'||
                           S[i+j]=='?')crep*=1/26.0;
                        else if(S[i-j]==S[i+j]);
                        else crep=0;
                        e+=crep;
                        LOG(crep,i-j,i+j)
                        if(crep==0)break;
                  }
            }
            for(int i=0;i<=n-2;i++){
                  double crep=1;
                  for(int j=0;j<=min(i,n-2-i);j++){
                        if(S[i-j]=='?'||
                           S[i+j+1]=='?')crep*=1/26.0;
                        else if(S[i-j]==S[i+j+1]);
                        else crep=0;
                        e+=crep;
                        LOG(crep,i-j,i+j+1)
                        if(crep==0)break;
                  }
            }
            return e;
      }
};