どうもこんにちは！
今週はCまでの3完でした。
C問題に１時間近くかけてしまいD問題には手を出せずでした。気づいてしまえばグラフの始点から到達可能な点の個数を出力するだけなのにねぇ。。
問題と公式の解説のリンク
問題は以下のリンクから。
A - Closed interval -
問題
与えられた2つの整数l,rがあり、l以上r以下の整数を出力する問題。
考え方とコード
r-l+1を出力すればOK。
l,r = map(int,input().split())
print(l-r+1)
B - Mapping -
問題
n人の人がいて、人iはm種類ある服のうちの１つを着ているとし、着ている服はリストで与えられているとします。
このときに人は全員異なる種類を着ているか、またM種類の服はすべて１人以上に着られているかをそれぞれ出力する問題。
考え方とコード
着ている服のリストの集合を作り、以下の通り判定して出力すればOKです。
- 集合の要素数がnであれば、人はすべて異なる服を着ています
- 集合の要素数がmであれば、すべての種類の服は1人以上に着られています
n,m = map(int,input().split())
f = [int(x) for x in input().split()]
sf = set(f)
print("Yes" if len(sf) == n else "No")
print("Yes" if len(sf) == m else "No")
C - Straw Millionaire -
問題
1からnまでのn種類のアイテムがあり、最初にアイテム1を持っているとします。
この状態からm人に会うとして、人iはアイテムAを持っていたらアイテムBをくれるとしたとき、入手できるアイテムはアイテム1も入れて何種類かを出力する問題。
なお、m人に会う順番は任意の順番でOKです。また、設問としては交換という形ですが回答は一度に持てる最大数ではなく、可能な交換ルートを使ったら何が手に入るかを出力することになります。
考え方とコード
アイテムを頂点、アイテムAからアイテムBの交換を辺とみると、頂点がn個で辺がm本のグラフができます。あとはアイテム1を始点とした幅優先探索で到達可能な頂点の数を出力すればOKです。
from collections import deque
n,m = map(int,input().split())
g = [[] for _ in range(n)]
for _ in range(m):
i,j = map(int,input().split())
g[i-1].append(j-1)
ans = 1
q = deque()
q.append(0)
visited = [False for _ in range(300000)]
visited[0] = True
while q:
i = q.popleft()
for j in g[i]:
if visited[j] == False:
ans += 1
visited[j] = True
q.append(j)
print(ans)
ではでは。