kmjp's blog

競技プログラミング参加記です

TopCoder SRM 761: Div1 Medium SortArray

これ落としたのもったいない。
https://community.topcoder.com/stat?c=problem_statement&pm=15578

問題

0~(N-1)のPermutationである数列を、以下のコマンド列に従って並べ替える。
コマンド列中の各コマンドは、数列中のindexのsubsetである。
各コマンドを実行すると、対応するindex内の要素について数列の値を昇順に並べ替える。

元のPermutationがどんな並びでも、コマンド列に従えば最後全体が昇順になるか判定せよ。
ならない場合、その例を示せ。

解法

PermutationをN!通り試すのは当然間に合わない。
N個の要素を、0~(N-1)ではなく0と1の2値に分けることを考える。
この時、0/1の値がどんな組み合わせでも、最終的に昇順になるのであれば条件を満たす。

例えば0がk個の時条件を満たしており、さらにそこから1か所1に置き換えて0が(k-1)個の時も条件を満たすならば、元のk個のどこが0~(k-1)であっても、(k-1)は最終的にあるべき場所に来ることになると言える。

これだとN!通りではなく2^N通りの数列だけ試せばいいので間に合う。

class SortArray {
	public:
	vector <int> verify(int N, vector <int> C) {
		int i,x,y;
		int mask;
		FOR(mask,1<<N) {
			vector<int> V(N,0);
			FOR(y,N) if((mask&(1<<y))==0) V[y]=1;
			
			FORR(c,C) {
				int n[2]={};
				FOR(y,N) if(c&(1<<y)) n[V[y]]++;
				FOR(y,N) if(c&(1<<y)) {
					if(n[0]) n[0]--, V[y]=0;
					else V[y]=1;
				}
			}
			FOR(y,__builtin_popcount(mask)) if(V[y]==1) {
				int a=0,b=__builtin_popcount(mask);
				FOR(y,N) {
					if((mask&(1<<y))) V[y]=a++;
					else V[y]=b++;
				}
				
				return V;
			}
		}
		return {};
		
		
	}
}

まとめ

Challengeフェーズでミスに気づいたんだよねぇ…。