問題概要
文字列のスコアを, その連続である部分文字列のうち, すべての文字が同じであるものの個数とする.
今, ?と英小文字からなる文字列$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$に出来るかを確かめたいとき
- $c_i$が
?で代替可能 : 区間内の?と$c_i$の個数の和が$r - l$なら, ${p_i}^{(\mathrm{?の個数})}\ \ $の確率で全て$c_i$に出来る. - $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;
}
};