CODE FESTIVAL 2018 Final D - Three Letters(500)

D - Three Letters

概要

英小文字・英大文字からなる文字列AiがN個与えられる。英小文字・英大文字からなる3文字の文字列の中で、N個の文字列のうち最も多くの文字列の部分列（連続でなくてよい）になっているものを答えよ。なお答えが複数ある場合は、辞書順で最も前のものを出力する。

制約

1 ≦ N ≦ 30000
Σ |Ai| ≦ 90000

方針

全ての3文字の文字列について、N個の文字列中いくつの文字列の部分列になっているかを調べたいが、これを愚直に行うとO*1

両端の2文字はあらかじめ含まれている文字種を調べておく

両端の2文字は文字種全てを探索し(52^2)、その中であらかじめ調べた文字種と合致するものをカウントする。ただし、3文字部分列は同じAiで1度だけカウントされるようにする

計算量は両端の2文字の文字種調べにO(|Ai|)、真ん中の文字の探索⇒両端の2文字の文字種全探索O(|Ai| * 52^2)でボトルネックはO(|Ai| * 52^2)である。90000 * 52^2 ≒ 2.4 * 10^8　であるため、何とか間に合う。

なお、両端の2文字の文字種調べは、先に右側の文字として調べた後、真ん中の文字の探索中に動的に左側・右側の文字種を増減させると上記の計算量を達成できる。

感想

下記ブログを参考にしました。
tutuz.hateblo.jp

解答

Submission #7187676 - CODE FESTIVAL 2018 Final (Parallel)

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int c2i(char c){
	if(c >= 'a') return c - 'a' + 26;
	return c - 'A';
}
 
char i2c(int i){
	if(i >= 26) return 'a' + i - 26;
	return 'A' + i;
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N;
	cin >> N;
 
	string A[N];
	rep(i, N) cin >> A[i];
 
	int ma = 0;
	int cnt[52][52][52];
	memset(cnt, 0, 52 * 52 * 52 * sizeof(int));
 
	for(int i = 0; i < N; i++){
		string s = A[i];
		int m = s.size();
 
		vector<int> L(52, 0), R(52, 0);
		bool used[52][52][52];
		memset(used, false, 52 * 52 * 52 * sizeof(bool));
 
		for(int j = 1; j < m; j++){
			char c = s[j];
			// cout << c2i(c) << " ";
			R[c2i(c)]++;
		}
		// cout << endl;
 
		for(int j = 1; j < m-1; j++){
			int md = c2i(s[j]);
			L[c2i(s[j-1])]++;
			R[c2i(s[j])]--;
			rep(l, 52) rep(r, 52){
				if(L[l] >= 1 && R[r] >= 1 && !used[l][md][r]){
					// cout << l << "," << md << "," << r << endl;
					used[l][md][r] = true;
					cnt[l][md][r]++;
					ma = max(ma, cnt[l][md][r]);
				}
			}
		}
	}
 
	// rep(i, 52) rep(j, 52) rep(k, 52){
	// 	if(cnt[i][j][k] > 0){
	// 		cout << i2c(i) << i2c(j) << i2c(k) << endl;
	// 	}
	// }
	//
	// cout << "the answer is ";
 
	rep(i, 52) rep(j, 52) rep(k, 52){
		if(cnt[i][j][k] == ma){
			cout << i2c(i) << i2c(j) << i2c(k) << endl;
			return 0;
		}
	}
}

*1:52^3) * N)で間に合わない。(52^3 >10^5)

方針を変えて、Aiから生成されうる3文字の部分列をすべて列挙し、最も多いものを求めることを考える。これも愚直に行うとO(|Ai|^3)かかるので間に合わない。
計算量を削減するため、Aiについての部分文字列を列挙するときに次のような考え方を用いる。

• 真ん中の文字は探索する(O(|Ai|