Codeforces #211 Div2. C. Fixing Typos

CF211はDiv2なので不参加。
正答者数が少ないEだけど、自力で解けたのでよかった。
http://codeforces.com/contest/363/problem/C

問題

文字列Sが与えられたとき、何文字か削って以下の条件を満たすようにしたい。

• 同じ文字は3文字以上続かない。
• 2種類の文字が2文字ずつ続かない。

削る文字数を最少にし、削った後の文字列の例を1つ答えよ。

解法

Greedyにできる。

まず、3文字以上連続のものを消す。
これはSを1文字ずつ見ていってS2に追加していき、S2の最後2文字と一致しない文字だけ追加していけばよい。

次に2文字の対を消す。
S2を1文字ずつ見ていってS3に追加していき、S3の最後3文字の後ろに1文字付け加えても2文字の対が生じない場合だけ付け加えていく。

S3が答え。

string S,S2,S3;
void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>S;
	FOR(i,S.size()) {
		if(i<2) S2+=S[i];
		else if(S[i]!=S2[S2.size()-1] || S[i]!=S2[S2.size()-2]) S2+=S[i];
	}
	FOR(i,S2.size()) {
		if(i<3) S3+=S2[i];
		else if(S2[i]!=S3[S3.size()-1] || S3[S3.size()-3]!=S3[S3.size()-2]) S3+=S2[i];
	}
	cout << S3 << endl;
}

まとめ

Div2とはいえCにしては簡単。