Rockethon 2014 : A. Genetic Engineering、B. Word Folding

さすがにA,Bは簡単。
http://codeforces.com/contest/391/problem/A
http://codeforces.com/contest/391/problem/B

A. Genetic Engineering

文字列が与えられるので、同じ文字が並ぶ部分文字列ごとに分解した場合、偶数長となる数を答えよ。
同じ文字が連続する数を数えていくだけ。

void solve() {
	int f,i,j,k,l,x,y;
	string S;
	
	y=0;
	x=1;
	cin>>S;
	FOR(i,S.size()-1) {
		if(S[i+1]==S[i]) {
			x++;
		}
		else {
			if(x%2==0) y++;
			x=1;
		}
	}
	if(x%2==0) y++;
	_P("%d\n",y);
	
}

B. Word Folding

文字列が与えられるので、特定の条件に基づき文字列を配置していく。
最大で縦方向に何個同じ文字が並べられるか。

各文字についてDPしていく。
ある文字の上に同じ文字を重ねるには、元の文字同士の距離が奇数でなければならない。
よって、各文字において状態を位置の偶奇で管理し、DPして同じ文字を積み重ねられる数を最大化していけばよい。

void solve() {
	int f,i,j,k,l,x,y;
	
	string S;
	cin>>S;
	
	int ma=0;
	FOR(i,26) {
		int dp[2]={0,0};
		
		FOR(x,S.size()) if(S[x]=='A'+i) dp[x%2] = max(dp[x%2], 1+dp[(x%2)^1]);
		ma=max(ma,dp[0]);
		ma=max(ma,dp[1]);
	}
	
	_P("%d\n",ma);
}

まとめ

Bは解答はシンプルだけど、問題設定が面白いな。