SRM 441 DIV1 Easy - PerfectPermutation (復習○)

問題


http://community.topcoder.com/stat?c=problem_statement&pm=10463&rd=13749

ある0~n-1の数がランダムに並べられた、長さnの配列が与えられる。
このとき、childpermutation Bは、
B[0]=0, B[i]=B[A[B[i-1]]で現した時
もとの配列と同様に0~n-1の数が存在するものと定義する。

最初に与えられた数列がchildpermutationを含む時は0を、
配列の数字の入れ替えが発生する場合は元の数列と異なる要素数のうち
最小の差のものを求める。

解き方


すべてpermutationしていては要素数が50のため間に合わない。

ここで、全ての数が現れる場合というのはBがループしている場合ということがわかる。
ループが1つの場合はそのまま答えになるが、
ループが複数存在する場合はお互いの数字を入れ替えることで一つのループにすることができる。

よって、ループの数を計算し1つであれば0、複数存在するのであればループ数を返す。

コード


#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class PerfectPermutation {

public: int reorder(vector<int> P) {
int n=P.size();
int ans=0;

int used[n];
memset(used,0,sizeof(used));
FORE(i,0,n){
if(!used[i]){
used[i]=1;
int x=i;
while(!used[P[x]]){
used[P[x]]=1;
x=P[x];
}
ans++;
}
}

return ans==1 ? 0 : ans;
}

};
このエントリーをはてなブックマークに追加