Codeforces Global Round 15 : G. A Serious Referee

コード量はそこまで長くないのだが。
https://codeforces.com/contest/1552/problem/G

問題

N要素の数列を、Kステップでソートすることを考える。
i番目のステップでは、ソート対象の数列の添字の集合が与えられるので、それらの要素を昇順に並べる。

この手順を行ったとき、全要素をちゃんとソートできるか判定せよ。

解法

0/1で構成された数列で常に条件を満たすなら、この手順でソートできるといえる。
なので、DFSでKステップを順に処理し、今まで処理しなかった初めて登場した添え字について、0/1の個数を総当たりして、最終的に0/1の数列がソートされるかを判定しよう。

int N,K;
ll active[55],sum[55];
int newbit[55];
ll mask[55][55];

void dfs(ll cur,int i) {
	if(i==K) {
		ll shift=((~cur)>>1)&((1LL<<(N-1))-1);
		if(cur&shift) {
			cout<<"REJECTED"<<endl;
			exit(0);
		}
		return;
	}
	int cur_ones = __builtin_popcountll(cur&active[i]);
	cur &= ~active[i];
	for(int add=0;add<=newbit[i];add++) {
		dfs(cur | mask[i][cur_ones+add], i+1);
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,K) {
		cin>>x;
		vector<int> Q;
		FOR(j,x) {
			cin>>y;
			y--;
			Q.push_back(y);
			active[i] |= 1LL<<y;
		}
		reverse(ALL(Q));
		FOR(j,x) {
			mask[i][j+1]=mask[i][j] | (1LL<<Q[j]);
		}
		
		newbit[i]=__builtin_popcountll(active[i]&~sum[i]);
		sum[i+1]=sum[i] | active[i];
	}
	
	if(N==1) {
		cout<<"ACCEPTED"<<endl;
		return;
	}
	
	if(sum[K]!=(1LL<<N)-1) {
		cout<<"REJECTED"<<endl;
		return;
	}
	
	dfs(0,0);
	cout<<"ACCEPTED"<<endl;
	
}

まとめ

Editorialにあるけど、計算量の見積もりがかなり独特。