第6回 ドワンゴからの挑戦状 予選 : D - Arrangement

Cよりこっちの方があっさり。
https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_d

問題

1～Nの整数が書かれたカードが1枚ずつある。
これらを横1列に並べる。
整数iの書かれたカードの右隣にP[i]のカードが来てはならない、という条件が各iに対し1つずつ指定される。
条件を満たす並べ方のうち、左からの並び順が辞書順最小のものを求めよ。

解法

辞書順最小のものを求める問題なので、基本的には左から順に小さい数字を置こうと深さ優先で試みればよい。
なお、カードが4枚以上あれば常に置く手段はあるので、基本的に小さい順においてしまってよい。

これで基本的によいが、例外として残ったカードのうち1枚以外のカードがその1枚を右に置きたくない、といった場合はそのカードを最も左におかなければならない。
(そうしないとそのカードの整数が最大の場合、O(N!)かかる可能性がある。)
そこで、残されたカードに関し、いくつのカードに右に置きたくないと思われているかを管理しておくとよい。

int N;
int A[101010];
vector<int> R;
set<int> S;
int C[101010];
set<pair<int,int>> cnt;

void dfs(int ng) {
	int x,y;
	if(S.empty()) {
		FORR(r,R) cout<<r+1<<" ";
		cout<<endl;
		exit(0);
	}
	
	if(S.size()==2) {
		x=*S.begin();
		y=*S.rbegin();
		if(A[x]==y && A[y]==x) return;
	}
	
	if(cnt.rbegin()->first==S.size()-1) {
		y=cnt.rbegin()->second;
		if(y!=ng) {
			S.erase(y);
			R.push_back(y);
			cnt.erase({C[y],y});
			if(S.count(A[y])) {
				cnt.erase({C[A[y]],A[y]});
				C[A[y]]--;
				cnt.insert({C[A[y]],A[y]});
			}
			dfs(A[y]);
			if(S.count(A[y])) {
				cnt.erase({C[A[y]],A[y]});
				C[A[y]]++;
				cnt.insert({C[A[y]],A[y]});
			}
			cnt.insert({C[y],y});
			R.pop_back();
			S.insert(y);
		}
	}
	else {
		x=0;
		while(1) {
			auto it=S.lower_bound(x);
			int y=*it;
			if(it==S.end()) return;
			
			if(y!=ng) {
				S.erase(it);
				R.push_back(y);
				cnt.erase({C[y],y});
				if(S.count(A[y])) {
					cnt.erase({C[A[y]],A[y]});
					C[A[y]]--;
					cnt.insert({C[A[y]],A[y]});
				}
				dfs(A[y]);
				if(S.count(A[y])) {
					cnt.erase({C[A[y]],A[y]});
					C[A[y]]++;
					cnt.insert({C[A[y]],A[y]});
				}
				cnt.insert({C[y],y});
				R.pop_back();
				S.insert(y);
			}
			x=y+1;
		}
	}
	
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	FOR(i,N) {
		cin>>A[i];
		A[i]--;
		C[A[i]]++;
		S.insert(i);
	}
	
	FOR(i,N) cnt.insert({C[i],i});
	
	dfs(-1);
	_P("-1\n");
	
}

まとめ

このあとCがすんなり思いついた。