kmjp's blog

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

Codeforces #616 Div1 B. Irreducible Anagrams

独自の定義を持ち出す問題文は理解に手間取る。
http://codeforces.com/contest/1290/problem/B

問題

文字列S,Tが単純化可能であるとは、S,Tをそれぞれ空でない2個以上の文字列S[i],T[i]に分割したとき、S[i]がT[i]のアナグラムであることをいう。
ここで文字列Sが与えられる。
以下のクエリに適宜答えよ。

  • Sの部分文字列がクエリとして指定される。この文字列に対し、単純化できないアナグラムが存在するか判定せよ。

解法

文字列が単純化できないアナグラムを持つのは、以下のいずれかの条件を満たす場合である。

  • 1文字である。
  • 先頭と末尾が異なる。末尾の文字と同じものをすべて先頭に集めた文字列は、単純化したアナグラムを持たない。
  • 文字が3種類以上ある。先頭でも末尾でもない2種類の文字を先頭と末尾に集めればよい。

そこで、部分文字列中の文字の登場回数を数えられれば上記を高速に判定できる。

int N;
string S;
int Q;
int C[202020][26];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	FOR(i,N) {
		FOR(j,26) C[i+1][j]=C[i][j];
		C[i+1][S[i]-'a']++;
	}
	
	
	cin>>Q;
	while(Q--) {
		int L,R;
		cin>>L>>R;
		L--;
		
		if(S[L]!=S[R-1] || R-L==1) {
			cout<<"Yes"<<endl;
			continue;
		}
		
		int num=0;
		FOR(i,26) if(C[R][i]-C[L][i]>0) num++;
		if(num>=3) {
			cout<<"Yes"<<endl;
		}
		else {
			cout<<"No"<<endl;
		}
		
	}
}

まとめ

本番Submitが怖いタイプの問題。