SRM654div1easy:SquareScores

SRM654に参加しました。結果はeasyをなんとか解いて(130ptぐらい)、チャレンジを1回成功させて自分にしてはそこそこ良い結果。

解法:1個連続になる個数の期待値、2個連続になる個数の期待値、...、n個連続になる個数の期待値を足した和が答え。それぞれの連続になる個数iについて、連続する区間[j-i+1,j]を考えて、そこに含まれる文字の種類を調べ、?のみの場合、?以外に2種類以上の文字が入っている場合、?以外に1種類の文字のみ入っている場合に場合分けして合計する。
以下ソースコード

class SquareScores {
public:
    double calcexpectation(vector <int> p, string s) {
        int m = p.size();
        vector<double> pp(m);
        for (int i = 0; i < m; i++) {
            pp[i] = (1. * p[i]) / 100;
        }
        int n = s.size();
        double ret = 1.*n;
        for (int i = 2; i <= n; i++) {
            int qcnt = 0;
            int cnt[26];
            for (int j = 0; j < 26; j++) cnt[j] = 0;
            for (int j = 0; j < n; j++) {
                if (s[j] != '?') cnt[s[j]-'a']++;
                else qcnt++;
                if (j >= i-1) {
                    int index = -1;
                    bool ng = false;
                    for (int k = 0; k < 26; k++) {
                        if (cnt[k] != 0) {
                            if (index == -1) index = k;
                            else {
                                ng = true;
                                break;
                            }
                        }
                    }
                    if (!ng) {
                        if (index == -1) {
                            for (int k = 0; k < m; k++) {
                                ret += pow(pp[k], qcnt);
                            }
                        } else {
                            ret += pow(pp[index], qcnt);
                        }
                    }
                    if (s[j-i+1] != '?') cnt[s[j-i+1]-'a']--;
                    else qcnt--;
                }
            }
        }
        return ret;
    }
};