ABC333の解説記事 (PyPy3 ABCD)

# はじめに
問題は[こちら](https://atcoder.jp/contests/abc333/tasks)
初心者（灰色〜茶色）向けです。
# A - Three Threes
https://atcoder.jp/contests/abc333/tasks/abc333_a
## 考え方
Pythonは同じ文字列の任意回数の繰り返しは文字列×文字数　で書けるので、
str(n) * n などと書けば良いです。（入力をintで受け取った場合）
## 解答例
```Python3:私の解答
n = int(input())
print(str(n)*n)
```
# B - Pentagon
https://atcoder.jp/contests/abc333/tasks/abc333_b
## 考え方
正五角形の対角線は全て同じ長さで、辺より必ず長いですから、
1. 二つの線分が共に辺、もしくは 共に対角線　であれば、「Yes」
1. 二つの線分の一方が辺、もう一方が対角線であれば、「No」

と考えます。
五角形の辺は5つしかないため、頂点の順番を考慮しても辺である文字列は10個です。
また、正五角形ABCDEの頂点が隣り合っている時が辺で、そうでない時は対角線ですから、この列挙は簡単です。
## 解答例
```Python3:私の解答
s = input()
t = input()
len1s = {'AB','BC', 'CD', 'DE', 'EA',\
         'BA','CB', 'DC', 'ED', 'AE'}
print('Yes' if ((s in len1s) and (t in len1s)) or ((s not in len1s) and (t not in len1s)) else 'No')
```
解答例はもう少し賢くやっています。
1つ目の解説では、2つの線分をアルファベットの若い順に並べ変えて、文字が連続しているか、もしくは'AE'のパターンかであれば、辺、そうでなければ対角線と判定しています。
2つ目の解説では、辺となりうる文字列を結合(時計回りの'ABCDEA'と反時計回り'AEDCBA'とを結合して'A'を削除するイメージ)して、SとTがその部分文字列であれば、辺、そうでなければ対角線と判定しています。

https://atcoder.jp/contests/abc333/editorial/7985

https://atcoder.jp/contests/abc333/editorial/7978

# C - Repunit Trio
https://atcoder.jp/contests/abc333/tasks/abc333_c
## 考え方
Nは最大333までしかないので、全て列挙して答えを出せば良いです。
また、この問題では、使用する最大のレピュニットは、「111111111111」（1が12こ続く）まであれば十分です。
実際、$K$種類のレピュニットを使った3つの和のパターン数は
1. 1種類のみを使うパターン：　$K$個
1. 2種類のみを使うパターン：　$K(K-1)$個
1. 3種類のみを使うパターン：　$K(K-1)(K-2)/6$個

であり、これらを全て足すと、$K(K+1)(K+2)/6個$です。
ですから、K種類ある時の和のパターン数は

|K|1|2|3|4|5|6|7|8|9|10|11|12|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|パターン数|1|4|10|20|35|56|84|120|165|220|286|364|

です。
なお、13番目に大きいレピュニットを使うことはありません。
なぜなら、異なるレピュニット$A,B,C$ ($A \leq B \leq C$)に対し、$A, B, C$を使った最も大きな和は$C+C+C$で、$C \leq D$となる$D$を使った最小の和は$D+A+A$ですが、$D+A+A$は$C+C+C$と比べて、少なくとも桁が一つ以上大きいです。
例えば、$A=1, B=11, C=111, D=1111$とすれば、
$C+C+C = 333 $
$D+A+A=1112$
となります。ｆ
## 解答例
```Python3:私の解答
repunits = []
tmp = 1
for _ in range(12) :
    repunits.append(tmp)
    tmp = tmp*10 + 1
trios = set()
for r1 in repunits :
    for r2 in repunits :
        for r3 in repunits :
            trios.add(r1+r2+r3)
print(sorted(list(trios))[int(input())-1])
```

# D - Erase Leaves
https://atcoder.jp/contests/abc333/tasks/abc333_d
## 考え方
「1」を削除するためには、「1」を葉にする必要があります。
「1」を葉にするためには、「1」と繋がっているノードの数が1つになるように「1」に繋がるノードを削除する必要があります。
そのため、最小になるのは、「1」に繋がるノードを削除するのが一番大変なノード以外を削除して、「1」を削除するときです。
よって、「1」に繋がるノードで一番削除に必要な枚数が多いものを考えます。
ここで、「1」に繋がるノード「X」を削除するには、「X」と「1」を切り離した、「X」側のノードのうち、「X」以外を全て削除する必要があります。
そのため、「1」と「X」を切り離したときの「X」を含む連結成分の数を数えればよい、ということになります。
これは、DFSで解けます。また、連結成分をグループに分けるので、UnionFind木でも解けます。
解答例では、timesで各ノードを削除するための最低枚数を保持しています。
-1が未設定で、0が設定中、それ以外の正の値が最低枚数　になっています。（「1」のノードは設定中としています。）
## 解答例
```Python3:私の解答
import sys
sys.setrecursionlimit(10**8)
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n-1) :
    u, v = map(int, input().split())
    graph[u-1].append(v-1)
    graph[v-1].append(u-1)
times = [-1]*n
times[0] = 0
def dfs(x) :
    tmp = 1
    for u in graph[x] :
        if times[u] == -1 and len(graph[u]) == 1 :
            times[u] = 1
        elif times[u] == -1 :
            times[u] = 0
            dfs(u)
        tmp += times[u]
    times[x] = tmp
maxB = 1
for i in graph[0] :
    times[i] = 0
    dfs(i)
    maxB = max(maxB, times[i])
print(n-maxB)
```
# 感想
諸事情あり、で久々の投稿になってしまいました。また、リアル参戦ができませんでした。
まだ投稿できておりませんが、ABC332とARCでやらかしてしまい、年内入緑は厳しそう、、です。