TopCoder SRM 607, Division 1, Level 1 : PalindromicSubstringsDiv1

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12964&rd=15840

問題概要

　英小文字及び '?' からなり、長さが 5,000 以下の文字列 S が与えられる。この文字列に含まれる全ての '?' をそれぞれ独立かつランダムに英小文字に置換したとき、回文となる部分文字列の数の期待値を求めよ。

解法

　文字列の長さを L と表記します。
　部分文字列の両端が決まっているとするとすると、等しくなるべき文字のペアが確定します。このペアの内いずれかが '?' のとき、そのペアが valid になる確率は 1 / 26 です。そうではない場合、二つの文字列が等しければ確率 1 で valid　になり、異なれば確率 0 で valid　になります。部分文字列中の全てのペアについて、valid になる確率を掛け合わせた値がその部分文字列が valid になる確率であると言えます。ただし、このままこれを計算すると全体で になって間に合わないので、一工夫する必要があります。
　ある文字列が回文であるとき、その両端（先頭文字及び末尾文字）を消去した文字列もまた回文となっています。逆に言えば、回文の先頭と末尾に同じ文字を付け足した文字列も回文となります。問題の方で考えると、ある部分文字列が回文である確率が p であり、その一つ外側にある文字のペアが valid になる確率が q であれば、部分文字列を両側に一文字ずつ伸ばして得られる文字列が回文となる確率は p * q です。得られる文字列は一つなので、期待値で言うと p * q 個の部分文字列が得られることになります。元の文字列の範囲内に収まる範囲でのこの値の総和が、回文でありかつそのときの初期状態を中心にもつ部分文字列の数の期待値です。初期状態の部分文字列の位置が異なれば背反な事象なので、初期位置を全て試して総和をとったものがそのまま全体の答えになります。この計算は なので Time Limit に間に合わせることができます。

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

class PalindromicSubstringsDiv1
{
public:
	string S;
	int L;

	double expectedPalindromes( vector <string> S1, vector <string> S2 )
	{
		{
			const string A = accumulate( ALL( S1 ), string() );
			const string B = accumulate( ALL( S2 ), string() );
			S = A + B;
			L = S.size();
		}

		double res = L;
		REP( i, 1, L - 1 )
		{
			res += solve( i - 1, i + 1 );
		}
		REP( i, 0, L - 1 )
		{
			res += solve( i, i + 1 );
		}
		return res;
	}

	double solve( int pos1, int pos2 )
	{
		double res = 0, p = 1;
		while ( 0 <= pos1 && pos2 < L )
		{
			const char c1 = S[ pos1 ], c2 = S[ pos2 ];

			if ( c1 == '?' || c2 == '?' )
			{
				p /= 26;
			}
			else if ( c1 != c2 )
			{
				p = 0;
			}

			res += p;

			pos1--;
			pos2++;
		}

		return res;
	}
}