みんなのプロコン 2018 決勝 : D - LCP(prefix,suffix)

これは勉強になりました。
https://beta.atcoder.jp/contests/yahoo-procon2018-final-open/tasks/yahoo_procon2018_final_d

問題

長さNの数列Aが与えられる。
以下の条件を満たすN文字の文字列Sは存在するか。なお、文字の種類に上限はない。

• Sのi文字のprefix(S[1..i])と、Sのi文字のSuffix(S[N-i+1..N])では、最長で先頭A[i]文字が一致する。

解法

Union-Findで同じ文字が来る位置を連結させることを考える。
S[1...i]とS[N-i+1...N]で先頭A[i]文字が一致するなら、これは以下を満たすことを意味する。

• S[1]=S[N-i+1]
• S[2]=S[N-i+2]

....

• S[A[i]]=S[N-i+A[i]]
• S[A[i]+1]!=S[N-i+A[i]+1]

まずA全てについて、文字が一致する位置をUniteしよう。
その後、本来異なる文字が来る位置(すなわちprefixの(A[i]+1)文字目)に同じ文字が来てしまう場合、それは条件を満たせないということになる。

問題は、上記処理では最悪Unite回数がO(N^2)となり、Unite1回の処理が軽くてもTLEすることである。

そこでダブリングを用いる。logN個程度Union-Findのデータ構造を作る。
uf(level,i) = uf(level,j) である場合、S[i...(i+2^level-1)]とS[j...(j+2^level-1)]が一致する、とみなすことにする。
こうすると、各A[i]に対し、Sparse Tableに似た考え方で、A[i]回Uniteすることなく、適切なlevelを求めればあるレベルに対し高々2回Uniteすれば済む。

こうして作成したlogN個のUnion-Findデータ構造を合わせていこう。
uf(level,i) = uf(level,j)であるということは、uf(level-1,i) = uf(level-1,j)かつuf(level-1,i+2^(level-1)) = uf(level-1,j+2^(level-1))であるとみなせるので、高いレベルのデータから順次下のレベルに再帰的にUnion関係を伝搬させることができる。

int N;
int L[303030];

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf[20];
vector<int> C[301010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>L[i];
		if(L[i]) {
			j=0;
			while(1<<(j+1)<=L[i]) j++;
			uf[j](0,N-1-i);
			uf[j](L[i]-(1<<j),N-1-i+L[i]-(1<<j));
		}
	}
	for(i=19;i>=1;i--) {
		FOR(x,N) C[x].clear();
		FOR(x,N) C[uf[i][x]].push_back(x);
		FOR(x,N) if(C[x].size()>1) {
			FOR(y,C[x].size()-1) {
				uf[i-1](C[x][y],C[x][y+1]);
				uf[i-1](C[x][y]+(1<<(i-1)),C[x][y+1]+(1<<(i-1)));
			}
		}
	}
	
	FOR(i,N) {
		if(L[i]<N && uf[0][L[i]]==uf[0][N-1-i+L[i]]) return _P("No\n");
	}
	_P("Yes\n");
}

まとめ

この考え方は勉強になった。