kmjp's blog

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

CODE FESTIVAL 2018 Final : D - Three Letters

まだ全問解いてないけど。
https://beta.atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_d

問題

N個の文字列S[i]が与えられる。
各文字はアルファベット大文字・小文字のいずれかである。
3文字の文字列のうち、N個の部分文字列として登場回数が最多の物を求めよ。

同着が複数ある場合は、辞書順最小のものを求めよ。

解法

各文字に現れる、3文字の部分文字列を列挙しよう。
しかし愚直にO(|S|^3)かけて列挙すると間に合わない。
幸い、文字の種類がc=52通りしかないので、各位置に対し左右に各文字が登場するか数えていけばO(|S|*c^2)で処理できる。

全体ではO(sum(|S|)*c^2 + c^3)なので割と大きいが何とか間に合う。

int N;
string A[303030];
string M;

int L[90909][53];
int R[90909][53];
int ret[52][52][52];
int pat[52][52][52];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int ma=0;
	FOR(i,N) {
		cin>>A[i];
		FORR(c,A[i]) {
			if(c>='A' && c<='Z') c-='A';
			else c=c-'a'+26;
		}
		FOR(j,52) FOR(x,A[i].size()+2) L[x][j]=R[x][j]=0;
		FOR(j,A[i].size()) {
			FOR(x,52) L[j+1][x]=L[j][x];
			L[j+1][A[i][j]]++;
		}
		for(j=A[i].size()-1;j>=0;j--) {
			FOR(x,52) R[j+1][x]=R[j+2][x];
			R[j+1][A[i][j]]++;
			FOR(x,52) FOR(y,52) if(L[j][x]&&R[j+2][y]) {
				if(pat[x][A[i][j]][y]==0) {
					pat[x][A[i][j]][y]=1;
					ret[x][A[i][j]][y]++;
					ma=max(ma,ret[x][A[i][j]][y]);
				}
			}
		}
		FOR(j,A[i].size()) {
			FOR(x,52) FOR(y,52) if(L[j][x]&&R[j+2][y]) pat[x][A[i][j]][y]=0;
		}
	}
	FOR(i,26) M+=(char)('A'+i);
	FOR(i,26) M+=(char)('a'+i);
	
	FOR(i,52) FOR(j,52) FOR(x,52) if(ret[i][j][x]==ma) {
		cout<<M[i]<<M[j]<<M[x]<<endl;
		return;
	}
	
}

まとめ

もうちょい計算量落ちないかな。