Codeforces #559 Div1 C. Permutation recovery

これは思いつけて良かったね。
https://codeforces.com/contest/1158/problem/C

問題

1～NのPermutation Pがあったとする。
この時、数列Qは以下のように定義される。

• Q[i]は、P[Q[i]]＞P[i]となるようなiより大きな整数のうち最小の値。すなわち後続にある最寄の自身より大きな要素のindex。

Qが与えられたとき、条件を満たすPがあるならそれを復元せよ。
ただし、Qの一部は欠損している。

解法

まず欠損部分を埋めよう。
仮に数列の最後に値(N+1)の要素があると考え、数列のindexをラベルとするN+1頂点の有向グラフを考える。
ここでQ[i]→iと辺を張ったとする。
問題の条件より、i＜j＜Q[i]＜Q[j]のように有向グラフが交差するような関係になることはありえない。
P[i]＞P[j]なら、P[Q[i]]＞P[j]だし、P[i]＜P[j]ならQ[i]はjとなるためである。

逆にそのような関係があると条件を満たすPは存在しない。
なので、欠損部分は矛盾ができるだけ生じないよう、Q[i]=i+1と最短にしておくとよい。

そうしたうえで、上記の交差判定を先に行おう。
これはdeque等使いスライド最小値の要領で行えばよい。
矛盾がある場合ここで終了する。

こうすると、有向グラフは(N+1)番の頂点を根とする木の形になる。
あとはDFS順なりBFS順なりで頂点訪問し、大きい順に値を割り当てればよい。

int T,N;
int nex[501010];
int la[501010];
vector<int> tar[501010];
int ret[501010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&T);
	while(T--) {
		scanf("%d",&N);
		for(i=1;i<=N+1;i++) la[i]=i,tar[i].clear();
		for(i=1;i<=N;i++) {
			scanf("%d",&nex[i]);
			if(nex[i]==-1) nex[i]=i+1;
			tar[la[nex[i]]].push_back(i);
			la[nex[i]]=i;
		}
		deque<int> D;
		for(i=1;i<=N;i++) {
			while(D.size()&&D.front()==i) D.pop_front();
			if(D.size()&&D.front()<nex[i]) {
				_P("-1\n");
				break;
			}
			D.push_front(nex[i]);
		}
		if(i<=N) continue;
		
		int cur=N+1;
		queue<int> Q;
		Q.push(N+1);
		while(Q.size()) {
			x=Q.front();
			Q.pop();
			
			ret[x]=cur--;
			FORR(t,tar[x]) Q.push(t);
		}
		assert(cur==0);
		for(i=1;i<=N;i++) _P("%d ",ret[i]);
		_P("\n");
	}
}

まとめ

シンプルな設定で良かった。
C問題とはいえ1250ptと言えばそんなもんかな。