kojingharangの日記

SRM 607 Div1 250 PalindromicSubstringsDiv1

23:28 |

• '?' か a-z を含む文字列 S がある。'?' をランダムに a-z のどれかに置換したとき、回文になってる部分文字列の個数の期待値を求めよ。
• 1≦|S|≦5000

• 15分くらい何の方針も立たず
• 部分文字列ごとに独立に期待値(そうなる確率 * 1個)を求めて足せば良いと気づく
• (部分問題とか状態、パラメータの依存関係を的確に明らかにしてくのがこういうののコツらしい)
• すると, ある部分文字列に対して O(N) で期待値が分かる
• 両端から見ていってどっちかが ? なら 1/26, そうでなくて同じ文字なら 1, 異なる文字なら 0 を掛けてく
• 部分文字列は N(N+1)/2 個なので O(N^3) (実際はもっと小さいんだっけ)
• 5000^3 はあれなので O(N^2) に落としたい
• S[s,e]が回文であるとは S[s]=S[e] かつ S[s+1, e-1] が回文みたいにして O(N^2) 化
• デバッグに時間がかかる (;_;)

• accepted

double dp[5010][5010]; // dp[a][b] ... s[a, b]が回文になる確率
class PalindromicSubstringsDiv1 {
	public:
	double expectedPalindromes(vector <string> S1, vector <string> S2) {
		CLEAR(dp, 0);
		string s = accumulate(ALL(S1), string(""))+accumulate(ALL(S2), string(""));
		int N=s.size();
		double ans=0;
		RANGE(L, 1, N+1) REP(i, N-L+1) {
			char a=s[i], b=s[i+L-1];
			double lans=1.0/26;
			if(L==1) lans=1.0;
			else {
				if(a!='?' && b!='?' && a==b) lans = 1.0;
				if(a!='?' && b!='?' && a!=b) lans = 0.0;
			}
			double inner = L<=2 ? 1.0 : dp[i+1][i+L-1-1];
			dp[i][i+L-1] = lans * inner;
			ans += dp[i][i+L-1];
		}
		return ans;
	}
};

ツイートする