AtCoder ABC 424 解いてみた (PythonでABC問題)

ABC424を復習しました

今回はリアルタイム参加できなかったため、後日問題を解きました。
結果は、ABCまで3問解答でした。

C問題は難しく感じ、4回提出してACしました。
リアタイ参加ではないための緊張感のなさもあったのですが、本番だったらできていただろうか...と不安もあります。

D問題も考えて回答を提出したのですが、解けませんでした。
貪欲法で行けそうと思ったんですが、解説によれば貪欲法は駄目だったようです。

A - Isosceles

辺の長さが3つとも異なる場合のみ、二等辺三角形ではないので、「No」を出力します。

判定は 辺A, 辺B, 辺C のSetを作成し、値が全部異なる場合、Setの要素数が3になることを利用しました。

a, b, c = map(int, input().split())
set_abc = {a, b, c}
if len(set_abc) == 3:
    print("No")
else:
    print("Yes")

B - Perfect

各回答者が解いた問題を dict に記録します。
dict の key が回答者ID、valueがその回答者が解いた問題の集合(set)です。
set が M個になれば、その回答者IDが全問題を解いたことになるので、answersに追加します。

N, M, K = map(int, input().split())

records = defaultdict(set) # key: 回答者ID, value: その回答者が解いた問題の集合
answers = [] # 全問解答者を回答順に格納するリスト

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

    # AさんがB問題を解いたことを記録
    records[A].add(B)

    # Aさんが全問解答したか確認
    if len(records[A]) == M:
        answers.append(A)

if len(answers) > 0:
    print(*answers)

C - New Skill Acquired

高橋くんは A, B = 0 のスキルは覚えているので、最初に initial_skill_set に記録します。
習得しているスキルを起点に、BFSで習得可能なスキルを探索しました。

---

入力例1 でいうと以下のように求められます。

initial_skill_set = {1} です。
↓
{1 or 3} のスキルが有れば、スキル2が習得可能になります。
↓
{2 or 3} のスキルが有れば、スキル3が習得可能になります。

---

N = int(input())
AB = []
for i in range(N):
    A, B = map(int, input().split())
    AB.append((A, B))

initial_skill_set = set() # 最初に覚えているスキル
skill_link = defaultdict(list) # key: スキルID, value: そのスキルがあれば習得可能なスキルIDのリスト

for i in range(N):
    A, B = AB[i]
    if A == B == 0:
        initial_skill_set.add(i + 1)
    else:
        skill_link[A].append(i + 1)
        skill_link[B].append(i + 1)

learned_skills = set(initial_skill_set) # 覚えているスキルの集合

# 初期スキルからBFSで習得可能なスキルを探索
for initial_skill in initial_skill_set:
    if initial_skill not in skill_link and initial_skill in learned_skills:
        continue

    # BFSで習得可能なスキルを探索
    queue = deque()
    queue.append(initial_skill)
    while queue:
        skill = queue.popleft()
        for linked_skill in skill_link[skill]:
            if linked_skill not in learned_skills:
                queue.append(linked_skill)
                learned_skills.add(linked_skill)

print(len(learned_skills))