SRM 324 Div1 Hard PalindromeEncoding

問題概要

0と1からなる文字列が与えられる。
この文字列に以下のような操作を繰り返し適用することができる。

文字列の長さが偶数の連続する部分文字列で、回文になっているものの、その右側を削除する。

このとき操作後に得られる文字列の長さの最小値を求めよ。

制約条件

文字列の長さ≦50

方針

なんとGreedyでいける。
文字列の先頭に同じ文字が連続していたらそれは取り除いても、最短文字列は変わらない。
（もし最適解が、取り除いた連続する文字を右側から取り除くのならば、対応する右側の部分で同じように先に取り除けばいいから）

すると文字列は
0101...011...もしくは1010...100...のような形になる。
ここで少し考えるとわかるが、2連続する文字以降の文字は全て消せる。

以後最初に2連続した文字以降を後半部分と呼ぶ。
後半部分は2連続する0をひとつの0,2連続する1をひとつの1に置き換えることをやれるだけやることで
1010...もしくは0101...の形になる。
後半部分にこの操作を施す。

前半部分が01...01だとして後半部分の最初の一文字が1なら、
011で11の部分が回文になっていて消せる。後半の最初の二文字が10なら、
010で0110の部分が回文になっていて消せる。

これは後半部分がなくなるまで繰り返し適用できる。

逆に連続するまでの010101の部分は偶数長の回文は含まれないので消せない。
よってこの部分が操作によってできる最短の文字列になる。

ソースコード

class PalindromeEncoding {
	public:
	int getLength(string s) 
	{
		while(s.size()>1&&s[0]==s[1])s=s.substr(1);
		for(int i=1;i<s.size();i++)if(s[i]==s[i-1]){
			s=s.substr(0,i);
			break;
		}
		return (int)s.size();
	}
};