Codeforces #777 : Div2 E. Madoka and the Sixth-graders

Div2回の割に6問中5問目でAC数少な目。
https://codeforces.com/contest/1647/problem/E

問題

N個の席があり、初期状態で1～N番の人がそれぞれの席についているとする。
i番目の席にはB[i]番の人が座っているとする。

ここで、ある数列Pが与えられる。
1回席替えをすると、以下のように遷移が行われる。

• i番の席に座っていた人がP[i]番の席に移動する。ただし2名以上が同じ席に座ろうとした場合、番号の小さい人が残って大きい人は退場する。
• この手続きによって席に空きができたとき、N+1,N+2...番の人が随時充当される。

なお、Pは少なくとも1名は退場するようになっている。

何回か席替えしたのちの各席に着く人の番号が与えられる。
条件を満たすBのうち辞書順最小のものを求めよ。

解法

N+1番以降の人の残り具合を見れば、何回席替えが行われたかがわかる。
そこで、その回数分巻き戻すと、最初から最後まで残っていた人が最初いられる場所の候補がわかるので、辞書順最小となるように埋めて行こう。

int N;
int P[101010][35];
int A[101010];
int B[101010];
int C[101010];
int go[101010];
vector<int> from[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>P[i][0];
		P[i][0]--;
		C[P[i][0]]++;
	}
	int rem=0;
	FOR(i,N) if(C[i]>1) rem+=C[i]-1;
	int ma=0;
	MINUS(go);
	FOR(i,N) {
		cin>>A[i];
		A[i]--;
		if(A[i]<N) go[A[i]]=i;
		ma=max(ma,A[i]);
	}
	int step=(ma-(N-1))/rem;
	
	vector<int> to;
	FOR(i,N) to.push_back(i);
	FOR(i,30) {
		if(step&(1<<i)) {
			vector<int> to2;
			FOR(j,N) to2.push_back(P[to[j]][i]);
			swap(to,to2);
		}
		FOR(j,N) P[j][i+1]=P[P[j][i]][i];
	}
	FOR(j,N) from[to[j]].push_back(j);
	
	set<int> space;
	
	MINUS(B);
	FOR(i,N) {
		if(go[i]==-1) {
			x=*space.begin();
			B[x]=i+1;
			space.erase(space.begin());
		}
		else {
			int first=0;
			FORR(f,from[go[i]]) {
				if(first==0) {
					B[f]=i+1;
					first=1;
				}
				else {
					space.insert(f);
				}
			}
		}
	}
	FOR(i,N) cout<<B[i]<<" ";
	cout<<endl;
}

まとめ

方針はわかっても細かいところ詰めるの割と面倒くさいな。