AtCoder ABC177 A-Dをpythonで

AtCoder ABC177 A-D問題までpythonで解いてみた.

AtCoder ABC177に参加したのでその記録として投稿しようと思います.

A問題

高橋君は青木君と待ち合わせをしています。
待ち合わせ場所は高橋君の家からDメートル離れた地点であり、待ち合わせの時刻はT分後です。
高橋君は今から家を出発し、分速Sメートルで待ち合わせ場所までまっすぐ移動します。
待ち合わせに間に合うでしょうか？

考えたこと

分速Sメートルで移動できる高橋君がT分で移動できる最大距離はS*Tです.
この値とDを比較すれば良いです.(不等号を間違えて1WA出しました())

d, t, s = map(int, input().split())
if s*t >= d:
    print("Yes")
else:
    print("No")

B問題

2つの文字列S,Tが与えられます。TがSの部分文字列となるように、Sのいくつかの文字を書き換えます。
少なくとも何文字書き換える必要がありますか？

考えたこと

len(S)>=len(T)より文字列TをSの中で動かしていき,その一致した最大文字数だけlen(T)から引いた値が答えとなります.

s = input()
t = input()
sl = len(s)
tl = len(t)

cnt = 0
ans = 0

for i in range(sl-tl+1):
    for j in range(tl):
        if t[j] == s[i+j]:
            cnt += 1

    ans = max(cnt, ans)#ans:一致した文字数の最大値
    cnt = 0

print(tl - ans)

C問題

N個の整数A1,…,ANが与えられます。1≤i<j≤Nを満たす全ての組(i,j)についての Ai×Ajの和を mod(10**9+7)で求めてください。

考えたこと

愚直にfor文を二重で回すとO(N^2)よりTLEになってしまう...
とりあえず書き出してみると以下のことが分かった.
ex.i=1, 2,...の時を考える.
sum = A1+A2+...ANとする.
i=1の時
A1 x A2 + A1 x A3 + A1 x A4 + ・・・・ + A1 x AN
= A1 x (sum - A1)
i=2の時
A2 x A3 + A2 x A4 + A2 x A5 + ・・・・ + A2 x AN
= A2 x (sum - A1 - A2)
これならばO(N)で抑えられる.
これをPythonで実装すると,

n = int(input())
A = [0]+list(map(int, input().split()))
mod = 10**9 + 7
S = sum(A)
ans = 0

for i in range(1, n):
    ans += A[i]*(S-A[i])
    ans %= mod
    S -= A[i]

print(ans)

D問題

人1から人NまでのN人の人がいます。「人Aiと人Biは友達である」という情報がM個与えられます。同じ情報が複数回与えられることもあります。
XとYが友達、かつ、YとZが友達ならば、XとZも友達です。また、M個の情報から導くことができない友達関係は存在しません。
悪の高橋君は、このN人をいくつかのグループに分け、全ての人について「同じグループの中に友達がいない」という状況を作ろうとしています。
最小でいくつのグループに分ければ良いでしょうか？

考えたこと

UnionFindTreeで最大の集合の要素数を答えれば良いです.
最大の集合を分解しその１つ１つの要素にその他の集合の要素を割り振れば良いからです.
UnionFindTreeの解説はYoutubeでかつっぱさんの動画をみれば理解できると思います.
'Friend'という文字列が入った問題はUnionFind使いがちらしいです()

import sys
sys.setrecursionlimit(10 ** 9)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rank = [0]*(n+1)

    def find(self, x):#親となる要素を探索
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])#再帰
            return self.root[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        elif self.rank[x] > self.rank[y]:#深い木に連結
            self.root[x] += self.root[y]
            self.root[y] = x#yの親をxとする

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def issame(self, x, y):#x, yが同じ集合か判定
            return self.find(x) == self.find(y)


    def count(self, x):#要素の個数
        return (-1)*self.root[self.find(x)]

n, m = map(int, input().split())
uf = UnionFind(n)

for i in range(m):
    a, b = map(int, input().split())
    uf.unite(a, b)

ans = 0

for i in range(n):
    ans = max(ans, uf.count(i))

print(ans)