yukicoder : No.1913 Periodic Comparison

考察が重めの問題。
https://yukicoder.me/problems/no/1913

問題

非負整数から非負整数への写像fがあり、以下の特性を持つ。

• fは全単射である
• 正整数Nが与えられ、f(i)＜f(j)ならf(i+N)＜f(j+N)である。
• 長さNの整数列X,Yが与えられる。この時、f(NX[i]+i)=Y[i]である。

条件を満たすfが存在するなら、f(0)～f(N-1)を答えよ。

解法

上2つの条件について、以下のようにvを0から順に、f(x)=vとなるxを定めることで満たすことができる。
0～(N-1)のラベルを持つN個の数列を考える。
i番の数列のj番目の値は、f(N*j+i)とみなす。

0～(N-1)のいずれかの値を最大1個ずつ取るqueueを考える。このqueueは初期状態で空である。
v=0から順にf(x)=vとなるxに該当する数列を、以下のいずれかを繰り返すことで定めよう。

• queueの先頭の値をとり、そのラベルを持つ数列にvを追加する。先頭の値は末尾に回す。
• queueに含まれない値を1つ選び、そのラベルを持つ数列にvを追加する。選んだ値は末尾に回す。

あとは、3つ目の条件、f(NX[i]+i)=Y[i]を考える。
上記手順を巻き戻すことを考える。すなわち初期状態はqueueには0～(N-1)がすべて何らかの順で入っている状態で、queueの末尾の値を、先頭に戻したり取り除いたりする。
最初、queueの各値は0～(N-1)のどれかわからないので未確定としておく。
vをmax(Y)から巻き戻していこう。
もし、v=Y[i]であるようなiがあったとき、その時点でqueueの値が1つ確定する。またその時点でX[i]の値がわかっているので、その値があとqueueを何周したら取り除かれるかわかる。
そこで、とにかくvを0になるまで巻き戻していき、矛盾が生じたら解なし。

int N;
int X[202020],Y[202020];

int F[202020];
int R[202020];
int rev[2020202];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(rev);
	cin>>N;
	int M=0;
	FOR(i,N) cin>>X[i];
	FOR(i,N) {
		cin>>Y[i];
		
		if(rev[Y[i]]!=-1) {
			cout<<-1<<endl;
			return;
		}
		rev[Y[i]]=i;
		
		M=max({M,X[i],Y[i]});
		
		
		
	}
	queue<int> Q;
	MINUS(R);
	FOR(i,N) Q.push(i);
	for(i=M;i>=0;i--) {
		if(Q.empty()) {
			cout<<-1<<endl;
			return;
		}
			
		x=Q.front();
		Q.pop();
		if(rev[i]>=0) {
			if(R[x]!=-1) {
				cout<<-1<<endl;
				return;
			}
			R[x]=rev[i];
			if(X[R[x]]>0) {
				Q.push(x);
			}
			F[R[x]]=i;
			X[R[x]]--;
		}
		else {
			if(R[x]!=-1) {
				if(X[R[x]]>0) {
					Q.push(x);
				}
				F[R[x]]=i;
				X[R[x]]--;
			}
			else {
				Q.push(x);
			}
		}
	}
	if(Q.size()) {
		cout<<-1<<endl;
		return;
	}
	FOR(i,N) cout<<F[i]<<" ";
	cout<<endl;
	
}

まとめ

なんとなくこうなりそうなのはわかるけど、細かいところを詰めていくのは難しい。