ABC404 の振り返り(A~D, Python)

A

({chr(i) for i in range(ord("a"), ord("z") + 1)} - set(S)).pop()
- 集合内包表記{chr(i) for i in range(ord("a"), ord("z") + 1)}で"a"~"z"の集合を作る
- そこから、Sの要素を取り除いたあとに一つを取得

def main():
    S = input()
    res = solve(S)
    print(res)


def solve(S: str) -> str:
    return ({chr(i) for i in range(ord("a"), ord("z") + 1)} - set(S)).pop()


if __name__ == "__main__":
    main()

別解

"a"~"z"を一つずつ見て、Sに含まれるか判定する
- 本番ではこっちで解いた

def main():
    S = input()
    res = solve(S)
    print(res)


def solve(S: str) -> str:
    for i in range(ord("a"), ord("z") + 1):
        t = chr(i)
        if t not in S:
            return t
    return ""


if __name__ == "__main__":
    main()

B

塗り替えのマスをカウント→最小だったら記録→回転を4回繰り返す
- カウントした値 + 回転した回数が求めたい値

def main():
    N = int(input())
    S = [list(input()) for _ in range(N)]
    T = [list(input()) for _ in range(N)]
    res = solve(N, S, T)
    print(res)


def solve(N: int, S: list[list[str]], T: list[list[str]]) -> int:
    def rotate(S: list[list[str]]) -> list[list[str]]:
        return [[S[N - 1 - j][i] for j in range(N)] for i in range(N)]

    def count(S: list[list[str]]) -> int:
        cnt = 0
        for i in range(N):
            for j in range(N):
                if S[i][j] != T[i][j]:
                    cnt += 1
        return cnt

    res = -1
    for i in range(4):
        cnt = count(S) + i
        if res == -1 or cnt < res:
            res = cnt
        S = rotate(S)
    return res


if __name__ == "__main__":
    main()

C

以下の2つの条件を満たすときサイクルグラフ
- すべての頂点の次数が2
  - すべて数えて判定
- 連結グラフ
  - DSU(Union-Find)で判定
本番では連結でない場合を見落としてWA→その後辿りながら判定した

from atcoder.dsu import DSU  # type: ignore


def main():
    N, M = map(int, input().split())
    AB = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]
    res = solve(N, M, AB)
    print("Yes" if res else "No")


def solve(N: int, M: int, AB: list[list[int]]) -> bool:
    dsu = DSU(N)
    cnt = [0 for _ in range(N)]
    for a, b in AB:
        dsu.merge(a, b)
        cnt[a] += 1
        cnt[b] += 1

    for c in cnt:
        if c != 2:
            return False

    if dsu.size(0) != N:
        return False

    return True


if __name__ == "__main__":
    main()

D

各動物園への訪問回数を0~2で全探索
- 同じ動物は2回見られればいいので3回以上同じ動物園に行く必要はない
- 3進数を使ってbit全探索の感じで探索

def main():
    N, M = map(int, input().split())
    C = [int(c) for c in input().split()]
    KA = [list(map(int, input().split())) for _ in range(M)]
    res = solve(N, M, C, KA)
    print(res)


def solve(N: int, M: int, C: list[int], KA: list[list[int]]) -> int:
    B: list[set[int]] = [set() for _ in range(N)]
    for i in range(M):
        for a in KA[i][1:]:
            B[a - 1].add(i)
    res = -1
    for i in range(3**N):
        mem = [0 for _ in range(M)]
        cost = 0
        for j in range(N):
            cnt = (i // (3**j)) % 3
            for a in B[j]:
                mem[a - 1] += cnt
            cost += C[j] * cnt
        if any(mem[i] < 2 for i in range(M)):
            continue
        if res == -1 or cost < res:
            res = cost
    return res


if __name__ == "__main__":
    main()

E

今週もEは全然わからなかった
- 40ケースでWAした