いろはちゃんコンテスト Day2 : H - 根室の巫女

なんか似たようなのどっかで見た気がする。
https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_h

問題

N要素の整数列Aがあったとする。
整数列B[i]は、A[0..(B[i]-1)]=A[(i-B[i])...(i-1)]が一致するような最大の値である。

Bが与えられたとき、対応するAが構成可能なら構成せよ。

解法

B[i]=xとすると、A[i-(x-1)]は少なくともx文字以上prefixと一致する。
という情報を元に、Aを先頭から決めていこう。
B[i]=0となる箇所に遭遇したら、A[i]は未登場の数字を適当に割り当てればよい。

Aを一旦構築したら、再度Bを生成してみて検証しておくこと。

int N;
int B[101010];
int D[101010];
int same[101010];
vector<int> C;
vector<int> Zalgo(vector<int> s) {
	vector<int> v(1,s.size());
	for(int i=1,l=-1,r=-1;i<s.size();i++) {
		if(i<=r && v[i-l]<r-i+1) v.push_back(v[i-l]);
		else {
			l=i; r=(i>r)?i:(r+1);
			while(r<s.size() && s[r-i]==s[r]) r++;
			v.push_back((r--)-l);
		}
	}
	v.push_back(0);
	return v;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>B[i];
		if(i&&B[i]>B[i-1]+1) return _P("No\n");
		if(B[i]) same[i-(B[i]-1)]=max(same[i-(B[i]-1)],B[i]);
	}
	
	int left=0;
	int pos=0;
	FOR(i,N) {
		if(same[i]>left) {
			pos=0;
			left=same[i];
		}
		if(left==0) C.push_back(i+1);
		else {
			C.push_back(C[pos]);
			pos++;
			left--;
		}
	}
	
	auto cand=Zalgo(C);
	
	queue<pair<int,int>> Q;
	FOR(i,N) {
		if(i&&cand[i]>0) Q.push({i,cand[i]});
		while(Q.size()&&i>=Q.front().first+Q.front().second) Q.pop();
		
		if(Q.size()) D[i]=i-Q.front().first+1;
		if(D[i]!=B[i]) return _P("No\n");
		
	}
	
	cout<<"Yes"<<endl;
	FOR(i,N) cout<<C[i]<<" ";
}

まとめ

手間取ったけどまぁ解けて良かった。