[ABC288 Python]Toyota Programming Contest 2023 Spring Qual A（AtCoder Beginner Contest 288）A～D問題Python解説

A問題

A - Many A+B Problems

N = int(input())
for i in range(N):
    A, B = map(int, input().split())
    print(A+B)

基本的には問題文のとおりに解ければ大丈夫です。
AとBがN回入力されるので、
1回ごとにA+Bを出力します。

B問題

B - Qualification Contest

N, K = map(int, input().split())
ans = []
for i in range(K):
    S = input()
    ans.append(S)
ans.sort()
for i in ans:
    print(i)

まずは、出力の対象となるのが
上位K人なので、
入力をすべて受け取る必要はなく、
K回だけで大丈夫です。
受け取ったK人のリストansを辞書順に並べ替えて、
1人ずつ出力することで回答します。

C問題

C - Don’t be cycle

import sys
sys.setrecursionlimit(10**7)

N,M = map(int, input().split())
Adj = [[] * N for _ in range(N)]

for _ in range(M):
  A,B = map(int, input().split())
  Adj[A-1].append(B-1)
  Adj[B-1].append(A-1)

def dfs(x):
  for y in Adj[x]:
    if not visited[y]:
      visited[y] = True
      dfs(y)

visited = [False] * N
cyc = 0

for i in range(N):
  if not visited[i]:
    visited[i] = True
    dfs(i)
    cyc += 1

print(M - N + cyc)

問題文より、グラフが閉路を持たないようにする
という記述があります。

では、グラフに閉路を持たせるためにはどうすればいいのかを考えてみます。

下の画像をご覧ください。

https://algo-logic.info/connected-components-num/

図のように連結成分の個数をcとすると、
答えとなる削除するべき辺の数ansは、
ans = 辺の数M-点の数N⁺連結成分の個数c
となります。

連結成分の個数はDFSやBFS、UnionFindなどで求めることができます。

D問題

D - Range Add Query

後日記載します。