yukicoder : No.1370 置換門松列

これもなかなか面白い問題。
https://yukicoder.me/problems/no/1370

問題

N要素の整数列Aが与えられる。
別の整数列Xに対し、Y=(X[A[0]], X[A[1]], ..., X[A[N-1]])で構築されるYが門松列列となるようなXを構築せよ。

解法

• A[i]==A[i+1]の場合、X[A[i]], X[A[i+1]]を含む部分が門松列にならないので解なし。
• A[i]==A[i+2]の場合、X[A[i]], X[A[i+1]], X[A[i+2]]の両端の値が一致するので解なし。

それ以外の場合、YはY[i]＜Y[i+1]とY[i]＞Y[i]を交互に繰り返すジグザグな数列となる。
ここから、偶数eに対しX[A[e-1]]＜X[A[e]]かつX[A[e]]＞X[A[e+1]]となる。
この大小関係をグラフの有向辺とみなすと、トポロジカルソート順にX[A[i]]の値を決めていくことができる。

int N,M;
int A[101010];

vector<int> E[101010];
int in[101010];
int ret[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i], A[i]--;
	
	FOR(i,N-1) if(A[i]==A[i+1]) return _P("No\n");
	FOR(i,N-2) if(A[i]==A[i+2]) return _P("No\n");
	FOR(i,N-1) {
		if(i%2==0) {
			E[A[i]].push_back(A[i+1]);
			in[A[i+1]]++;
		}
		else {
			E[A[i+1]].push_back(A[i]);
			in[A[i]]++;
		}
	}
	
	queue<int> Q;
	FOR(i,M) if(in[i]==0) Q.push(i);
	int cur=0;
	while(Q.size()) {
		x=Q.front();
		Q.pop();
		ret[x]=++cur;
		FORR(e,E[x]) {
			in[e]--;
			if(in[e]==0) Q.push(e);
		}
	}
	if(cur!=M) return _P("No\n");
	cout<<"Yes"<<endl;
	FOR(i,M) cout<<ret[i]<<" ";
	cout<<endl;
	
}

まとめ

色々考えるなぁ。