🎉
【ABC287】AtCoder Beginner Contest 287 A-D 振り返り【python】
A - Majority
それぞれの文字のカウントする。Forが大きかったらYes。
解法
n = int(input())
s_list = [input() for i in range(n)] # 文字列S
for_count = 0
against_count = 0
for i in s_list:
if i == "For":
for_count += 1
else:
against_count += 1
if for_count >= against_count:
print("Yes")
else:
print("No")
B - Postal Card
文字列の末尾3つは、s[-3:]で取り出すことが可能。存在確認はsetを使って計算量削減。
参考↓
n, m = map(int, input().split())
s_list = [int(input()) for i in range(n)] # 文字列S
t_list = [int(input()) for i in range(m)] # 文字列T
t_set = set(t_list)
count = 0
for s in s_list:
s = str(s)
selected = int(s[-3:])
if selected in t_set: # 効率化のため、setで存在確認
count += 1
print(count)
C - Path Graph?
問題文にある条件を満たすためには以下の3つを満たす必要がある。
- 次数が2以下
- 次数1が2つ
- グラフが連結
atcoder公式の解説では 辺がちょうどN-1本が条件となっているが、多分次数1が2つでも大丈夫なはず。間違っていたらコメントください。
グラフの連結はUnion Findを作成して、グループ（連結成分）が1であることを確認すればよい。
Union Findの実装はこちらを参考に実装したものを使用する。
from collections import defaultdict
class UnionFind:
# ↑ 記事では割愛
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
uf = UnionFind(n)
one_num = 0 # 次数1のカウント
two_num = 0 # 次数2のカウント
for _ in range(m):
a, b = map(int, input().split())
a -= 1
b -= 1
graph[a].append(b)
graph[b].append(a)
uf.union(a, b)
for one in graph:
if len(one) == 1:
one_num += 1
elif len(one) == 2:
two_num += 1
else:
print("No")
exit()
if one_num == 2 and uf.group_count() == 1:
print("Yes")
else:
print("No")
D - Match or Not
先頭から判定する配列pre[len(T)+1]と後ろから判定する配列suf[len(T)+1:を初期値Falseで定義する。それぞれの0番目はTrue（判定する文字列がない）。
SとTを先頭から判定し、マッチしたらpre[i+1]=Trueにする。マッチしない場合、それ以降はすべてをFalseにする。
SとTを逆順にして同じ処理をsufで行う。
これらの処理は公式の解説動画がわかりやすく解説している。 YouTubeのvideoIDが不正です
s = list(input())
t = list(input())
def match_or_not(a, b):
if a == "?" or b == "?" or a == b:
return True
else:
return False
pre = [False] * (len(t) + 1)
suf = [False] * (len(t) + 1)
pre[0] = True
for i in range(len(t)):
if not match_or_not(t[i], s[i]): # 一致しなかったらそれ以降すべてマッチせず
break
else:
pre[i + 1] = True
s = s[::-1]
t = t[::-1]
suf[0] = True
for i in range(len(t)):
if not match_or_not(t[i], s[i]):
break
else:
suf[i + 1] = True
for i in range(len(t) + 1):
if pre[i] and suf[len(t) - i]:
print("Yes")
else:
print("No")
Discussion