ABC333の解説記事 (PyPy3 ABCD)

はじめに

問題はこちら
初心者（灰色〜茶色）向けです。

A - Three Threes

考え方

Pythonは同じ文字列の任意回数の繰り返しは文字列×文字数　で書けるので、
str(n) * n などと書けば良いです。（入力をintで受け取った場合）

解答例

私の解答

n = int(input())
print(str(n)*n)

B - Pentagon

考え方

正五角形の対角線は全て同じ長さで、辺より必ず長いですから、

1. 二つの線分が共に辺、もしくは 共に対角線　であれば、「Yes」
2. 二つの線分の一方が辺、もう一方が対角線であれば、「No」

と考えます。
五角形の辺は5つしかないため、頂点の順番を考慮しても辺である文字列は10個です。
また、正五角形ABCDEの頂点が隣り合っている時が辺で、そうでない時は対角線ですから、この列挙は簡単です。

解答例

私の解答

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がその部分文字列であれば、辺、そうでなければ対角線と判定しています。

C - Repunit Trio

考え方

Nは最大333までしかないので、全て列挙して答えを出せば良いです。
また、この問題では、使用する最大のレピュニットは、「111111111111」（1が12こ続く）まであれば十分です。
実際、$K$種類のレピュニットを使った3つの和のパターン数は

1. 1種類のみを使うパターン：　$K$個
2. 2種類のみを使うパターン：　$K(K-1)$個
3. 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$
となります。ｆ

解答例

私の解答

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

考え方

「1」を削除するためには、「1」を葉にする必要があります。
「1」を葉にするためには、「1」と繋がっているノードの数が1つになるように「1」に繋がるノードを削除する必要があります。
そのため、最小になるのは、「1」に繋がるノードを削除するのが一番大変なノード以外を削除して、「1」を削除するときです。
よって、「1」に繋がるノードで一番削除に必要な枚数が多いものを考えます。
ここで、「1」に繋がるノード「X」を削除するには、「X」と「1」を切り離した、「X」側のノードのうち、「X」以外を全て削除する必要があります。
そのため、「1」と「X」を切り離したときの「X」を含む連結成分の数を数えればよい、ということになります。
これは、DFSで解けます。また、連結成分をグループに分けるので、UnionFind木でも解けます。
解答例では、timesで各ノードを削除するための最低枚数を保持しています。
-1が未設定で、0が設定中、それ以外の正の値が最低枚数　になっています。（「1」のノードは設定中としています。）

解答例

私の解答

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でやらかしてしまい、年内入緑は厳しそう、、です。