SRM654 div1 easy SquareScores
考えたこと
- 部分文字列[l,r]が同じ文字になる確率を考える
- ?がなくて全部同じ文字→1
- 違う文字が混ざっている→0
- ?がm個で他が全部同じ文字c→(cの確率)^m
- 全部?でm個→sum(p[i]^m)
- よくよく考えると各部分文字列について独立っぽい
- 全ての部分文字列について確率を求めて足せばよい
- O(|S|^3)で求められる
考察はすぐだったけど凡ミスで実装に時間をかけて反省
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typedef vector<VL> VVL; typedef pair<int, int> PII; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define IN(a, b, x) (a<=x&&x<b) #define MP make_pair #define PB push_back const int INF = (1LL<<30); const ll LLINF = (1LL<<60); const double PI = 3.14159265359; const double EPS = 1e-12; const int MOD = 1000000007; //#define int ll template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; class SquareScores { public: double calcexpectation(vector <int> p, string s) { int n = s.size(); int sz = p.size(); REP(i, 26 - sz) p.PB(0); double ret = 0; REP(l, n) FOR(r, l, n) { if(l == r) {ret++; continue;} char c = '?'; int cnt = 0; bool flag = true; FOR(i, l, r+1) { if(s[i] != '?') { if(c == '?') {c = s[i];} else if(c == s[i]) {c = s[i];} else {flag = false; break;} } else { cnt++; } } if(flag) { if(cnt == 0) ret++; else if(cnt == r-l+1) { REP(j, 26) { ret += pow(p[j]/100.0, cnt); } } else { ret += pow(p[c-'a']/100.0, cnt); } } } return ret; } };