AtCoder Regular Contest 141 E問題メモ

AtCoder Regular Contest 141

最近のARC、青・黄くらいの難易度帯が少ない。

E - Sliding Edge on Torus

問題

$N \times N$ の正方形状に頂点が並んだグラフを考える
- 平面座標のように $(0,0)～(N-1,N-1)$ で頂点番号を表す
グラフには、はじめ、辺はない
$Q$ 個のクエリが順に与えられるので、以下のように辺を追加する
- クエリは $a,b,c,d$ で与えられる
- $k=0～N-1$ について、$((a+k) \mod N,(b+k) \mod N)$ と $((c+k) \mod N,(d+k) \mod N)$ 間に辺を追加する
各クエリ後における、グラフ全体の連結成分数をそれぞれ答えよ
$2 \le N \le 2 \times 10^5$
$1 \le Q \le 2 \times 10^5$

解法

頂点とクエリの変形

1つのクエリで辺が追加される頂点のうち、 $((a+k) \mod N,(b+k) \mod N)$ の頂点をまとめて $(a,b)$ 側の頂点、もう一方を $(c,d)$ 側の頂点と呼ぶことにする。

追加する辺が斜めにずれていくのがややこしいので、頂点の並べ方を、↘が↓となるよう以下のように変形する。

(0,0)  (0,1)  (0,2)  (0,3)
(1,1)  (1,2)  (1,3)  (1,0)
(2,2)  (2,3)  (2,0)  (2,1)
(3,3)  (3,0)  (3,1)  (3,2)

こうすると、$(a,b)$ 側、$(c,d)$ 側がそれぞれ同じ列になるので、ちょっと考えやすくなる。

また、クエリ $(a,b),(c,d)$ を上端にシフトして、$a=0$ にして考える。こうしてもクエリに対する操作に変化はない。

クエリを $a=0$ にシフトした上で、改めて $b,d$ を「変形後のグラフ上で左から何列目か」という情報に置き換えた値を $(a',b'),(c',d')$ とする。

たとえば、$(a,b),(c,d) = (1,3),(2,3)$ の場合、シフトして $(0,2),(1,2)$ となり、さらに列を置き換えて $(a',b'),(c',d')=(0,2),(1,1)$ となる。

$a'=0$
$b'=(b-a)\mod{N}$
$c'=(c-a)\mod{N}$
$d'=(d-a-c')\mod{N}$

以降、「列」などの表現は、変形した後の並びにおけるものを表すとする。

列ごとの連結成分数

全ての頂点を表現することはメモリ的にできないので、列ごとの連結成分数を記録しておく。

はじめは、全列 $N$ であり、連結成分数は $N^2$ である。

初期状態に「同列に対するクエリ」「異なる列に対するクエリ」が来たときにどうなるか考える。

同列に対するクエリ

必ずしも列の全ての頂点が連結になるとは限らない。
たとえば $N=6$ で $c'=3$ だった場合、3個おきにグループができる。（連結成分は3個となる）

(0,0)┐      連結成分数 6→3
(1,1)┼┐
(2,2)┼┼┐
(3,3)┘││
(4,4)─┘│
(5,5)──┘

一般に、その列の現在の連結成分数が $p$ だった場合、新たな連結成分数は $GCD(p,c')$ となる。

全体の連結成分数 $ans$ は、$ans-p+GCD(p,c')$ に更新される。

異なる列に対するクエリ

列は統合される。
いま、考察の対象とするのは、あくまで双方の列が、まだ他の列と統合されたことがない場合に限るとする。

一般に、統合される前の列の連結成分数が $p,q$ だった場合、新たな連結成分数は $GCD(p,q)$ となる。
全体の連結成分数 $ans$ は、$ans-p-q+GCD(p,q)$ に更新される。

      2      3        ←クエリ前の連結成分数
  ┌(0,0)─(0,1)┐      
┌┼(1,1)─(1,2)┼┐    クエリ後はGCD(2,3)=1 のため、
│├(2,2)─(2,3)┼┼┐  連結成分数は1(全体が連結)になる
├┼(3,3)─(3,4)┘││
│└(4,4)─(4,5)─┘│
└─(5,5)─(5,0)──┘

Union-Findなどで統合列を管理するとよさそう。

クエリにより統合された複数の列を、「列グループ」と呼ぶこととする。

異なる列に対する複数のクエリ

統合されたことのない列同士なら上記のような感じで良いのだが、実際は、統合済みの列がさらに統合されたり、同じ2列の異なる頂点にクエリが来たりする。
この処理をどうするかが難しい。

Union-Findで $b',d'$ が同じ列グループだったとする。

その時、列グループの現在の連結成分数が $p$ なら、クエリ後は $GCD(p,c')$ になる？かというと、そうでもない。

【A】           【B】
                    \ \
(0,0) `(0,1)    (0,0)\ (0,1)
     ＼             \ \
(1,1)  (1,2)    (1,1)\ (1,2)
     ＼             \ \
(2,2)  (2,3)    (2,2)\ (2,3)
     ＼             \ \
(3,3)  (3,4)    (3,3)\ (3,4)
     ＼             \ \
(4,4)  (4,5)    (4,4)\ (4,5)
     ＼             \ \
(5,5)  (5,0)    (5,5)\ (5,0)
     `              `

この両者、いずれも連結成分数は6だが、ここに (0,0)→(3,4) の辺を新たに張ると、$GCD(6,3)=3$ にはならず、連結成分数は【A】は2、【B】は1になる。

この両者を区別するような、データの持たせ方をしないといけない。

ここで、「異なる列グループの間に最初に張る辺は、必ず平行な辺とするよう、一方をシフトさせる」ことを考える。

すると上記はそれぞれ以下のようになり、

【A】           【B】
(0,0)─(1,2)    (0,0)─(2,3)
(1,1)─(2,3)    (1,1)─(3,4)
(2,2)─(3,4)    (2,2)─(4,5)
(3,3)─(4,5)    (3,3)─(5,0)
(4,4)─(5,0)    (4,4)─(0,1)
(5,5)─(0,1)    (5,5)─(1,2)

(0,0)→(3,4) の辺は、それぞれ

【A】は(0,0)と(3,4)=2段下を結ぶ。$GCD(6,2)=2$
【B】は(0,0)と(3,4)=1段下を結ぶ。$GCD(6,1)=1$

となり、結果の連結成分数と一致する。
要は、$c'$ そのものではなく、「$c'$ と、過去に張られた辺との差分」とのGCDが必要で、シフトすることでそれを図的にイメージしやすくなる。

あれ、GCDをとるのは最初に張られた辺との差分だけでいいの？ 3本目が追加されたとき、2番目と3番目の差分は考慮できてなくない？と思うが、 $g=GCD(t_2-t_1,t_3-t_1)$ とすると、$t_1=a_1g+k,t_2=a_2g+k,t_3=a_3g+k$ のように表せるので、結局、$t_3-t_2$ も $g$ の倍数であり、変化しないので大丈夫。

統合済みの列同士の統合

さて、$N=6$ とし、「列1を基準にすると、列2は5のシフト」「列3を基準にすると、列4は3のシフト」という統合済みの列グループが2つあったとする。

列2・4の間に、「列2を基準にすると、列4は2のシフト」が必要な新たなクエリが飛んできたとする。

この場合、全体を統合した結果は「列1を基準にすると、列2は5、列3は4、列4は1のシフト」となる。（$N$ でループする点に注意）

統合済みの1つの列グループに対し、一律にシフト値を増減させても関係性は変わらないので、新たなクエリに矛盾しないように調整する必要がある。

しかし、列グループのサイズは $O(N)$ なので、毎回、一方の列グループの全ての値を書き換えていたら、$O(NQ)$ かかる。

ここで、重み付きUnion-Find、または、ポテンシャル付きUnion-Find などと呼ばれるデータ構造が役に立つ。

UnionFindTree に関する知見の諸々 - noshi91のメモ

要は、以下のような特徴を持ったデータ構造である。

各頂点に、整数値 $A_i$ を割り当てていく（この問題ではシフト値に相当）
いくつかの $(x,y)$ について、「$A_y-A_x=d$ である」という条件が決まっている
条件を順に適用していき、任意のタイミングで、各 $A_i$ を、その時点までの条件に矛盾しないような状態に保つことができる
- たとえば、$(w,z)$ を指定して、$A_z-A_w$ が一意に決まるか判定し、決まるならその値を得ることができる

これを使って、クエリで指定された列 $b',d'$ が、、、

未統合なら
- $b'$ と $d'$ の現在のシフト値 $S_b,S_d$ を得る
- $d'$ の側の列グループ全体をさらに $S_b+c'-S_d$ だけシフトさせつつ、2つの列グループを統合する
- 両者の統合前の連結成分数のGCDが、統合後の列グループの連結成分数
統合済みなら
- $b'$ と $d'$ の現在のシフト値 $S_b,S_d$ を得る
- $c'-(S_d-S_b)$ が、シフトを考慮した上での「何段下と結ぶか」を示す値となる
- 自身の列グループの連結成分数を、上の値とのGCDに更新する

としていくとできる。
もちろん、ポテンシャルUnion-Findを使わなくても、クエリを2回走査して、1回目で全体に矛盾しないシフト値を求め、2回目でそれを使って実際に答えを求める、などでもよい。

Python3

from math import gcd
from typing import Callable


class UnionFindWithPotential:

    def __init__(self, n: int, init: Callable[[], int],
                 func: Callable[[int, int], int],
                 rev_func: Callable[[int, int], int]):
        self.table = [-1] * n
        self.values = [init() for _ in range(n)]
        self.init = init
        self.func = func
        self.rev_func = rev_func

    def root(self, x):
        stack = []
        tbl = self.table
        vals = self.values

        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        if stack:
            val = self.init()
            while stack:
                y = stack.pop()
                val = self.func(val, vals[y])
                vals[y] = val
                tbl[y] = x
        return x

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

    def diff(self, x, y):
        assert self.find(x, y)
        vx = self.values[x]
        vy = self.values[y]
        return self.rev_func(vy, vx)

    def unite(self, x, y, d):
        """ yをxの子にするとき、その差分(y-x)はd """
        rx = self.root(x)
        ry = self.root(y)
        vx = self.values[x]
        vy = self.values[y]
        if rx == ry:
            assert self.rev_func(vy, vx) == d
            return False

        rd = self.rev_func(self.func(vx, d), vy)
        self.table[rx] += self.table[ry]
        self.table[ry] = rx
        self.values[ry] = rd
        return True

    def get_size(self, x):
        return -self.table[self.root(x)]


n, q = map(int, input().split())
ans = n * n
gcds = [n] * n
uft = UnionFindWithPotential(n, int, lambda a, b: (a + b) % n, lambda b, a: (b - a) % n)

for _ in range(q):
    a, b, c, d = map(int, input().split())
    if a > c:
        a, b, c, d = c, d, a, b
    b = (b - a) % n
    c = c - a
    d = (d - a - c) % n
    a = 0

    rb = uft.root(b)
    rd = uft.root(d)
    vb = uft.values[b]
    vd = uft.values[d]
    if rb == rd:
        diff = uft.diff(b, d)
        new = gcd(gcds[rb], (c - diff) % n)
        ans -= gcds[rb]
        ans += new
        gcds[rb] = new
        print(ans)
    else:
        uft.unite(b, d, c)
        new = gcd(gcds[rb], gcds[rd])
        ans -= gcds[rb] + gcds[rd]
        ans += new
        r = uft.root(b)
        gcds[r] = new
        print(ans)

目次