Google Code Jam 2022 Round 1C : A. Letter Blocks

前2ラウンドに比べて難しくない？
https://codingcompetitions.withgoogle.com/codejam/round/0000000000877b42/0000000000afe6a1

問題

N個の文字列が与えられる。
これらを任意の順で並べて連結した文字列を作りたい。
その際、同種の文字列はすべて連続していなければならない。

可能ならば一例を示せ。

解法

各文字列、先頭と末尾の文字を考える。
文字列Sの末尾と、文字列Tの先頭が同じなら、S→Tの順で連続するようにしよう。
ただし、先頭も末尾もSの末尾と同じ文字列Uがあるなら、それらはSとTの間に挟むようにする。
それ以外の関係にある文字列同士の順は問わない。

このように先頭と末尾のみ考慮して文字列を並べて行き、最後に同種の文字が連続しているか確認しよう。
以下のコードでは無駄にオイラーパスのライブラリを使ったが、必要なさそうだった。

int N;
string S[101];

template<int MV> class DirectedEulerPath {
public:
	int NV;
	vector<int> path;
	vector<vector<int>> paths;
	vector<int> E[MV];
	vector<int> deg;
	void add_path(int x,int y) { E[x].push_back(y);}
	
	void init(int NV){
		this->NV=NV;
		for(int i=0;i<NV;i++) E[i].clear();
		path.clear();
	}
	void dfs(int cur) {
		while(E[cur].size()) {
			int e=E[cur].back();
			deg[cur]--;
			deg[e]++;
			E[cur].pop_back();
			dfs(e);
		}
		path.push_back(cur);
	}
	
	bool GetPath() {
		assert(NV);
		int te=0,i,j;
		deg.resize(NV);
		FOR(i,NV) {
			te += E[i].size();
			deg[i]+=E[i].size();
			FORR(e,E[i]) deg[e]--;
		}
		paths.clear();
		FOR(j,NV) {
			FOR(i,NV) {
				if(deg[i]==1) {
					path.clear();
					dfs(i);
					paths.push_back(path);
				}
			}
		}
		FOR(i,NV) if(deg[i]==0) {
			path.clear();
			dfs(i);
			paths.push_back(path);
		}
		
		FOR(i,NV) if(E[i].size()) return 0;
		return 1;
	}
};

void solve(int _loop) {
	int f,i,j,k,l,x,y;

	DirectedEulerPath<26> dep;
	vector<int> C[26][26];
	dep.init(26);
	cin>>N;
	FOR(i,N) {
		cin>>S[i];
		dep.add_path(S[i][0]-'A',S[i].back()-'A');
		C[S[i][0]-'A'][S[i].back()-'A'].push_back(i);
	}
	
	FOR(i,26) {
		int num=0;
		FOR(x,26) if(i!=x) num+=C[i][x].size();
		if(num>1) break;
		num=0;
		FOR(x,26) if(i!=x) num+=C[x][i].size();
		if(num>1) break;
	}
	
	
	if(i!=26||dep.GetPath()==0) {
		cout<<"Case #"<<_loop<<": IMPOSSIBLE"<<endl;
		return;
	}
	string T;
	FORR(path,dep.paths) {
		reverse(ALL(path));
		FOR(x,path.size()-1) {
			y=C[path[x]][path[x+1]].back();
			C[path[x]][path[x+1]].pop_back();
			T+=S[y];
		}
	}
	int mask=0,pre=-1;
	FORR(c,T) {
		if(c==pre) continue;
		if(mask&(1<<(c-'A'))) {
			mask=-1;
			break;
		}
		mask |= (1<<(c-'A'));
		pre=c;
	}
	if(mask!=-1) {
		cout<<"Case #"<<_loop<<": "<<T<<endl;
		return;
	}
	
	
	cout<<"Case #"<<_loop<<": IMPOSSIBLE"<<endl;
}

まとめ

1Aも1Bも1問目はだいぶ簡単だったのに…。