kmjp's blog

競技プログラミング参加記です

Codeforces #295 Div1 A. DNA Alignment

CF#295は不参加。出てたらちょっと苦戦してABC完だったので、レートは増えたか微妙。
http://codeforces.com/contest/521/problem/A

問題

同じ長さNの文字列s,tに対し、h(s,t)とは同じ位置の文字が等しい数とする。
また、ρ(s,t)はs及びhをそれぞれ0~(N-1)文字回転させたs'、t'に対するh(s',t')の総和とする。

'ATCG'の4文字で構成されたN文字の文字列sが与えられる。
ρ(s,t)が最大となるN文字の文字tが何通りあるか答えよ。

解法

文字t[j]が最終的なρ(s,t)の値に影響するのは、各s[i]とt[j]の等しい数である。
当然、t[j]としてはもっともs中で登場頻度が高い文字にするのが良い。

そのため、この問題はs中における'ATCG'の頻度を数え、同着1位の文字がp個ある場合p^Nが解となる。

int L;
string S;
ll A[4];

ll mo=1000000007;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>L>>S;
	FOR(i,L) {
		A[0]+=S[i]=='A';
		A[1]+=S[i]=='T';
		A[2]+=S[i]=='G';
		A[3]+=S[i]=='C';
	}
	sort(A,A+4);
	x=1;
	if(A[3]==A[2]) x++;
	if(A[3]==A[1]) x++;
	if(A[3]==A[0]) x++;
	ll ret=1;
	FOR(i,L) ret=ret*x%mo;
	
	cout<<ret << endl;
}

まとめ

理解してしまえば実装は簡単。