Codeforces #258 Div2 D. Count Good Substrings

本番は長いコードを書いてしまったけど、実はあっさり解ける問題。
http://codeforces.com/contest/451/problem/D

問題

'a''b'で構成される文字列が与えられる。
この文字列の連続部分文字列のうち、同じ文字の連続を取り除き1文字だけ残す、という処理を行った後が回文になるものについて、連続部分文字列長が偶数のものと奇数のものの数を答えよ。

解法

本番は先に同じ文字の連続を取り除いてDPしたためえらく手間取ったが、その後Hack過程でもっと簡単な方法を知った。

連続部分文字列の最初と最後のものが等しければ、同じ文字の連続を取り除いたあとは回文になる。
よって「連続部分文字列の最初と最後のものが等しい」というものを奇数偶数別に数え上げるだけ。

dp[先頭の文字][先頭の文字の位置]で先頭の文字を4通りに分類しながらDPすればよい。

string S;
ll ret[2], dp[2][2];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>S;
	FOR(i,S.size()) {
		dp[S[i]-'a'][i%2]++;
		ret[0]+=dp[S[i]-'a'][(i%2)^1];
		ret[1]+=dp[S[i]-'a'][(i%2)];
	}
	_P("%lld %lld\n",ret[0],ret[1]);
}

まとめ

本番もっと簡単に考えればよかったな。