Google Code Jam 2019 Round 1A : C. Alien Rhyme

今回で一番オーソドックスな問題。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000051635/0000000000104e05

問題

N個の文字列S[i]が与えられる。
N個のうち任意の個数を取り除いたうえで、各文字列に対しSuffixを1つ定めよう。
残された文字列をSuffixが同じものがちょうど2つずつあるようにしたい。

最適にSuffixを定め、かつ文字列を取り除く場合、最大何個の文字列を残せるか。

解法

仮にx文字のsuffixを等しくできる文字列のペアがある場合、(x-1)文字のsuffixも等しい。
よって、逆に長い共通suffixを持つペアがあればそこから貪欲にペアを組んでしまおう。
同じsuffixのペアが2つできそうな場合は、2つめはあきらめ、1つ短いsuffixが空いていればそこで組ませるものとする。

共通suffix長の算出は、Trieを用いればO(sum(S))でできるが、N,|S|が小さいのでO(N^2)回文字列長を比較して(N*sum(S))かかっても間に合う。

int N;
string W[1010];

int valid[1010];
int num[1010][1010];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) {
		cin>>W[i];
		reverse(ALL(W[i]));
	}
	ZERO(num);
	FOR(y,N) FOR(x,y) {
		while(num[x][y]<W[x].size()&&num[x][y]<W[y].size()&&W[x][num[x][y]]==W[y][num[x][y]]) num[x][y]++;
	}
	ZERO(valid);
	int ret=0;
	for(i=50;i>=1;i--) {
		set<string> SS;
		FOR(y,N) if(valid[y]==0) FOR(x,y) if(valid[x]==0 && num[x][y]>=i) {
			string S=W[x].substr(0,i);
			if(SS.count(S)==0) {
				SS.insert(S);
				ret+=2;
				valid[x]=valid[y]=1;
			}
		}
	}
	
	
	_P("Case #%d: %d\n",_loop,ret);
}

まとめ

本番Trieが思い浮かんでなかったので、|S|やNがもう少し大きいと危なかったかも。