−目次

AtCoder Beginner Contest 401 E,F,G問題メモ
- E - Reachable Set
  - 問題文
  - 制約
  - 解法
- F - Add One Edge 3
  - 問題文
  - 制約
  - 解法
- G - Push Simultaneously
  - 問題文
  - 制約
  - 解法

AtCoder Beginner Contest 401 E,F,G問題メモ

AtCoder Beginner Contest 401

E - Reachable Set

問題文

$N$ 頂点 $M$ 辺からなる無向グラフがあります。

頂点には $1,2,\ldots,N$ の番号がついており、 $i$ 番目 $(1\leq i\leq M)$ の辺は頂点 $u _ i$ と頂点 $v _ i$ を結んでいます。

$k=1,2,\ldots,N$ について、次の問題を解いてください。
- 次の操作について考える。
  - 頂点を一つ選ぶ。選んだ頂点と、選んだ頂点に接続する全ての辺をグラフから削除する。
- 上の操作を繰り返すことで、次の条件を満たすことができるか判定せよ。
  - 頂点 $1$ から辺をたどって到達できる頂点の集合が、頂点 $1,$ 頂点 $2,\ldots,$ 頂点 $k$ のちょうど $k$ 個からなる。
- 可能な場合、条件を満たすために少なくとも何回操作を行う必要があるか求めよ。

制約

$1\leq N\leq2\times10 ^ 5$
$0\leq M\leq3\times10 ^ 5$
$1\leq u _ i\lt v _ i\leq N\ (1\leq i\leq M)$
$(u _ i,v _ i)\neq(u _ j,v _ j)\ (1\leq i\lt j\leq M)$
入力はすべて整数

解法

可能かどうかの判定は、以下になる。

「両端がどちらも $k$ 以下の頂点を結ぶ辺」だけで、 $1～k$ が連結になるか？

可能な場合、消さなければいけない頂点は、以下になる。

$1～k$ のいずれかと辺で接している、 $k+1$ 以上の頂点

$k=1,2,...,N$ の順に答えを求めていく。以下のデータを用意する。

$L_{small}[i]:=i$ と辺で結ばれている $i-1$ 以下の頂点の集合
$L_{large}[i]:=i$ と辺で結ばれている $i+1$ 以上の頂点の集合
$UF:=$ Union-Find木
$S:=$ 今現在、 $1～k$ のいずれかと辺で接している、 $k+1$ 以上の頂点の集合

最初、 $UF$ は全頂点バラバラ、 $S$ は空とする。
$k=i$ の時、以下のように状態を更新すればよい。

$L_{small}[i]$ の各頂点と $i$ を $UF$ 上で結ぶ
$S$ に $L_{large}[i]$ の要素を追加し、 $i$ 自身が入っていたら除く
$UF$ で $1～i$ が非連結なら（頂点 $1$ の属する連結成分のサイズが $i$ 未満なら）不可能
連結なら、 $|S|$ が答え

Python3

        
          
          
              
              class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n
 
    def root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x
 
    def find(self, x, y):
        return self.root(x) == self.root(y)
 
    def unite(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return False
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1
        return True
 
    def get_size(self, x):
        return -self.table[self.root(x)]
 
 
def solve(n, m, edges):
    small_edges = [set() for _ in range(n)]
    large_edges = [set() for _ in range(n)]
    for u, v in edges:
        u -= 1
        v -= 1
        small_edges[u].add(v)
        large_edges[v].add(u)
    ans = []
    uft = UnionFind(n)
    remove = set()
    for i in range(n):
        remove.update(small_edges[i])
        remove.discard(i)
        for j in large_edges[i]:
            uft.unite(i, j)
        if uft.get_size(0) != i + 1:
            ans.append(-1)
            continue
        ans.append(len(remove))
    return ans
 
 
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
ans = solve(n, m, edges)
print('\n'.join(map(str, ans)))

            

        
      

F - Add One Edge 3

問題文

$N_1$ 頂点の木 $1$ と、 $N_2$ 頂点の木 $2$ が与えられます。
木 $1$ の頂点 $i$ と、木 $2$ の頂点 $j$ を双方向に結ぶ辺を追加すると一つの木が得られます。この木の直径を $f(i,j)$ と定めます。
$\displaystyle \sum_{i=1}^{N_1}\sum_{j=1}^{N_2} f(i,j)$ を求めてください。

制約

$1\leq N_1,N_2\leq 2\times 10^{5}$
$1\leq u_{1,i},v_{1,i}\leq N_1$
$1\leq u_{2,i},v_{2,i}\leq N_2$
入力されるグラフは共に木
入力される数値は全て整数

解法

それぞれの木につき、以下を計算する。これは、Rerooting（全方位木）で求められる。

$\mathrm{Farthest}_t[i]:=$ 木 $t$ の中で、頂点 $i$ から最も遠い頂点までの距離

また、2つの木の（結ぶ前での）直径のうち、大きい方を $D$ とすると、以下が成り立つ。

$g(i,j):=\mathrm{Farthest}_1[i]+\mathrm{Farthest}_2[j]+1$ として、
$f(i,j)=\max(D, g(i,j))$

木 $1$ 側の頂点 $i$ を固定する。

この時 $f(i,j)$ が $D$ になるか $g(i,j)$ になるかは、 $\mathrm{Farthest}_2[j] \le D-\mathrm{Farthest}_1[i]-1$ かどうかで判定できる。

$\mathrm{Farthest}_2$ をソートしておけば、二分探索で $D$ になる方の個数が求められる。

またソート後の累積和も計算しておけば、 $g(i,j)$ になる方だけの $\mathrm{Farthest}_2[j]$ の総和もわかるので、答えが計算できる。

Python3

        
          
          
              
              from bisect import bisect_left
from itertools import accumulate
 
from dataclasses import dataclass
from typing import List, Callable, TypeVar
 
T = TypeVar('T')
U = TypeVar('U')
 
 
@dataclass
class RerootingEdge:
    src: int
    tgt: int
    value: U
 
 
class Rerooting:
    """
    抽象化 全方位木DP
    ・r = 1,2,...,N について、頂点 r を根とした木DPの結果（DP[r]）を求める。
    ・merge 演算に逆演算が成り立たない場合に対応
    ・頂点に対して値が決められている場合、辺に対して値が決められている場合（あるいは両方）のいずれにも対応
 
    【使い方】
    ① __init__()に示された関数を定義する
    ② add_edge()にてN-1本の辺を与える。u→v と v→u で2回呼んで双方向で与える。
    ③ solve()
 
    【apply, merge 関数で処理すべき内容】
       (u)      ans[v] には、"v 自身の値は未反映の" v 以下の部分木に対するDP結果が入る。（その方が定義する関数の数を減らせるため）
      ／|＼      （※ たとえば「ans[i] = i 以下の部分木の頂点数」とした場合、ans[v] には v 自身は加算されていない）
    (v)(w)(x)   ans[u] を求める際に呼ばれる apply(ans[v]) 内で、v についての情報を反映する。
                apply では↑と同時に、辺をu→vとたどる際に何らかの処理が行われる場合はそれも反映する。頂点 u の値の反映は行わない。
                merge は、[ unit, apply(ans[v]), apply(ans[w]), apply(ans[x]) ] を左から2つずつ累積的に合成していく処理を行う。
                全てマージされた結果が、ans[u] となる。
    """
 
    def __init__(self,
                 n: int,
                 leaf_factory: Callable[[], T],  # 1回目のDFSで葉に適用する値
                 unit_factory: Callable[[], T],  # 単位元
                 merge: Callable[[T, T], T],  # 演算
                 apply: Callable[[T, RerootingEdge], T],  # [子の値, 親→子への辺] から、親に伝える情報を計算
                 ) -> None:
        self.n: int = n
        self.links: List[List[RerootingEdge]] = [[] for _ in range(n)]
        self.leaf = leaf_factory
        self.unit = unit_factory
        self.merge = merge
        self.apply = apply
 
    def add_edge(self, s, t, value) -> None:
        self.links[s].append(RerootingEdge(src=s, tgt=t, value=value))
 
    def solve(self) -> List[T]:
        links = self.links
        status = [0] * self.n
 
        leaf = self.leaf
        unit = self.unit
        merge = self.merge
        apply = self.apply
 
        # 1回目のDFSで、自身の子のapply済み結果の左からの累積和
        acc_left: List[List[T]] = [[unit()] for _ in range(self.n)]
        # 1回目のDFSで、自身の子のapply済み結果の右からの累積和
        acc_right: List[List[T]] = [[unit()] for _ in range(self.n)]
 
        # 最終結果（1回目のDFSでは自身のsubtreeのみの結果が入る）
        ans: List[T] = [unit() for _ in range(self.n)]
        # 親に向かう辺
        parents: List[RerootingEdge | None] = [None for _ in range(self.n)]
        # 2回目のDFSで、親から伝播される値（apply済）
        from_parent: List[T] = [unit() for _ in range(self.n)]
 
        q = [0]
        while q:
            v = q[-1]
            if status[v] == 0:
                status[v] = 1
 
                # 親頂点をリンクリストから除く
                children_links = []
                for e in links[v]:
                    if status[e.tgt] == 0:
                        children_links.append(e)
                    else:
                        parents[v] = e
                links[v] = children_links
 
                for e in links[v]:
                    q.append(e.tgt)
            else:
                q.pop()
 
                if len(links[v]) == 0:
                    ans[v] = leaf()
 
                else:
                    acl = acc_left[v]
 
                    for e in links[v]:
                        acl.append(apply(ans[e.tgt], e))
 
                    acr = acc_right[v]
                    for i in range(len(acl) - 1, 0, -1):
                        acr.append(merge(acl[i], acr[-1]))
                    acr.reverse()
 
                    for i in range(1, len(acl)):
                        acl[i] = merge(acl[i - 1], acl[i])
 
                    ans[v] = acl[-1]
 
                status[v] = 2
 
        q = [0]
        while q:
            v = q.pop()
            fp = from_parent[v]
            ans[v] = merge(ans[v], fp)
 
            acl = acc_left[v]
            acr = acc_right[v]
            for li, e in enumerate(links[v]):
                pe = parents[e.tgt]
                tgt_data = merge(fp, merge(acl[li], acr[li + 1]))
                from_parent[e.tgt] = apply(tgt_data, pe)
                q.append(e.tgt)
 
        return ans
 
 
def solve(n1, edges1, n2, edges2):
    apply = lambda cv, edges: cv + 1
    reroot1 = Rerooting(n1, int, int, max, apply)
    reroot2 = Rerooting(n2, int, int, max, apply)
    for u, v in edges1:
        u -= 1
        v -= 1
        reroot1.add_edge(u, v, 0)
        reroot1.add_edge(v, u, 0)
    for u, v in edges2:
        u -= 1
        v -= 1
        reroot2.add_edge(u, v, 0)
        reroot2.add_edge(v, u, 0)
    farthest1 = reroot1.solve()
    farthest2 = reroot2.solve()
    d = max(max(farthest1), max(farthest2))
    if len(farthest1) > len(farthest2):
        n1, n2 = n2, n1
        farthest1, farthest2 = farthest2, farthest1
    farthest2.sort()
    acc = [0] + list(accumulate(farthest2))
    total = acc[-1]
 
    ans = 0
    for du in farthest1:
        lim = d - du
        k = bisect_left(farthest2, lim)
        ans += d * k + (du + 1) * (n2 - k) + total - acc[k]
    return ans
 
 
n1 = int(input())
edges1 = [tuple(map(int, input().split())) for _ in range(n1 - 1)]
n2 = int(input())
edges2 = [tuple(map(int, input().split())) for _ in range(n2 - 1)]
ans = solve(n1, edges1, n2, edges2)
print(ans)

            

        
      

基本的な解法は変わらないが、全方位木など使わなくても、もう少し単純に以下のように考えることもできる。

木において、各頂点から最も遠い頂点の1つは、木の直径の両端のいずれかになる。

木の直径の両端の頂点 $u,v$ を求め、 $u,v$ から各点までの距離 $d_u(i),d_v(i)$ を求めれば、 $\mathrm{Farthest}[i]=\max(d_u(i),d_v(i))$ で求められる。

G - Push Simultaneously

問題文

平面上に $N$ 人の高橋くんと $N$ 個のボタンがあります。
平面上には原点があり、原点から東に $x$ メートル進み、北に $y$ メートル進んだ位置を座標 $(x,y)$ で表すこととします。
- $i$ 番目 $(1\leq i\leq N)$ の高橋くんははじめ座標 $(\mathit{sx} _ i,\mathit{sy} _ i)$ にいます。
- $i$ 番目 $(1\leq i\leq N)$ のボタンは座標 $(\mathit{gx} _ i,\mathit{gy} _ i)$ にあります。
高橋くんたちはそれぞれ移動をした後、この $N$ 個のボタンを一斉に押したいです。
- 各ボタンは、そのボタンがある座標にいる高橋くんだけが押すことができます。
それぞれの高橋くんは秒速 $1$ メートル以下の速さで好きな方向に進むことができます。
高橋くんたちが目標を達成するために必要な時間を求めてください。
- 相対誤差が $10^{-6}$ 以下の時、正解と判定されます。

制約

$1\leq N\leq 300$
$0\leq\mathit{sx} _ i\leq10 ^ {18}\ (1\leq i\leq N)$
$0\leq\mathit{sy} _ i\leq10 ^ {18}\ (1\leq i\leq N)$
$0\leq\mathit{gx} _ i\leq10 ^ {18}\ (1\leq i\leq N)$
$0\leq\mathit{gy} _ i\leq10 ^ {18}\ (1\leq i\leq N)$
$(\mathit{sx} _ i,\mathit{sy} _ i)\neq(\mathit{sx} _ j,\mathit{sy} _ j)\ (1\leq i\lt j\leq N)$
$(\mathit{gx} _ i,\mathit{gy} _ i)\neq(\mathit{gx} _ j,\mathit{gy} _ j)\ (1\leq i\lt j\leq N)$
$(\mathit{sx} _ i,\mathit{sy} _ i)\neq(\mathit{gx} _ j,\mathit{gy} _ j)\ (1\leq i\leq N,1\leq j\leq N)$
入力はすべて整数

解法

要は、 $N$ 組の高橋君とボタンをマッチングさせた時、最もユークリッド距離が大きい組の距離を最小化させる問題。

実数 $X$ に対して以下の問題が解ければ、答えを二分探索できる。

高橋君 $i$ とボタン $j$ のユークリッド距離を $d(i,j)$ とする。
高橋君とボタンをそれぞれ表現する $2N$ 個の頂点からなる二部グラフを考える。
$d(i,j) \le X$ であるような $i,j$ のみに辺があるグラフに、完全マッチングが存在するか？

これは愚直に各辺を調べた後に最大流問題で $O(V^2 + \sqrt{V}E)$ などで解ける。（ $V$ 頂点数、 $E$ 辺数）

この最大流の計算が、二分探索で何回繰り返されるかを概算する。
相対誤差が $10^{-6}$ まで許容されるので、だいたい上位6桁があってたらいい。
だが、真の答えの最大値は $\sqrt{2} \times 10^{18}$ 、最小値は $1$ である。もし真の答えが $1$ の場合、相対誤差を満たすには $1.000000$ まで求めないといけない。最大から、 $1.000000$ まで二分探索で求めようとすると、80回程度の繰り返しが必要となってしまう。

また、各座標の距離が互いに近いケースでは、大半の繰り返しにおいて、最大流のグラフで全ての辺が条件を満たすため、 $E = V^2$ となる。これが繰り返されると、最大流の計算で毎回 $O(V^{2.5})$ の計算量がかかってしまう。
これを80回繰り返すと $V=300$ の元で約 $1.2 \times 10^8$ となり、言語によっては時間が厳しい。

公式Editorial では、そもそも答えはどれかの(高橋君,ボタン)ペアの距離と一致し、候補は $N^2$ 個しか無いのだから、それ基準で二分探索すると繰返し回数は $O(\log{N})$ で済むよ、と言っている。確かに。これなら繰り返しは確実に20回未満で済む。

Python3

        
          
          
              
              from collections import deque
from typing import Tuple, List
 
 
class Dinic:
    """
    Usage:
       mf = Dinic(n)
    -> mf.add_link(from, to, capacity)
    -> mf.max_flow(source, target)
    """
 
    def __init__(self, n: int):
        self.n = n
        self.links: List[List[List[int]]] = [[] for _ in range(n)]
        # if exists an edge (v→u, capacity)...
        #   links[v] = [ [ capacity, u, index of rev-edge in links[u], is_original_edge ], ]
 
    def add_link(self, from_: int, to: int, capacity: int) -> None:
        self.links[from_].append([capacity, to, len(self.links[to]), 1])
        self.links[to].append([0, from_, len(self.links[from_]) - 1, 0])
 
    def bfs(self, s: int) -> List[int]:
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev, _ in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        return depth
 
    def dfs(self, s: int, t: int, depth: List[int], progress: List[int], link_counts: List[int]) -> int:
        links = self.links
        stack = [s]
 
        while stack:
            v = stack[-1]
            if v == t:
                break
            for i in range(progress[v], link_counts[v]):
                progress[v] = i
                cap, to, rev, _ = links[v][i]
                if cap == 0 or depth[v] >= depth[to] or progress[to] >= link_counts[to]:
                    continue
                stack.append(to)
                break
            else:
                progress[v] += 1
                stack.pop()
        else:
            return 0
 
        f = 1 << 60
        fwd_links = []
        bwd_links = []
        for v in stack[:-1]:
            cap, to, rev, _ = link = links[v][progress[v]]
            f = min(f, cap)
            fwd_links.append(link)
            bwd_links.append(links[to][rev])
 
        for link in fwd_links:
            link[0] -= f
 
        for link in bwd_links:
            link[0] += f
 
        return f
 
    def max_flow(self, s: int, t: int) -> int:
        link_counts = list(map(len, self.links))
        flow = 0
        while True:
            depth = self.bfs(s)
            if depth[t] < 0:
                break
            progress = [0] * self.n
            current_flow = self.dfs(s, t, depth, progress, link_counts)
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, depth, progress, link_counts)
        return flow
 
    def cut_edges(self, s: int) -> List[Tuple[int, int]]:
        """ max_flowしたあと、最小カットにおいてカットすべき辺を復元する """
        q = [s]
        reachable = [0] * self.n
        reachable[s] = 1
        while q:
            v = q.pop()
            for cap, u, li, _ in self.links[v]:
                if cap == 0 or reachable[u]:
                    continue
                reachable[u] = 1
                q.append(u)
        edges = []
        for v in range(self.n):
            if reachable[v] == 0:
                continue
            for cap, u, li, orig in self.links[v]:
                if orig == 1 and reachable[u] == 0:
                    edges.append((v, u))
        return edges
 
 
def solve(n, starts, goals):
    distances = [[0.] * n for _ in range(n)]
    lo_limit = 0.
    hi_limit = 0.
    for i in range(n):
        sx, sy = starts[i]
        for j in range(n):
            gx, gy = goals[j]
            d2 = (sx - gx) ** 2 + (sy - gy) ** 2
            distances[i][j] = d2 ** 0.5
        lo_limit = max(lo_limit, min(distances[i]))
        hi_limit = max(hi_limit, max(distances[i]))
 
    l = lo_limit
    r = hi_limit
    eps = 1e-7
    s = n * 2
    t = s + 1
    while True:
        if (r - l) / r < eps:
            break
        lim = (l + r) / 2
 
        dnc = Dinic(n * 2 + 2)
        for i in range(n):
            dnc.add_link(s, i, 1)
            dnc.add_link(i + n, t, 1)
            for j in range(n):
                d = distances[i][j]
                if d <= lim:
                    dnc.add_link(i, j + n, 1)
        f = dnc.max_flow(s, t)
        if f == n:
            r = lim
        else:
            l = lim
 
    return r
 
 
n = int(input())
starts = [tuple(map(int, input().split())) for _ in range(n)]
goals = [tuple(map(int, input().split())) for _ in range(n)]
ans = solve(n, starts, goals)
print(f'{ans:.7f}')

            

        
      