ABC401をPythonで（A～E）

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

https://atcoder.jp/contests/abc401



# A問題
https://atcoder.jp/contests/abc401/tasks/abc401_a

200以上300未満の時にSuccessを出力する
```python:A
print("Success"if 200<=int(input())<300 else"Failure")
```

# B問題
https://atcoder.jp/contests/abc401/tasks/abc401_b

login状態をフラグで保持してprivateに入ったかカウントする
```python: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問題
https://atcoder.jp/contests/abc401/tasks/abc401_c

区間の合計を別途保持して計算していく
```python: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問題
https://atcoder.jp/contests/abc401/tasks/abc401_d

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

```python: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問題
https://atcoder.jp/contests/abc401/tasks/abc401_e

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

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

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

```python: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)
```