Zenn
🎮

[AtCoder]ABL個人的メモ[Python]

2020/09/29に公開
Python
競技プログラミング
AtCoder
tech

ABL

所感

A,B,Cの3完の581パフォ
前回が良かっただけに残念だった
segment-treeが重要らしい

A - Repeat ACL

やるだけ

#!/usr/bin/env python3
def main():
    print('ACL' * int(input()))


if __name__ == '__main__':
    main()

B - Integer Preference

解説放送の図が分かりやすい

#!/usr/bin/env python3
def main():
    A, B, C, D = map(int, input().split())

    if A <= C <= B or C <= A <= D:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()

C - Connect Cities

union-findで(rootの数)-1を出力すればおｋ
自作のunion-findがバグってて肝が冷えました
ACLだとDSUって名前みたい
でもtwitterを見る限り，英語名がDSUってわけでもない？
良く分からんがとりあえず名前はunionfindで良いと思われる

提出コード
#!/usr/bin/env python3
class UnionFind:
    """Union-Find(素集合データ構造)"""
    def __init__(self, n: int):
        """
        Constructer(Initialize parameter in this class)

        Parameters
        ----------
        n : int
            Number of node

        Yields
        -----
        root : list
            When value is postive, express root of the node.
            When it is negative, express this node is root and size of set.
        """

        self.root = [-1] * n

    def find(self, x: int):
        """
        Search root of node x

        Parameters
        ----------
        x : int
            node x

        Returns
        -------
        x : int
            Root of node x
        """

        if self.root[x] < 0:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]

    def unite(self, x: int, y: int):
        """
        Unite two set including node x and node y into one set.

        Parameters
        ----------
        x, y : int
            Node number

        Returns
        -------
        unite_result : bool
            False : Already two node include same set.
            True  : United
        """

        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.root[x] > self.root[y]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x
        return True

    def same(self, x: int, y: int):
        """
        Determine if x and y are in same set.

        Parameters
        ----------
        x, y : int
            Node number

        Returns
        -------
        result : bool
            Determining result
        """

        return self.find(x) == self.find(y)

    def size(self, x: int) -> bool:
        """
        Return size of set including node x.

        Parameters
        ----------
        x : int
            Node number

        Returns
        -------
        Size of set : int
        """

        return self.root[self.find(x)] * -1


def main():
    N, M = map(int, input().split())

    lst = UnionFind(N)
    for _ in range(M):
        a, b = map(int, input().split())
        lst.unite(a - 1, b - 1)

    ans = -1
    for i in lst.root:
        if i < 0:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

D - Flat Subsequence

dpかな~と思ったけど，どんなdpでやれば良いか分からなかった
edpcやるといいらしい
dp[i][j]でi個目までの数で，最後に選んだ値がjの時の部分列の最大長
このままだとdpの項が10^{5 \times 2}個でMLEするので効率化が必要
dpのiは省略してdp[j]とし，chmax(dp[Ai], max(dp[Ai - K:Ai + K + 1]))で更新してけばおｋ
普通にやるとTLEするので，segtreeで更新時の計算量を効率化
これで全体の計算量はO(N\log N)となる
N_{max}=3 \times 10 ^ 5だからO(10^6)なので何とか間に合いそう？
pypyでac, pythonでtleでした
蟻本にsegtreeの項目有

提出コード
#!/usr/bin/env python3
class segtree:
    """
    segment tree
    value store as object type and get update function(merge_func) from outside

    Attributes
    ----------
    n : int
        Number of elements
    initialize_func : func
        function for initialization
    merge_func : func
        function for merge x and y to x(this merge is distruction update)

    Methods
    -------
    update(i, x)
        update tree[i] value to x
    get(a, b)
        get value from [a, b)
        include a but not include b, return a merged value
    """
    def __init__(self, n, initialize_func, merge_func):
        """
        Constructer(Initialize parameter in this class)

        Parameters
        ----------
        n : int
            Number of elements
        initialize_func : func
            function for initialization
        merge_func : func
            function for merge x and y to x(this merge is distruction update)
        """
        self.n = n
        self.initialize = initialize_func
        self.merge = merge_func
        n2 = 1  # n2はnより大きい2の冪数
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [initialize_func() for _ in range(n2 << 1)]

    def update(self, index, x):
        index += self.n2
        self.tree[index] = self.merge(self.tree[index], x)
        while index > 1:
            # (index ^ 1) はiと1の排他的論理和(XOR)
            x = self.merge(x, self.tree[index ^ 1])
            index >>= 1  # 右ビットシフトで親ノードのインデックスへ移動
            self.tree[index] = self.merge(self.tree[index], x)

    def get(self, a, b):
        result = self.initialize()
        q = [(1, 0, self.n2)]
        while q:
            k, left, right = q.pop()
            if a <= left and right <= b:
                result = self.merge(result, self.tree[k])
                continue
            m = (left + right) // 2
            k <<= 1
            if a < m and left < b:
                q.append((k, left, m))
            if a < right and left < m:
                q.append((k + 1, m, right))
        return result


def main():
    N, K = map(int, input().split())
    A = [int(input()) for _ in range(N)]
    max_A = 3 * 10 ** 5 + 1

    seg = segtree(max_A, lambda: 0, max)
    for a in A:
        next = seg.get(max(0, a - K), min(a + K + 1, max_A))
        seg.update(a, next + 1)
    print(seg.get(0, max_A))


if __name__ == '__main__':
    main()

E - Replace Digits

遅延セグ木？とかいうの使うらしい

参考資料

Discussion