BETA

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

投稿日:2020-08-31
最終更新:2020-08-31

ABC177

初4完

ABC177 A - Don't be late

$\dfrac{D}{S}\leqq{T}$ならYes,そうじゃないならNO
しかし,int型同士の割り算はfloat型となる
この時に誤差が発生し得るので,float型は避けるのが無難
なので,判定式を$D\leqq TS$とする
こうすればint型のみでの計算となるのでfloat型による誤差が生じない
計算量は$O(1)$

#!/usr/bin/env python3  
def main():  
    D, T, S = map(int, input().split())  
    print('Yes' if S * T >= D else 'No')  


if __name__ == '__main__':  
    main()  

ABC177 B - Substring

全探索
Tの先頭文字とSの先頭文字が一致する状態から,Tを1文字ずつ右に動かしていき,Tの最後部とSの最後部が一致するまで動かす
各状態でSとTの違う文字を数えて,全パターンを通じてのその値の最小値が答え
このとき,全パターン数は$len(S)-len(T)+1$
計算量は$O(|S||T|)$

#!/usr/bin/env python3  
def main():  
    S = input()  
    T = input()  

    ans = 10 ** 6  
    for i in range(len(S) - len(T) + 1):  
        cnt = 0  
        for j in range(len(T)):  
            if S[i + j] != T[j]:  
                cnt += 1  
        ans = min(ans, cnt)  
    print(ans)  


if __name__ == '__main__':  
    main()  

ABC177 C - Sum of product of pairs

全探索すると$O(N^2)$で$2\leqq N\leqq 2\times 10^5$だから,$O(10^{10})$となりTLE
求める式は以下の様に表される
$$\sum_{i=1}^{N-1} \sum_{j=i+1}^{N}A_iA_j$$
よって累積和を用いれば$O(N)$で解ける
解説によれば,図形を基にして考えても解けるらしい
python3.8以上ではaの逆元のmodがpow(a, -1, mod)で計算できるし,その方が速いらしい

# 累積和  
#!/usr/bin/env python3  
def main():  
    _ = int(input())  
    A = [int(x) for x in input().split()]  
    mod = 10 ** 9 + 7  

    lst = [sum(A)]  
    for j in A:  
        lst.append(lst[-1] - j)  
    ans = 0  
    for index, i in enumerate(A):  
        ans += i * lst[index + 1] % mod  
    print(ans % mod)  


if __name__ == '__main__':  
    main()  
# 図形を基にした解法  
#!/usr/bin/env python3  
def main():  
    _ = int(input())  
    A = [int(x) for x in input().split()]  
    mod = 10 ** 9 + 7  

    square_S = sum(A) ** 2 % mod  
    diagonal = sum([x ** 2 % mod for x in A]) % mod  
    #  By the Fermat's little theorem  
    print(((square_S - diagonal) % mod * pow(2, mod - 2, mod)) % mod)  


if __name__ == '__main__':  
    main()  

ABC177 D - Friends

最大のグループを1人ずつ別のグループにした時のグループ数が,条件を満たす最小のグループ数となる
よって,最大グループの構成人数を求めればおk
Union-Findすればおk
コンテスト中はUnion-Find未履修だったのでBFSで解いた

# Union-Find  
#!/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 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())  
    uf = unionfind(N)  
    for _ in range(M):  
        a, b = map(int, input().split())  
        uf.unite(a - 1, b - 1)  

    ans = 0  
    for i in range(N):  
        ans = max(ans, uf.size(i))  
    print(ans)  


if __name__ == '__main__':  
    main()  
# BFS  
#!/usr/bin/env python3  
def main():  
    from collections import deque  

    N, M = map(int, input().split())  
    friends_input = [set() for _ in range(N)]  
    for _ in range(M):  
        a, b = map(int, input().split())  
        friends_input[a - 1].add(b - 1)  
        friends_input[b - 1].add(a - 1)  

    seen = [False] * N  
    friends_group = []  
    for i in range(N):  
        if seen[i]:  
            continue  
        q = deque([i])  
        tmp_group = set([i])  
        while q:  
            now = q.popleft()  
            if seen[now]:  
                continue  
            seen[now] = True  
            for j in friends_input[now]:  
                if not seen[j]:  
                    q.append(j)  
                    tmp_group.add(j)  
        friends_group.append(tmp_group)  
    ans = 0  
    for i in friends_group:  
        ans = max(ans, len(i))  
    print(ans)  


if __name__ == '__main__':  
    main()  

ABC177 E - Coprime

wa
pairwise coprimeを制限時間内に解く方法が分からなかった
pairwiseの判定 -> setwiseの判定の順に行なう

pairwiseの判定は,2つの整数が互いに素なら成立
つまり,同じ素因数が含まれているAが2つ以上あったら不成立
これを調べるのにエラトステネスの篩を使う
篩に掛けるときに2つ以上の数が落とされた場合,pairwise不成立と分かる

setwiseの判定は,標準ライブラリのgcdを使えばおk

互いに素の事を英語でcoprimeって言うらしい
標準ライブラリに最大公約数求めるGCDあるの知らなかった

#!/usr/bin/env python3  
def main():  
    from math import gcd  

    N = int(input())  
    A = []  
    Constraints_val_A = 10 ** 6 + 5  
    A_duplication = [0] * Constraints_val_A  
    for a in [int(x) for x in input().split()]:  
        A.append(a)  
        A_duplication[a] += 1  

    pairwise = True  
    for i in range(2, Constraints_val_A):  
        cnt = 0  
        for j in range(i, Constraints_val_A, i):  
            cnt += A_duplication[j]  
        if cnt > 1:  
            pairwise = False  
    if pairwise:  
        print("pairwise coprime")  
        return  

    g = 0  
    for i in range(N):  
        g = gcd(g, A[i])  
        if g == 1:  
            print('setwise coprime')  
            return  

    print('not coprime')  


if __name__ == '__main__':  
    main()  

参考資料

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

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

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

よく一緒に読まれる記事

0件のコメント

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