問題概要

文字列のスコアを, その連続である部分文字列のうち, すべての文字が同じであるものの個数とする.

今, ?と英小文字からなる文字列$s$が与えられる. $s$の各?を$\displaystyle\frac{p[i]}{100}$の確率で$i+1$番目のアルファベットにするとき, 文字列$s$のスコアの期待値を求めなさい.

制約

  • $1 \leq |s| \leq 1000$
  • $s$は?と英小文字からなる
  • $1 \leq |p| \leq 26$
  • $0 \leq p_i \leq 100$
  • $p$の要素の総和は$100$

考察

$|s|$の制約が小さいので, 全ての部分文字列の全探索が出来る.

$s$の部分文字列を全て$c_i(a, b, \ldots, z)$にする期待値を求めて, それらの総和を取れば答え.

実装

累積和を使って, 任意区間における特定の文字の個数を$O(1)$で取れるように前処理する.

$[l, r)$を全て$c_i$に出来るかを確かめたいとき

  1. $c_i$が?で代替可能 : 区間内の?と$c_i$の個数の和が$r - l$なら, ${p_i}^{(\mathrm{?の個数})}\ \ $の確率で全て$c_i$に出来る.
  2. $c_i$が?で代替不可能 : 区間内がもともと全て$c_i$である必要がある.

提出コード(C++🔆)

struct SquareScores {
    vector<int> p;
    string s;
    int acc[27][1010];
    double calcexpectation(vector<int> _p, string _s) {
        p = _p, s = _s;
        int P = p.size(), N = s.size();
        // 累積和で任意区間の中にある特定の文字の個数を取れるように
        REP(i, 27) acc[i][0] = 0;
        REP(i, N) acc[0][i + 1] = acc[0][i] + (s[i] == '?');
        REP(i, 26) REP(j, N) acc[i + 1][j + 1] = acc[i + 1][j] + (s[j] == 'a' + i);
        double res = 0.0;
        REP(l, N) REP(r, N + 1) {
            if (l >= r) continue;
            int mighty = acc[0][r] - acc[0][l];
            REP(i, 26) {
                // [l, r)の全てが, 'a'+iになる確率
                int moji = acc[i + 1][r] - acc[i + 1][l];
                // '?'で代用できない文字は, '?'がある時点でむり
                if (P <= i and mighty != 0) continue;
                if (moji + mighty != r - l) continue;
                res += pow(double(p[i]) / 100, mighty);
            }
        }
        return res;
    }
};