ABC372をPythonで（A～E）

ユニークビジョンプログラミングコンテスト2024 秋（AtCoder Beginner Contest 372）の解答等の速報的まとめ

A問題

言語仕様に頼る

A

print(input().replace(".", ""))

B問題

$3^n$を用意して大きいほうから引いてうまいことやる

B

m = int(input())

lst = [1]
while lst[-1] <= m:
    lst.append(lst[-1] * 3)

ans = []
i = len(lst) - 1
while m > 0:
    while m < lst[i]:
        i -= 1
    ans.append(i)
    m -= lst[i]

print(len(ans))
print(*ans)

C問題

変更を加える箇所でABCが減ったら$-1$、増えたら$+1$する

C

n, q = map(int, input().split())
s = list(input())
ABC = ["A", "B", "C"]
cnt = 0
for i in range(n):
    if i - 1 >= 0 and i + 1 < n and s[i - 1:i + 2] == ABC:
        cnt += 1

for _ in range(q):
    X, c = input().split()
    x = int(X) - 1
    if s[x-2:x+1] == ABC or s[x - 1:x + 2] == ABC or s[x:x + 3] == ABC:
        cnt -= 1
    s[x] = c
    if s[x-2:x+1] == ABC or s[x - 1:x + 2] == ABC or s[x:x + 3] == ABC:
        cnt += 1

    print(cnt)

D問題

$j$を基準にどこまで$i$を前にやれるかを考える

D

n = int(input())
h = list(map(int, input().split()))

stack = []
ans = [0] * n
for i in range(n - 1, -1, -1):
    ans[i] = len(stack)
    while stack and stack[-1] < h[i]:
        stack.pop()
    stack.append(h[i])

print(*ans)

E問題

UnionFindしながら配列結合する
Kが最大10なので結合する配列の長さを10までにすれば間に合う

E

import sys;sys.setrecursionlimit(10 ** 7)

def merge(x, y):
    global lst
    new = []
    i = j = 0
    if len(lst[x]) == 0:
        return lst[y]
    if len(lst[y]) == 0:
        return lst[x]

    while i < len(lst[x]) and j < len(lst[y]) and len(new) < 10:
        if lst[x][i] > lst[y][j]:
            new.append(lst[x][i])
            i += 1
        else:
            new.append(lst[y][j])
            j += 1

    while i < len(lst[x]) and len(new) < 10:
        new.append(lst[x][i])
        i += 1
    while j < len(lst[y]) and len(new) < 10:
        new.append(lst[y][j])
        j += 1

    return new

def find(x):
    global parent
    if parent[x] < 0:
        return x
    else:
        parent[x] = find(parent[x])
        return parent[x]

def union(x, y):
    global parent, lst
    px = find(x)
    py = find(y)
    if px == py:
        return
    if parent[px] > parent[py]:
        px, py = py, px

    parent[px] += parent[py]
    parent[py] = px
    lst[px] = merge(px, py)


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

parent = [-1] * n
lst = [[i + 1] for i in range(n)]
for _ in range(q):
    com, a, b = map(lambda x:int(x) - 1, input().split())
    if com == 0:
        union(a, b)
    else:
        i = find(a)
        print(-1 if len(lst[i]) <= b else lst[i][b])