AtCoder Beginner Contest 223 F,G問題メモ

F - Parenthesis Checking

問題

'(' と ')' からなる文字列 $S$ に対して、クエリが $Q$ 個与えられる
クエリ
- $o_i, l_i, r_i$ の3つの整数が与えられる
- $o_i=1$ のとき、$S_{li}$ と $S_{ri}$ の文字を入れ替える
- $o_i=2$ のとき、$S_{li}S_{li+1}...S_{ri}$ からなる部分文字列が正しい括弧列か判定する
クエリ2に全て答えよ
$1 \le |S|,Q \le 2 \times 10^5$

解法

区間加算更新・区間min取得の遅延評価セグメント木。
遅延セグ木はACL Libraryにあるが、更新操作と取得操作の演算が違ってもちゃんと使えますか、という練習問題かも。

正しい括弧列の判定は、'(' を $+1$、')' を $-1$ に置きかえて、累積和を考えるのがよくある解法。

    0 1 2 3 4   Sのindex
--------------
S   ( ( ) ) ( 
A  0 1 2 1 0 1  累積和
--------------
   0 1 2 3 4 5  累積和のindex

文字列 $S$ から $[l,r)$ を取り出した部分文字列が正しい括弧列かどうかは、以下をともに満たすかで判定できる。

$A_l=A_r$
$A_l,A_{l+1},...,A_{r}$ の最小値が $A_l$ に等しい

要は、開き括弧と閉じ括弧の数は等しいですか、途中で開かれた括弧より閉じた括弧の方が多くなっていませんか、ということを確認している。

区間minが必要になるので、Aをセグメント木で管理するなどで、'2'のクエリには答えることができる。

しかし、今回は'1'のクエリ、括弧を入れ替えるという操作が出てくる。
$S_l$ と $S_r$ の入れ替えにより累積和がどう影響するかというと、

$S_l=S_r$ のとき
- 何も変わらない
$S_l=($、$S_r=)$ のとき
- $A_{l+1}～A_{r}$ の値が $-2$ ずつされる
$S_l=)$、$S_r=($ のとき
- $A_{l+1}～A_{r}$ の値が $+2$ ずつされる

このようになるので、区間加算ができればよい。

$A$ に対して区間更新と区間取得ができればよいので、遅延評価セグメント木で実装できる。

AtCoder LibraryのLazy Segtreeの使い方 - ARMERIA

抽象化された遅延セグ木は5つの関数を定義するが、今回は以下のようになる。

関数	役割	今回の問題
e()	dataの単位元	常に $\infty$ を返す関数
id()	lazyの単位元	常に $0$ を返す関数
op(a,b)	data同士のマージ	min
mapping(f,x)	dataにlazyを反映	add
composition(f,g)	lazy同士のマージ	add

上の記事からリンクされてるチートシートに、そのものズバリな設定がある。親切。

Python3

from itertools import accumulate
from operator import add
from typing import TypeVar, Generic, Callable, List

T = TypeVar('T')
U = TypeVar('U')


class LazySegmentTreeInjectable(Generic[T, U]):
    def __init__(self,
                 n: int,
                 identity_data: Callable[[], T],
                 identity_lazy: Callable[[], U],
                 operation: Callable[[T, T], T],
                 mapping: Callable[[T, U], T],
                 composition: Callable[[U, U], U],
                 ):
        self.n = n
        self.depth = n.bit_length()
        self.offset = 1 << self.depth
        self.identity_data = identity_data
        self.identity_lazy = identity_lazy
        self.operation = operation
        self.mapping = mapping
        self.composition = composition
        self.data = [identity_data() for _ in range(self.offset << 1)]
        self.lazy = [identity_lazy() for _ in range(self.offset)]

    @classmethod
    def from_array(cls,
                   arr: List[T],
                   identity_data: Callable[[], T],
                   identity_lazy: Callable[[], U],
                   operation: Callable[[T, T], T],
                   mapping: Callable[[T, U], T],
                   composition: Callable[[U, U], U],
                   ):
        ins = cls(len(arr), identity_data, identity_lazy, operation, mapping, composition)
        ins.data[ins.offset:ins.offset + ins.n] = arr
        for i in range(ins.offset - 1, 0, -1):
            ins.update(i)
        return ins

    def push(self, i: int) -> None:
        if i < self.offset:
            data = self.data
            lazy = self.lazy
            lz = lazy[i]

            lch = i << 1
            rch = lch + 1
            data[lch] = self.mapping(data[lch], lz)
            data[rch] = self.mapping(data[rch], lz)
            if lch < self.offset:
                lazy[lch] = self.composition(lazy[lch], lz)
                lazy[rch] = self.composition(lazy[rch], lz)
            lazy[i] = self.identity_lazy()

    def update(self, i: int) -> None:
        lch = i << 1
        rch = lch + 1
        self.data[i] = self.operation(self.data[lch], self.data[rch])

    def all_apply(self, i: int, d: U) -> None:
        self.data[i] = self.mapping(self.data[i], d)
        if i < self.offset:
            self.lazy[i] = self.composition(self.lazy[i], d)

    def propagate(self, l: int, r: int) -> None:
        for i in range(self.depth, 0, -1):
            if ((l >> i) << i) != l:
                self.push(l >> i)
            if ((r >> i) << i) != r:
                self.push((r - 1) >> i)

    def range_update(self, l: int, r: int, d: U) -> None:
        l += self.offset
        r += self.offset
        self.propagate(l, r)

        l2 = l
        r2 = r
        while l < r:
            if (l & 1) == 1:
                self.all_apply(l, d)
                l += 1
            if (r & 1) == 1:
                r -= 1
                self.all_apply(r, d)
            l >>= 1
            r >>= 1
        l = l2
        r = r2

        for i in range(1, self.depth + 1):
            if ((l >> i) << i) != l:
                self.update(l >> i)
            if ((r >> i) << i) != r:
                self.update((r - 1) >> i)

    def range_query(self, l: int, r: int) -> T:
        l += self.offset
        r += self.offset

        self.propagate(l, r)
        sml = self.identity_data()
        smr = self.identity_data()
        while l < r:
            if (l & 1) == 1:
                sml = self.operation(sml, self.data[l])
                l += 1
            if (r & 1) == 1:
                r -= 1
                smr = self.operation(self.data[r], smr)
            l >>= 1
            r >>= 1
        return self.operation(sml, smr)

    def point_set(self, p: int, d: T) -> None:
        p += self.offset
        for i in range(self.depth, 0, -1):
            self.push(p >> i)
        self.data[p] = d
        for i in range(1, self.depth + 1):
            self.update(p >> i)

    def point_get(self, p: int) -> T:
        p += self.offset
        for i in range(self.depth, 0, -1):
            self.push(p >> i)
        return self.data[p]

    def debug_print(self) -> None:
        i = 1
        while i <= self.offset:
            print(*map('{: 4d}'.format, self.data[i:i * 2]))
            i <<= 1
        i = 1
        while i <= self.offset:
            print(*map('{: 4d}'.format, self.lazy[i:i * 2]))
            i <<= 1


n, q = map(int, input().split())
s = input()
aaa = [1 if c == '(' else -1 for c in s]
acc = [0] + list(accumulate(aaa))

INF = 1 << 60
identity_data = lambda: INF
identity_lazy = int
operation = min
mapping = add
composition = add

lst = LazySegmentTreeInjectable.from_array(acc, identity_data, identity_lazy, operation, mapping, composition)

for _ in range(q):
    op, l, r = map(int, input().split())
    l -= 1
    r -= 1
    if op == 1:
        if aaa[l] == aaa[r]:
            continue
        if aaa[l] == 1:
            lst.range_update(l + 1, r + 1, -2)
        else:
            lst.range_update(l + 1, r + 1, 2)
        aaa[l], aaa[r] = aaa[r], aaa[l]
    else:
        lp = lst.point_get(l)
        rp = lst.point_get(r + 1)
        range_min = lst.range_query(l + 1, r + 1)
        if lp == rp and lp <= range_min:
            print('Yes')
        else:
            print('No')

G - Vertex Deletion

問題

$N$ 頂点の木が与えられる
この木の最大マッチングの大きさを $m$ とする
以下の条件を満たす頂点 $v$ の個数を求めよ
- $v$ および $v$ を端点に持つ辺を取り除いたグラフでも、最大マッチングの大きさは $m$ のまま
$2 \le N \le 2 \times 10^5$

解法

ABCで2回連続全方位木DPが出たので、世は空前の全方位DPブーム。
（先週せっかくライブラリ化したのに、今回Fで延々とバグらせ続けていたせいで日の目を見ませんでした。悲しいね）

グラフ上から、「どの2辺も両端の頂点を共有しない」という条件で選んだ辺集合をマッチングと呼ぶ。
その中で、取れる辺数が最大であるものを最大マッチングと呼ぶ。

通常のグラフにおける最大マッチングは難しいが、二部グラフや木では効率的に解ける方法がある。
木の最大マッチングはいろいろな解き方があるが、葉から貪欲にマッチングしていく、という方法が可能。

      ○
    ／  ＼
  ○     ○
 /｜\    /\
○○○  ○○
          ｜
          ○
    ↓↓↓
      ○
    ／  ＼
  ①     ③
 /｜\    /\
①○○  ③②
          ｜
          ②

上の例の場合、最大マッチングは3だが、根の頂点自身はペアに使われずとも各子の部分木だけで完結しているので、消しても最大マッチングに影響ない。

      ②
    ／  ＼
  ①     ②
 /｜\
①○○

逆にこの例では最大マッチング達成のためには根頂点が必要で、消すことが出来ない。

従って、根を決めて、以下のような木DPを考えた場合、

$DP[v]=(c, flag)$
- 頂点 $v$ 以下の部分木で達成できるマッチングが $c$ 個
- 頂点 $v$ 自身はそのマッチングに $flag=0:使われている/1:使われていない$

$DP[根]$ の $c$ が最大マッチングと一致し、$flag=1$ なら根は消せる。$0$ なら消せないとなる。

なお、根の $c$ は最大になるに決まっているので、答えを求める上では $flag$ だけ管理すればよいが、イメージ的にわかりやすくするため $c$ を添えて考える。

$DP[v]$ の値は、$v$ の子頂点たちを先に計算しておくことで、以下で求められる。

$flag=1$ の子が1つでもある場合
- $c$ は子頂点達の合計 $+1$（$v$ と子で新規ペアが1個出来る）
- $flag$ は '0'
$flag=1$ の子が1つもない場合
- $c$ は子頂点達の合計
- $flag$ は '1'
葉は $(0,1)$

全方位DPを利用することで全頂点に対して「自身を根としたときの $DP$ の値」が $O(N)$ で求められる。

Python3

from typing import List, Callable, TypeVar, Generic
from operator import or_

T = TypeVar('T')
U = TypeVar('U')


class Rerooting(Generic[T, U]):
    """
    全方位DP

    ① __init__()に示された関数などを定義する
    ② add_edge()にてN-1本の辺を与える。必ず2回ずつ呼んで双方向で与えること。
    ③ solve()

    mergeが逆演算を持たない場合を想定し、子の左右からの累積和を記録する実装のため、
    Type:T が整数値でなくListなどのObjectの場合、リスト生成が重くてTLEするかも。

    その場しのぎ的には、Type:Tが複数の整数値であれば、bitshiftにより1つの整数にまとめるのが手っ取り早い。
    """

    class Edge:
        src: int
        tgt: int
        value: U

        def __init__(self, src, tgt, value):
            self.src = src
            self.tgt = tgt
            self.value = value

    links: List[List[Edge]]

    def __init__(self,
                 n: int,
                 leaf_factory: Callable[[], T],  # 1回目のDFSで葉に適用する値
                 unit_factory: Callable[[], T],  # 単位元
                 merge: Callable[[T, T], T],  # 演算
                 apply: Callable[[T, int, int, U], T],  # 隣接頂点の値から自身の値を算出
                 # （たとえば辺の値をXORするとか自身の頂点の値を足すとか）
                 # 隣接頂点の値, 自身の頂点, 隣接頂点, 自身→隣接 辺の値
                 ) -> None:
        self.n = n
        self.links = [[] 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(self.Edge(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['Edge'] = [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.src, e.tgt, e.value))

                    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.src, pe.tgt, pe.value)
                q.append(e.tgt)

        return ans


n = int(input())

leaf_factory = int
unit_factory = int
merge = or_
apply = lambda p, s, t, v: p ^ 1

rrt = Rerooting(n, leaf_factory, unit_factory, merge, apply)

for _ in range(n - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    rrt.add_edge(u, v, 0)
    rrt.add_edge(v, u, 0)

result = rrt.solve()
ans = n - sum(result)

print(ans)

目次

AtCoder Beginner Contest 223 F,G問題メモ

F - Parenthesis Checking

問題

解法

G - Vertex Deletion

問題

解法