ABC329をPythonで（A~F）

Ｓｋｙ株式会社プログラミングコンテスト2023（AtCoder Beginner Contest 329）

A問題

pythonのzipを使う

A

print(*[s for s in input()])

B問題

setに入れて2番目に大きいのを取る

B

input()
a = set(map(int, input().split()))
print(sorted(a)[-2])

C問題

各文字について一番長いのが何文字か数えて、その総和をとる

C

n = int(input())
s = input()

d = dict()
last = [0, 0]
for s_i in s:
    if last[0] == s_i:
        last[1] += 1
    else:
        last = [s_i, 1]

    if last[0] not in d:
        d[last[0]] = last[1]
    else:
        d[last[0]] = max(d[last[0]], last[1])

print(sum(val for val in d.values()))

D問題

セグ木を使ってごり押した。

D

class SegTree:
    # single update & range get
    def __init__(self,n , ide_ele, seg_func):
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        self.seg_func = seg_func

    def init_value(self, values):
        for i in range(n):
            self.tree[self.num + i] = values[i]
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.seg_func(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.seg_func(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [L, r)のsegfuncしたものを得る
        L: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.seg_func(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.seg_func(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


n, m = map(int, input().split())
Tree = SegTree(n + 1, [0, 0], max)
Tree.init_value([[-1, 0]] + [[0, -i] for i in range(1, n + 1)])
A = [0] * (n + 1)
for a_i in list(map(int, input().split())):
    A[a_i] += 1
    Tree.update(a_i, [A[a_i], -a_i])
    x = Tree.query(1, n + 1)
    print(-x[1])

E問題

解説AC

E

n, m = map(int, input().split())
s = list(input())
t = list(input())

stack = [i for i in range(n - m + 1)]
check = [False] * n
while stack:
    new_stack = set()
    for i in stack:
        flag = True
        for j in range(m):
            if t[j] != s[i + j] != "#":
                flag = False
        if flag:
            check[i] = True
            for j in range(m):
                s[i + j] = "#"

            for j in range(1, m):
                if 0 <= i - j <= n - m and not check[i - j]:
                    new_stack.add(i - j)
                if 0 <= i + j <= n - m and not check[i + j]:
                    new_stack.add(i + j)

    stack = list(new_stack)

print("Yes" if s == ["#"] * n else "No")

F問題

解説AC

F

n, q = map(int, input().split())
c = []
for c_i in list(map(int, input().split())):
    c.append({c_i})

for _ in range(q):
    a, b = map(lambda x:int(x) - 1, input().split())
    if c[a] and c[b]:
        if len(c[a]) < len(c[b]):
            c[b] |= c[a]
            c[a] = {}
        else:
            c[a] |= c[b]
            c[b] = {}
            c[a], c[b] = c[b], c[a]
    elif c[a]:
        c[a], c[b] = c[b], c[a]

    print(len(c[b]))