BETA

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

投稿日:2020-09-28
最終更新:2020-09-28

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$を出力すればおk
自作の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]))で更新してけばおk
普通にやると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

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

参考資料

技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
駆け出しエンジニアからエキスパートまで全ての方々のアウトプットを歓迎しております!
or 外部アカウントで 登録 / ログイン する
クランチについてもっと詳しく

この記事が掲載されているブログ

AtCoderで競プロはじめました その記録をつけていく予定です

よく一緒に読まれる記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう