LoginSignup
1
1

ABC328をPythonで(A~F)

Posted at

トヨタ自動車プログラミングコンテスト2023#7(AtCoder Beginner Contest 328)

A問題

問題文の通りにやる。

A
n, x = map(int, input().split())
a = list(map(int, input().split()))
print(sum(a_i for a_i in a if a_i <= x))

B問題

全部調べる。

B
n = int(input())
d = list(map(int, input().split()))
ans = 0
for i, d_i in enumerate(d, 1):
    for j in range(1, d_i + 1):
        if len(set(list(str(i) + str(j)))) == 1:
            ans += 1

print(ans)

C問題

i番目までに連続しているところがいくつあるか事前に数える。

C
n, q = map(int, input().split())
s = input()

d = [0] * n
for i in range(1, n):
    d[i] += d[i - 1]
    if s[i] == s[i - 1]:
        d[i] += 1

for _ in range(q):
    l, r = map(int, input().split())
    print(d[r - 1] - d[l - 1])

D問題

先頭から貪欲にやっていく。

D
s = input()

ans = []
for s_i in s:
    ans.append(s_i)
    if len(ans) >= 3 and ans[-3:] == ["A", "B", "C"]:
        ans.pop();ans.pop();ans.pop()

print("".join(ans))

E問題

辺を$n-1$本選んですべて連結するか確認。
その中で最小のものを出力。

E
from itertools import combinations
from collections import defaultdict

class UnionFind:
    """
    URL : https://note.nkmk.me/python-union-find/
    """
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())


n, m, k = map(int, input().split())
data = []
for _ in range(m):
    u, v, w = map(int, input().split())
    data.append((u - 1, v - 1, w))

ans = float("inf")
for c in combinations(range(m), n - 1):
    UF = UnionFind(n)
    ans_i = 0
    for c_i in c:
        u, v, w = data[c_i]
        UF.union(u, v)
        ans_i = (ans_i + w) % k
    
    if UF.group_count() == 1:
        ans = min(ans, ans_i)

print(ans)

F問題

重み付きUnionFindで順にやっていくだけ。

F
class WeightedUnionFind:
    """
    URL:https://at274.hatenablog.com/entry/2018/02/03/140504#%E5%AE%8C%E6%88%90%E5%BD%A2
    """
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 根への距離を管理
        self.weight = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    # 併合
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]


n, q = map(int, input().split())
ans = []
UF = WeightedUnionFind(n + 10)
for i in range(1, q + 1):
    a, b, d = map(int, input().split())
    if UF.same(a, b) and UF.diff(a, b) != d:
        continue
    else:
        ans.append(i)
        UF.union(a, b, d)

print(*ans)
1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
1