ABC333(A~E)をPythonで解く

# A: Three Times

https://atcoder.jp/contests/abc333/tasks/abc333_a

数字NをN個つなげて得られる文字列を出力します。

<details><summary>コード</summary>

```python
N = int(input())
ans = ""
for i in range(N):
    ans += str(N)

print(ans)
```

</details>

# B: Pentagon 

https://atcoder.jp/contests/abc333/tasks/abc333_b

スマートな解法が思い浮かばなかったので地道に全部辺を列挙しました。
短い辺の集合にどちらも存在するかどちらも存在しないかの時だけYesです。

公式の滅茶苦茶スマートな解法は[こちら](https://atcoder.jp/contests/abc333/editorial/7985)


<details><summary>コード</summary>

```python
one = ["AB", "BC", "CD", "DE", "EA", "AE", "ED", "DC", "CB", "BA"]

S = input()
T = input()

if (S in one and T in one) or (S not in one and T not in one):
    print("Yes")
else:
    print("No")
```

</details>

# C: Repunit Trio 

https://atcoder.jp/contests/abc333/tasks/abc333_c

入力例３から、あり得る最大の答えがわかります。112222222233(12桁)以上の数を考える必要はないので、13桁のレピュニットまで(1111111111111)を考えます。

レピュニット数をすべて列挙したリストを作り、そこからあり得る和を3重ループで求めてソートすれば問題なく答えが求められます。

<details><summary>コード</summary>

```python
N = int(input())

# 13桁までのレピュニット数のリスト
rep = [int("1"*i) for i in range(1,14)]

ans = []
for i in range(len(rep)):
    for j in range(len(rep)):
        for k in range(len(rep)):
            ans.append(rep[i]+rep[j]+rep[k])

ans = sorted(list(set(ans)))
print(ans[N-1])
```

</details>

# D: Erace Leaves 

https://atcoder.jp/contests/abc333/tasks/abc333_d

頂点１を削除するためには、頂点１が葉である必要があります。従って、頂点１から出ている辺を１にまで減らします。

これは、頂点１を根とする木を一つを残して全て削除することで実現できます。

操作回数を最小にしたいので、残す木は最大のものにしたいです。

よって、頂点１を根とする木のうち最大のもの以外をすべて削除し、最後に頂点１を削除します。これは Union Findで頂点１から出ている辺以外を全て管理し、木の大きさを考えることで求められます。

（木は連結であるのでどの頂点も必ず1を根とする木の中に含めることができます。）

Union Findは[アルゴ式](https://algo-method.com/descriptions/136)に実装例が載っています。

<details><summary>コード</summary>

このUnion Findのコードはどこかから頂いたものです…(再発見できず)。

```python
from typing import List

class UnionFind:
    """0-indexed"""

    def __init__(self, n):
        self.n = n
        self.parent = [-1] * n
        self.__group_count = n

    def unite(self, x, y) -> bool:
        """xとyをマージ"""
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return False

        self.__group_count -= 1

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

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

        return True

    def is_same(self, x, y) -> bool:
        """xとyが同じ連結成分か判定"""
        return self.root(x) == self.root(y)

    def root(self, x) -> int:
        """xの根を取得"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def size(self, x) -> int:
        """xが属する連結成分のサイズを取得"""
        return -self.parent[self.root(x)]

    def all_sizes(self) -> List[int]:
        """全連結成分のサイズのリストを取得 O(N)"""
        sizes = []
        for i in range(self.n):
            size = self.parent[i]
            if size < 0:
                sizes.append(-size)
        return sizes

    def groups(self) -> List[List[int]]:
        """全連結成分の内容のリストを取得 O(N・α(N))"""
        groups = dict()
        for i in range(self.n):
            p = self.root(i)
            if not groups.get(p):
                groups[p] = []
            groups[p].append(i)
        return list(groups.values())

    @property
    def group_count(self) -> int:
        """連結成分の数を取得 O(1)"""
        return self.__group_count

```

```python
def main():
    N = int(input())
    uf = UnionFind(N)
    for _ in range(N-1):
        u, v = map(int, input().split())
        # １から出ている辺は無視する
        if u==1 or v==1:
            continue
        uf.unite(u-1,v-1)
    
    # 最大の木を除いたすべての頂点を削除する
    print(sum(uf.all_sizes())-max(uf.all_sizes()))

main()
```

</details>


# E: Takahashi Quest 

https://atcoder.jp/contests/abc333/tasks/abc333_e

[kyopuro_friendsさんのユーザー解説](https://atcoder.jp/contests/abc333/editorial/7981)にもあるように、後ろから「必要なポーションの種類と数」を辞書で管理します。

まずは、必要ポーションの数と種類を表す辞書`portion`と、その時に所持しているポーションの数を表す変数`num`、ポーションを拾ったかを記録するリスト`actions`を用意します。

ポーションを見つけた時(t=1)、まずはそのポーションが必要かどうか確認します。これは`portion[x]`が1以上であるかどうかで判断できます。

もしポーションが必要であれば、そのポーションを拾って使います。これにより、この先必要なポーションが1つ減り、所持しているポーションも一つ減ります。

もしポーションが必要でないなら、拾わなくていいです。

これは下記のコードで実装できます。

```python
if t==1:
    if portion[x] > 0:
        portion[x] -= 1
        num -= 1
        actions.append(1)
    else:
        actions.append(0)
```

モンスターと出会った時(t=2)、対応したポーションが必要なのでそれを必要ポーションに加えます。さらに所持ポーションが増えるので、最大ポーション所持数も更新しておきます。

```python
if t==2:
    portion[x] += 1
    num += 1
    k = max(k, num)
```

最後に、必要ポーションが全て０になっていることを確認してモンスター撃退完了の確認をします。

必要なポーションが残っているのに拾えていない場合は対応するモンスターが撃退できないので`-1`を出力します。

```python
if sum(portion.values()) == 0:
    print(k)
    print(*reversed(actions))
else:
    print(-1)
```

まとめたコードがこちら

<details><summary>コード</summary>

```python
from collections import defaultdict 

N = int(input())
TX = reversed([list(map(int, input().split())) for _ in range(N)])
portion = defaultdict(int)
k = 0
num = 0
actions = []

for t, x in TX:
    if t == 1:
        if portion[x] > 0:
            portion[x] -= 1
            num -= 1
            actions.append(1)
        else:
            actions.append(0)
    else:
        portion[x] += 1
        num += 1
        k = max(k, num)

if sum(portion.values()) == 0:
    print(k)
    print(*reversed(actions))
else:
    print(-1)
        
```

</details>