Google Code Jam 2018 Round1C : A Whole New Word

くだらないミスも多かったけど、何とかRound1は突破できた。
https://codejam.withgoogle.com/2018/challenges/0000000000007765/dashboard

問題

L文字の文字列N個が与えられる。
L文字の文字列のうち、i文字目はN個のいずれかに一致しつつ、かつ全体としてはN個のどれとも一致しない文字列が構築できるか。

解法

Nがあまり大きくないので、各位置に来うる文字から生成できる文字列を全列挙してもよい。

以下の解法では、先頭から文字を１文字ずつ決めている。
その際、N個中prefixが一致するものが少ないものを選ぶようにした。

int N,L;
string S[2020];
set<string> SS;
set<char> C[2020];
map<string,int> pref[11];

string ret;

void dfs(int cur,string s) {
	if(cur==L) {
		if(SS.count(s)==0) ret=s;
		return;
	}
	int mi=101010;
	char be='0';
	FORR(c,C[cur]) {
		if(pref[cur+1][s+c]<mi) {
			mi=pref[cur+1][s+c];
			be=c;
		}
	}
	s+=be;
	dfs(cur+1,s);
}

void solve(int TC) {
	int i,j,k,l,r,x,y; string s;
	cin>>N>>L;
	SS.clear();
	FOR(i,L) C[i].clear();
	FOR(i,L+1) pref[i].clear();
	
	ret="";
	FOR(i,N) {
		cin>>S[i];
		SS.insert(S[i]);
		FOR(j,L) {
			C[j].insert(S[i][j]);
			pref[j+1][S[i].substr(0,j+1)]++;
		}
	}
	
	dfs(0,"");
	
	if(ret.empty()) _P("Case #%d: -\n",TC);
	else _P("Case #%d: %s\n",TC,ret.c_str());
	
}

まとめ

GCJのUIが使いにくい…。