TopCoder SRM 728 Div2 Hard: TrisomorphismEasy

するめうめ

問題概要

原文 → TopCoder Statistics - Problem Statement

$N \ \ (1 \leq N \leq 10)$ 頂点の有向グラフがあり、各頂点はそれぞれ $0$ から $N-1$ までの番号でラベル付けされている。

ある $3$ つの頂点を選び、ラベルをローテーションするという操作を何回か行い、元のグラフのラベリングを変更する。

これによってできる、元のグラフと異なる unique なグラフは何通りあるか。

解説

$1$ 回の操作は長さ $3$ の巡回置換です。

$\left( 1\ \ 2\ \ 3 \right) = \left( 1\ \ 2 \right) \left( 1\ \ 3 \right)$ と、 $2$ つの互換の積で表せることから、これは偶置換です。偶置換を何回か適用したものもまた偶置換なので、結局「元の順列に対して、全ての偶置換を適用することを考えれば良い」ことがわかります。実際に $N$ が小さいため、全て試すことができます。

さて、ある順列 $P$ に対して、その転倒数の偶奇は置換の偶奇に等しいという重要な性質があります。つまり、順列を試すときはその転倒数を調べ、それが奇数であれば無視する必要があります。

あとは unique なグラフの調べ方ですが、「頂点 $x$ から出ている辺が $y$ につながっている」という情報が一つでも異なれば unique です。したがって、各頂点についてどこにつながっているかを見て、それを適当に hash にして管理すればよいです。

ソースコード

class TrisomorphismEasy {
    public:
    int count(vector<int> edgeTo) {
        int N = edgeTo.size();
        vector<ll> pw(N, 1), trans(N);
        iota(trans.begin(), trans.end(), 0);

        for(int i=1; i<N; i++) {
            pw[i] = pw[i-1] * 10;
        }

        unordered_set<ll> S;
        do {
            bool rev = false;
            for(int i=0; i<N; i++) {
                for(int j=i+1; j<N; j++) {
                    if(trans[i] > trans[j]) rev ^= 1;
                }
            }
            if(rev) continue;

            ll hash = 0;
            for(int i=0; i<N; i++) {
                hash += pw[ trans[i] ] * trans[ edgeTo[i] ];
            }
            S.insert(hash);
        }while(next_permutation(trans.begin(), trans.end()));

        return (int)S.size() - 1;
    }
};