AtCoder Beginner Contest 097 D - Equals

AtCoder Beginner Contest 097 D - Equals が面白かった。

以下のコードは Python3 (3.4.3) で AC を確認している。

問題 D

入力の $P = \{ p_1, p_2, \ldots, p_N \}$ を $x_i, y_i$ によって移り合うもの同士をひとまとめにして、交わりのない集合に分割することを考える。つまり

$$ P = \bigcup_{i=1}^k G_i $$

$$ G_i \cap G_j = \emptyset \left( i \neq j \right) $$

とする。例えば問題の入力例 $1$ の場合は、

$$ \{ p_1, p_3 \}, \{ p_2 \}, \{ p_4, p_5 \} $$

となる。この時、同じ集合内の要素を $x_i, y_i$ を用いて自由に並び替えられるならば、可能な限り $p_i$ の値と添字が一致する場所に移動することで解が得られる。その計算には例えば Union-Find を用いれば良い。

以降は、自由に並び替えられることを見ていく。

$x_i, y_i$ は二要素の交換であり、この操作のことを互換といい $( x_i y_i )$ と書く。互換によって要素を移動することを互換を作用させるという。例えば互換 $( 1 2 )$ に $1$ を作用させる場合は $( 1 2 ) ( 1 ) = 2$ と書く。なお、互換によって動かない場合は $( 1 2 ) ( 3 ) = 3$ となる。

二つの互換 $(a b), (b c)$ から $(a c)$ が得られる。実際に $(b c) (a b) (b c)$ という三つの互換の積を考えると $a$ は $a \rightarrow a \rightarrow b \rightarrow c$ と $c$ へと移り $b$ は $b \rightarrow c \rightarrow c \rightarrow b$ と元に戻り $c$ は $c \rightarrow b \rightarrow a \rightarrow a$ と $a$ へと移るため、これは $(a c)$ に等しい。

同じ集合内の要素は有限個の互換の積で移り合うため、上記の互換の積の還元を繰り返し適用することで、同じ集合内の任意の二つの要素を移し合う互換が得られる。

最後に、任意の置換は互換の積で書けることを示せば、集合内の要素を自由に並び替えることができると示せる。

任意の置換

$$ \sigma = \Big( \begin{array}{cccc} 1 & 2 & \cdots & n\\ a_1 & a_2 & \cdots & a_n\\ \end{array} \Big) $$

に対して $a_1, a_2, \ldots, a_n$ のどれか一つが $1$ であるので、そのような要素を $a_k$ とする。この時、互換 $(1 a_1)$ を用いて

$$ \sigma = (1 a_1) \Big( \begin{array}{cccccc} 1 & 2 & \cdots & k & \cdots & n\\ 1 & a_2 & \cdots & a_1 & \cdots & a_n\\ \end{array} \Big) $$

と書ける。この操作を繰り返すことにより $\sigma$ は互換の積で表すことができる。

以上の考察により $x_i, y_i$ で互いに移り合う要素をまとめて、その中で添え字と値の一致する要素を数え上げればよい。

# Python3 (3.4.3)
class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n

    def root(self, x):
        if self.par[x] == x:
            return x
        r = self.root(self.par[x])
        self.par[x] = r
        return r

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]:
            self.par[x] = ry
            self.par[rx] = ry
        else:
            self.par[y] = rx
            self.par[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

def main():
    N, M, *PXY = map(int, open(0).read().split())
    P = PXY[:N]
    uf = UnionFind(N + 1)
    for i in range(M):
        x, y = PXY[N + 2*i + 0], PXY[N + 2*i + 1]
        uf.unite(x, y)
    ans = 0
    for i in range(N):
        if uf.same(i + 1, P[i]):
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

AtCoder Beginner Contest 097 D - Equals

問題 D

Published

Category

Tags

Contact