[ABC292 Python]AtCoder Beginner Contest 292A～D問題Python解説

A問題

A - CAPS LOCK

S = input()
s = S.upper()
print(s)

Pythonには英大文字小文字の変換をする関数が既に存在するので、それを使いましょう。

大文字と小文字を変換する(lower, upper, capitalize, title, swapcase)

upper メソッドは文字列のすべての文字を大文字に変換した新しい文字列を返します。

B問題

B - Yellow and Red Card

N, Q = map(int, input().split())
player = [0 for _ in range(N)]

for i in range(Q):
    c, x = map(int, input().split())
    x -= 1
    if c == 1:
        player[x] += 1
    elif c == 2:
        player[x] += 2
    else:
        if player[x] >= 2:
            print("Yes")
        else:
            print("No")

選手のもらったカードの枚数を保存し、
c = 3の時にそれを見返して出力しましょう。

問題文のとおり、
イエローカードは2枚でレッドカードとなり退場となります。
つまりカードの枚数で言うと、
イエローカードをもらったときはカード+=1
レッドカードをもらったときはカード+=2
として、
もらったカードの枚数が2枚以上だったら退場だと判断します。

後はイベントごとに指示通り判断すればよさそうです。

C問題

C - Four Variables

N = int(input())
from collections import defaultdict
d = defaultdict(int)


def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

for i in range(1, N):
    d[i] = len(make_divisors(i))


ans = 0
for i in d:
    ans += ans[i]*ans[N-i]

# print(ans)
print(ans)

Nの値が大きいので、
A,B,C,D全ての値を試すとTLEになります。

今回考え方で重要なのは、
ABとCDの区別、
AとBの区別、
CとDの区別は必要ないということです。

具体的に入力例1を見ながら解説したいと思います。

N = 4

今回AB + CD = 4となる
ABCDを探すわけですが、
ABCDは問題文から0より大きい整数であるので、
AB=1,CD=3
AB=2,CD=2
AB=3,CD=1
に絞ることができます。

一般的に考えると、
i=1~N-1の整数iについて
積がiになるような正の整数を探せばいいということになります。
これを俗に約数ということになります。

入力例1の場合は、
積が1になるのは1×1の1個
積が2になるのは1×2,2×1の2個
積が3になるのは1×3,3×1の2個
が考えられます。

また、
和が4になるのは1+3,2+2,3+1
の3通りなので、
計算式は
(積が1の個数)×(積が3の個数)+(積が2の個数)×(積が2の個数)+(積が3の個数)×(積が1の個数)
=1×2+2×2+2×1
=8
という計算になります。

約数の計算は以下を参考にさせていただきました。

約数を高速で列挙するコード(Python) - Qiita

後は積がiの個数を保存して足してNになるように個数の掛け算をしたら答えにたどり着きます。

D問題

D - Unicyclic Components

from collections import defaultdict, deque
# NとMを入力
N, M = map(int, input().split())
# 変数graphに辺の情報を保存
graph = defaultdict(list)
# 1つの辺が同じ頂点を結ぶ場合(ループと名付ける)、その辺の個数を頂点ごとに保存
looped = [0 for _ in range(N)]
for i in range(M):
    # uとvを入力
    u, v = map(int, input().split())
    # インデックスの関係で-1する
    u -= 1
    v -= 1
    # ループの場合
    if u == v:
        looped[u] += 1
    else:
        graph[u].append(v)
        graph[v].append(u)
# 全ての頂点について調べたか調べてないかを保存する
visited = [False for _ in range(N)]

for i in range(N):
    # 既に調べた頂点であればスルーする
    if visited[i]:
        continue
    # これから調べなければいけない頂点をqueに保存していく
    que = deque()
    # まずは現在いる頂点を調べる
    que.append(i)
    # 頂点の数を保存するvertex
    vertex = 0
    # 辺の数を保存するside
    side = 0
    # ループの数を保存するloop
    loop = 0
    # 調べる頂点がなくなるまで続ける
    while que:
        # 現在いる頂点now
        now = que.popleft()
        # 頂点の個数+1する
        vertex += 1
        # ループがあればループ+1
        loop += looped[now]
        # この頂点は調べているのでTrueにする
        visited[now] = True
        # この頂点から辺が伸びている全ての頂点について
        for next in graph[now]:
            # 辺の数+1
            side += 1
            # 次の頂点がまだ調べていなかったら
            if not visited[next]:
                # その頂点を調べたことにする
                visited[next] = True
                # その頂点を調べるためにqueに追加する
                que.append(next)
    # 左辺＝頂点の数、右辺＝辺の数＋ループの数
    # 辺は往復するので2で割った数にする
    if vertex != side//2 + loop:
        print("No")
        exit()
# 全ての連結成分に対して、頂点の個数と辺の本数が等しいことが確認出来たら最後にYesと出力する
print("Yes")

2023/03/08追記しました。

グラフの問題ではUnionFindやDFS、BFSが用いられますが、今回はBFSで考えていきます。

グラフの問題で連結成分の個数を求める問題が良く出題されると思うのですが、それを少しいじって、頂点と辺の数を数えながら求めていくことで、
全ての連結成分について、頂点の個数と辺の本数を数えることができます。

1つ注意しなければいけないのは、
今回はuiとviが違うとは限らないので、
辺の両端が同じ点を結ぶ場合について留意しなければいけません。