AtCoderをPythonで取り組んだ振り返り(ABC424 A~C)

どうもこんにちは！

今週のコンテストはCまで完答、振り返りもCまで。
C問題で再帰を使ったらREになってはまってしまい、D問題に取り組む時間はありませんでした。。

問題と公式の解説のリンク

問題は以下のリンクから。

A - Isosceles -

問題

与えられた3つの数値で二等辺三角形を作れるかを判定する問題。正三角形も二等辺三角形に含まれます。

考え方とコード

三角形の条件は2辺の和が残り1辺より長いです。加えていずれか2辺の長さが同じとなっているかを判定するようにしました。

a,b,c = map(int,input().split())
ans = False
if (a == b or b == c or a == c) and (a+b > c and b+c > a and a+c > b):
    ans = True

print("Yes" if ans else "No")

B - Perfect -

問題

N人がM問の問題を解くとし、人iが問題jを解けたというイベントがK個与えられます。
すべてのイベントを順番に処理して全問解けた人を早く解けた順に出力する問題。
なお、人数や問題数の最大はそれぞれ10人。イベントの数は1以上で上限の規定はなし。

考え方とコード

問題を解けたかを管理するフラグを用意して、イベントを処理するごとに全問解けた人がでてきたらその人を別で保持するという形にしました。

n,m,k = map(int,input().split())
ans = [[False] * m for _ in range(n)]
p = []
for _ in range(k):
    a,b = map(int,input().split())
    ans[a-1][b-1] = True
    if ans[a-1].count(True) == m:
        p.append(a)

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

C - New Skill Acquired -

問題

1からNの番号がついたスキルがあるとし、スキルiの習得条件は以下のどちらかを満たした場合です。

• 与えられた数値AiとBiがともに0の場合
• AiまたはBiの数値のスキルを習得済みの場合。例えばスキル4に対して与えられた数値A4が2、B4が6だった場合、スキル2か6を習得していればスキル4も習得できるとなります。

以上の条件のもとでn,Ai,Biを与えられたときに習得するスキルの数を出力する問題。
なお、Nの最大は$2×10^5$、AiとBiの値の範囲は1からN。

考え方とコード

解説見たらグラフを作って探索すればよいそうですね・・・全然思いいたりませんでした。
ということで以下は別解ということで。。
基本は問題の通りですが、スキル1から順番に習得可否を確認したときに、例えばスキル6を習得できたことでスキル2が習得でき、さらにスキル2を習得できたことでスキル3も習得できるようになったというように連鎖が発生するケースを考慮する必要があります。
コーディングの考え方としてはスキルiを習得したときに習得可能となるスキルの番号を辞書で記録しておき、スキルが習得できたときにその辞書を確認して習得可能となったスキルを習得していくという形で実装しました。
これを再帰で作って最終的にACにできたんですが、ずっとREで解消できず1時間近く悩みました。。再帰の回数に制限があるというのをふと思い出して調べてことなきを得ましたが、我ながらよく思い出せたなと思います。

import sys
sys.setrecursionlimit(10**9)

def check(di):
    for i in di:
        if s[i] == False:
            s[i] = True
            if i in d:
                check(d[i])


n = int(input())

s = [False] * (n+1) # 習得済みスキルのまとめ
d = {}              # 条件を満たしたときに習得できるスキルの辞書
for i in range(1,n+1):
    ai,bi = map(int,input().split())

    # スキルの習得条件を満たしているかを確認
    if (ai == 0 and bi == 0) or (s[ai] == True or s[bi] == True):
        s[i] = True
        # スキルiの習得が習得条件のスキルをチェック
        if i in d:
            check(d[i])
    # 習得条件の辞書の作成
    # ほかのスキルを習得したときにスキルiも習得できるかの確認に使う
    else:
        if ai not in d:
            d[ai] = [i]
        else:
            d[ai].append(i)
        if bi not in d:
            d[bi] = [i]
        else:
            d[bi].append(i)

print(s.count(True))

ではでは。