ABC401をPythonで（A～E）

AtCoder Beginner Contest 401の解答等の速報的まとめ

A問題

200以上300未満の時にSuccessを出力する

A

print("Success"if 200<=int(input())<300 else"Failure")

B問題

login状態をフラグで保持してprivateに入ったかカウントする

B

cnt = 0
is_login = False
for _ in range(int(input())):
    match input():
        case "login":
            is_login = True
        case "logout":
            is_login = False
        case "public":
            pass
        case "private":
            if not is_login:
                cnt += 1

print(cnt)

C問題

区間の合計を別途保持して計算していく

C

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

mod = 10 ** 9
a = list()
sums = 0
for i in range(n + 1):
    if i < k:
        a.append(1)
        sums += 1
    else:
        a.append(sums)
        sums += a[-1]
        sums -= a[i - k]
        sums %= mod

print(a[-1])

D問題

最初にoの隣にある？を.に変換する
そのあと、

1. Sに入っているoの個数が k と一致したら、?はすべて.になる
2. 連続する？の個数を2で割り端数を切り上げた和とoの個数が k と一致したら、？が奇数個連続する箇所がo.が交互に置かれる

D

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

for i, s_i in enumerate(s):
    if s_i == "?" and ((0 <= i - 1 and s[i - 1] == "o") or (i + 1 < n and s[i + 1] == "o")):
        s[i] = "."

o_count = s.count("o")

q = [[0, n]]
for i, s_i in enumerate(s):
    if s_i == "?":
        q[-1][0] += 1
        q[-1][1] = min(q[-1][1], i)
    else:
        if q[-1][0] > 0:
            q.append([0, n])

if o_count == k:
    for i in range(n):
        if s[i] == "?":
            s[i] = "."
elif sum((q_i[0] + 1) // 2 for q_i in q) + o_count == k:
    for cnt, ind in q:
        if cnt % 2 == 1:
            for i in range(ind, ind + cnt):
                if (i - ind) % 2 == 0:
                    s[i] = "o"
                else:
                    s[i] = "."

print(*s, sep="")

E問題

$k=i$のとき

• $i$以下の頂点はすべて連結である
• $i$より大きい頂点で$i$以下との辺があるものは削除対象である

したがって、$i$において

• 1と未連結の頂点をスタックに入れ、$i$と$i$未満をつなげた後でスタック内の頂点がつながっているか調べる
• $i+1$以上で辺があるものをセットに入れる

これでスタックに入っている頂点がないときはセット内の要素数、あるときは$-1$を出力する

E

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 same(self, x, y):
        return self.find(x) == self.find(y)


n, m = map(int, input().split())
edge = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(lambda x:int(x) - 1, input().split())
    edge[u].append(v)
    edge[v].append(u)

flag = True
s = set()
need_connect = list()
UF = UnionFind(n)
for i in range(n):
    s.discard(i)
    need_connect.append(i)
    for v_i in edge[i]:
        if i < v_i:
            s.add(v_i)
        else:
            UF.union(i, v_i)

    while need_connect and UF.same(0, need_connect[-1]):
        need_connect.pop()

    print(len(s) if len(need_connect) == 0 else -1)