AtCoder Beginner Contest 177の感想

AtCoder

2020.08.302020.09.10

ABC177に参加した。

AtCoder Beginner Contest 177 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A – Don’t be late

やるだけ。

d, t, s = map(int, input().split())

if d / s <= t:
    print('Yes')
else:
    print('No')

B – Substring

部分文字列を全列挙し、列挙した部分文字列を1文字ずつ比較していく。

s = input()
t = input()

ans = 100000

n = len(s)
m = len(t)

for i in range(n - m + 1):
    temp = s[i:i + m]
    count = 0
    for a, b in zip(temp, t):
        if a != b:
            count += 1
    ans = min(count, ans)

print(ans)

C – Sum of product of pairs

例えばA1, A2, A3, A4が与えられた時、求める答えは

A1xA2 + A1xA3 + A1xA4 + A2xA3 + A2xA4 + A3xA4

= A1 ( A2+A3+A4 ) + A2 ( A3 + A4 ) + A3xA4

と式変形できる。

括弧の部分は累積和でO(n)であらかじめ計算しておけば、足し込んでいく処理もO(n)で実行できる。

n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

cumsum = [0] * n
cumsum[0] = a[0]
for i in range(1, n):
    cumsum[i] = cumsum[i - 1] + a[i]

ans = 0
for i in range(n):
    ans += a[i] * (cumsum[-1] - cumsum[i]) % mod

print(ans % mod)

D – Friends

本番中は幅優先探索で考えていたがWA。

解説放送でUnionFindというのを初めて知り、やりたいことが簡単に出来てしまった。

素集合のデータ構造の代表例らしい。

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]


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

    def find(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return
        elif self.rank[x] > self.rank[y]:
            self.parent[x] += self.parent[y]
            self.parent[y] = x
        else:
            self.parent[y] += self.parent[x]
            self.parent[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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

    def count(self, x):
        return -self.parent[self.find(x)]


uf = UnionFind(n)

for a, b in ab:
    uf.union(a, b)

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

print(ans)

もうちょっとでHighest更新できそう。