AtCoder-ABC225 A - Distinct Strings / B - Star or Not【Python解答例】

AtCoder Beginner Contest225のA とB問題についてPythonの解答例を記事にしていきます。
UNICORN Programming Contest 2021(AtCoder Beginner Contest 225) - AtCoder

AtCoder Beginner Contest225 A - Distinct Strings

A - Distinct Strings

問題文

英小文字のみからなる長さ 3 の文字列 S が与えられます。

S の各文字を並び替えて得られる文字列は、何種類ありますか？

制約

・S は英小文字のみからなる長さ 3 の文字列

解答例

S = input()

if S[0] == S[1] and S[1] == S[2]:
    print(1)
elif S[0] != S[1] and S[1] != S[2] and S[2] != S[0]:
    print(6)
else:
    print(3)

解説

3文字の英子文字から何通りの文字列がつくれるか答える問題です。

3文字のなかに同じ文字があるかで場合分けを行いました。

3文字がすべて同じ文字の場合は、できる文字列は1通りだけです。

すべて文字が異なれば、文字列は6通りできます。

そうでなければ、おなじ文字が2つの場合になりますので、そのときは3通りです。

この場合分けで答えを出力すればOKでした。

AtCoder Beginner Contest225 B - Star or Not

B - Star or Not

問題文

N 頂点 N−1 辺の木が与えられます。

頂点には 1,2,…,N の番号がついており、i 本目の辺は頂点 a i​ と頂点 b i​ を結んでいます。

この木がスターであるか判定してください。

ただしスターとは、1 つの頂点から、他の全ての頂点に 1 本ずつ辺が出ている木のことです。

制約

・3≤N≤10 ^5
・1≤a i​

解答例

n = int(input())

graph = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

res = 0
for i in range(n):
    res = max(res,len(graph[i]))

if res == n-1:
    print("Yes")
else:
    print("No")

解説

N頂点N-1辺の木が与えられ、その木がスターか判別する問題です。

スターとは問題文にあるように、１つの頂点からほかのすべての頂点に1本ずつ辺がでている木のことです。

配列graphを用意して、各頂点から出ている辺を格納していきます。
graph[i]には頂点iから辺でつながっているほかの頂点が保存されています。

したがって、変数resを用意し、ひとつの頂点から出ている辺の最大値を求めました。

このresがn-1ならばその木はスターで、そうでなければスターでないと判別できました。