Google Code Jam 2022 Round 3 : C. Mascot Maze

本番に解けてよかった。
https://codingcompetitions.withgoogle.com/codejam/round/00000000008779b4/0000000000b44a4f

問題

N頂点のグラフが与えられる。
各点からは、2つの異なる頂点に有向辺が伸びている。
各頂点に13種類の文字の1つを割り当てることを考える。

辺に沿って連続で3つの頂点をたどるとき、その3頂点で文字が重複しないようにしたい。
そのような割り当ては可能か、可能なら1例を示せ。

解法

まず長さ2の閉路がある場合は、自明に割り当て不可。
そうでない場合を考える。
13に着目してみよう。
平均的には、連続した3頂点を選ぶとき、各頂点と一緒に選ばれる可能性のある頂点は、

• 2つの子頂点
• 4つの孫頂点
• 2つの親頂点
• 4つの親の親頂点

であり、自身を合わせると13頂点ある。

一緒に選べる可能性がある頂点が自身含めて13頂点以下ならば、自分以外の頂点に割り当てられた文字が何であれ、自身の文字は残った文字を割り当てられるので、他頂点より後に決めることができる。
よって、「他頂点より後に決めることができる」頂点をどん欲に取り除いていくと、最終的に全頂点を取り除くことができる。
逆に、逆順に頂点に文字を割り当てて行けば、常に文字を割り当てる際は「一緒に選べる可能性がある文字確定済みの頂点は自身を含め13個以下」なので、何か知らの文字を割り当てることができる。

int N;
int L[101010];
int R[101010];
vector<int> in[101010];
string S="ACDEHIJKMORST";
int C[101010];
int cost[101010];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) {
		in[i].clear();
		C[i]=-1;
		cost[i]=0;
	}
	FOR(i,N) {
		cin>>L[i];
		L[i]--;
		in[L[i]].push_back(i);
	}
	FOR(i,N) {
		cin>>R[i];
		R[i]--;
		in[R[i]].push_back(i);
	}
	
	FOR(i,N) {
		if(L[L[i]]==i) break;
		if(L[R[i]]==i) break;
		if(R[L[i]]==i) break;
		if(R[R[i]]==i) break;
	}
	
	if(i<N) {
		cout<<"Case #"<<_loop<<": IMPOSSIBLE"<<endl;
		return;
	}
	
	FOR(i,N) {
		cost[i]+=6;
		cost[L[i]]++;
		cost[R[i]]++;
		cost[L[L[i]]]++;
		cost[L[R[i]]]++;
		cost[R[L[i]]]++;
		cost[R[R[i]]]++;
	}
	queue<int> Q;
	vector<int> V;
	FOR(i,N) if(cost[i]<=12) {
		C[i]=-2;
		Q.push(i);
	}
	while(Q.size()) {
		int cur=Q.front();
		Q.pop();
		V.push_back(cur);
		vector<int> cand;
		cand.push_back(L[cur]);
		cand.push_back(R[cur]);
		cand.push_back(L[L[cur]]);
		cand.push_back(L[R[cur]]);
		cand.push_back(R[L[cur]]);
		cand.push_back(R[R[cur]]);
		FORR(e,in[cur]) {
			cand.push_back(e);
			FORR(e2,in[e]) cand.push_back(e2);
		}
		FORR(c,cand) {
			cost[c]--;
			if(C[c]==-1&&cost[c]<=12) {
				C[c]=-2;
				Q.push(c);
			}
		}
	}
	reverse(ALL(V));
	FORR(cur,V) {
		int mask=(1<<13)-1;
		vector<int> cand;
		cand.push_back(L[cur]);
		cand.push_back(R[cur]);
		cand.push_back(L[L[cur]]);
		cand.push_back(L[R[cur]]);
		cand.push_back(R[L[cur]]);
		cand.push_back(R[R[cur]]);
		FORR(e,in[cur]) {
			cand.push_back(e);
			FORR(e2,in[e]) cand.push_back(e2);
		}
		FORR(c,cand) {
			if(C[c]>=0 && (mask&(1<<C[c]))) mask^=1<<(C[c]);
		}
		FOR(i,13) if(mask&(1<<i)) C[cur]=i;
	}
	
	
	cout<<"Case #"<<_loop<<": ";
	FOR(i,N) {
		assert(C[i]!=C[L[i]]);
		assert(C[i]!=C[R[i]]);
		assert(C[i]!=C[L[L[i]]]);
		assert(C[i]!=C[L[R[i]]]);
		assert(C[i]!=C[R[L[i]]]);
		assert(C[i]!=C[R[R[i]]]);
		cout<<S[C[i]];
	}
	cout<<endl;
}

まとめ

これは思いつけて良かったね。
B,Cはある意味Round2より素直だったかも。