これ落としたのもったいない。
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フェーズでミスに気づいたんだよねぇ…。