TopCoder SRM 650 Div1 Easy TaroFillingAStringDiv1、Div2 Medium TaroFillingAStringDiv2

SRM650は不参加。
でもMediumの正答者が少なかったので、出てたらEasy早解きだけでちょっとレート上がりそう。
http://community.topcoder.com/stat?c=problem_statement&pm=13669
http://community.topcoder.com/stat?c=problem_statement&pm=13668

問題

N文字の文字列Sを考える。各文字は'A'か'B'の何れかである。
N文字中一部の位置については、'A'か'B'かが判明している。

文字列の汚さとは、文字列中で同じ文字が２連続している数の事を示す。
未定の場所に'A'か'B'を適切に入れることで汚さを最小化したい。

Div2 Medium : 汚さの最小値を答えよ。
Div1 Easy : 汚さが最小値である文字列は何通りあるか。

解法

汚さが生じるのは以下のケースである。
S[i]とS[j]が決まっており、S[(i+1)..(j-1)]が未定とする。

• j-iが偶数でS[i]!=S[j]の場合
• j-iが奇数でS[i]==S[j]の場合

上記の場合、S[i..j]はどうやっても１か所同じ文字が連続する箇所が生じる。
そのためDiv2 Mediumはその数をカウントすればよい。
Div1 Easyでは、同じ文字が連続する箇所は(j-i)箇所のどこかで連続が生じるので、それを掛け合わせればよい。

class TaroFillingAStringDiv2 {
	public:
	int getNumber(string S) {
		int L=S.size(),i,x,y,t=0;
		pair<int,char> P[55];
		
		FOR(i,L) if(S[i]!='?') P[t++] = make_pair(i,S[i]);
		sort(P,P+t);
		
		int ret=0;
		FOR(i,t-1) {
			int dif=P[i+1].first-P[i].first;
			if(dif%2==abs(P[i+1].second-P[i].second)) continue;
			ret++;
		}
		return ret;
	}
}

ll mo=1000000007;
class TaroFillingAStringDiv1 {
	public:
	
	int getNumber(int N, vector <int> position, string value) {
		int L=position.size(),i,x,y;
		pair<int,char> P[55];
		FOR(i,L) P[i]=make_pair(position[i]-1,value[i]);
		sort(P,P+L);
		
		ll ret=1;
		FOR(i,L-1) {
			int dif=P[i+1].first-P[i].first;
			if(dif%2==abs(P[i+1].second-P[i].second)) continue;
			if(dif==0) continue;
			ret = ret * dif % mo;
		}
		return ret;
	}
}

まとめ

割とすんなり。
このSRM出ておけばよかったな…。