yukicoder : No.1401 全自動マクロの作り方

これ本番に自信をもってACできる気がしないな。
https://yukicoder.me/problems/no/1401

問題

N個の整数列Sが与えられる。
以下の条件を満たすAが作れるか。

Aを何度か繰り返した数列A'を考える。

各数列Sに対し、変数iを考える。初期値でi=0である。
A'の各要素vに対し、S[i%|S|]=vならiをインクリメントする。
A'の全要素を処理したとき、i%|S|=0である。

解法

各Sについて、Sの末尾(の値に対応する頂点)から先頭要素(の値に対応する頂点)に対する有向辺を張るグラフを考える。

このグラフが閉路なら、条件を満たすAは存在しない。
どこかの数列でi=0を達成しようとしたとき、他の数列でi=1になってしまうためである。
そうでない場合、このグラフはDAGを成すので、Aをトポロジカルソート順にしたものを取ればよい。

int N;
vector<int> S[2020];

vector<int> E[2020];
int in[2020];
set<int> is;
vector<int> R;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		S[i].resize(x);
		FOR(j,x) {
			cin>>S[i][j];
			is.insert(S[i][j]);
		}
		if(S[i].back()!=S[i][0]) {
			E[S[i][0]].push_back(S[i].back());
			in[S[i].back()]++;
		}
	}
	queue<int> Q;
	FORR(s,is) if(in[s]==0) Q.push(s);
	while(Q.size()) {
		x=Q.front();
		Q.pop();
		R.push_back(x);
		FORR(e,E[x]) {
			in[e]--;
			if(in[e]==0) Q.push(e);
		}
	}
	FORR(s,is) if(in[s]) return _P("0\n");
	cout<<R.size()<<endl;
	FOR(i,R.size()) {
		if(i) cout<<" ";
		cout<<R[i];
	}
	cout<<endl;
}

まとめ

実装は軽いけど考察が重め。