AtCoder ABC #349 : G - Palindrome Construction

Manacher絡むんだろうなと思いつつ細かい実装が詰められなかった。
https://atcoder.jp/contests/abc349/tasks/abc349_g

問題

N要素の整数列Aが与えられる。
以下を満たす正整数列Sが存在する場合、辞書順最小のものを求めよ。

• S[(i-A[i])...(i+A[i])]は回文である
• S[(i-A[i]-1)...(i+A[i]+1)]は回文でない

解法

回文の条件から、値が一致すべきSの添え字を、Union-Findでくっ付けていこう。
これを愚直に行うとO(N^2)回Unionが生じるが、Manacherのアルゴリズムの要領でO(N)回のUnionに落とせる。

次に回文でない条件から、値が一致してはならない添え字の対が求められる。
あとはSの先頭から値を決めていく。
値が一致してはならない添え字の対に違反しない範囲で、最小の正整数を愚直に割り当てていこう。

Manacherの要領でAの配列を読み飛ばすとき、A[i-j]とA[i+j]が実は不一致なのに誤って読み飛ばさないよう注意。

int N;
int A[202020];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt,G[um];
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<202020> uf;
int did[202020];
vector<int> E[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	for(i=j=0;i<N;i+=k,j-=k) {
		for(;j<=A[i];j++) uf(i-j,i+j);
		for(k=1;i-k>=0&&k+A[i-k]+1<j;) {
			if(A[i-k]!=A[i+k]) {
				cout<<"No"<<endl;
				return;
			}
			k++;
		}
	}
	
	
	FOR(i,N) {
		x=i-A[i]-1;
		y=i+A[i]+1;
		if(x>=0&&y<N) {
			x=uf[x];
			y=uf[y];
			if(x==y) {
				cout<<"No"<<endl;
				return;
			}
			E[x].push_back(y);
			E[y].push_back(x);
		}
	}
	
	cout<<"Yes"<<endl;
	FOR(i,N) {
		x=uf[i];
		if(did[x]==0) {
			set<int> D;
			FORR(e,E[x]) D.insert(did[e]);
			did[x]=1;
			while(D.count(did[x])) did[x]++;
		}
		cout<<did[x]<<" ";
	}
	cout<<endl;
	
	
}

まとめ

Fもいまいちだったしダメダメだったな。