ABC427をPythonで

パナソニックグループ プログラミングコンテスト2025（AtCoder Beginner Contest 427）の解答等の速報的まとめ

A問題

真ん中 = len(s) // 2

A

s = input()

print(s[:len(s) // 2] + s[len(s) // 2 + 1:])

B問題

桁和を別途記録する

B

def calc(x):
    res = 0
    for i in str(x):
        res += int(i)
    return res

a = [1]
f = [1]

for _ in range(100):
    f.append(calc(a[-1]))
    a.append(sum(f))

print(a[int(input()) - 1])

C問題

bitで2部グラフの全パターンを検証
繋がっている頂点が同じグループだったらその辺を消す対象として記録

C

n, m = map(int, input().split())
data = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(m)]

ans = m
for bit in range(1 << n):
    ans_i = 0
    for u, v in data:
        if (bit >> u & 1) ^ (bit >> v & 1):
            continue
        else:
            ans_i += 1
    ans = min(ans, ans_i)

print(ans)

D問題

メモ化再起でDFSをする
DFS内はミニマックス法で判定

D

def generate_key(a, b):
    return a * 100 + b

def calc(now, depth=0):
    global memo
    key = generate_key(now, depth)
    if key in memo:
        return memo[key]
    elif depth == k:
        memo[key] = s[now]
        return s[now]
    else:
        st = set()
        for to in edge[now]:
            st.add(calc(to, depth + 1))

        if len(st) == 2:
            memo[key] = "A" if depth % 2 == 0 else "B"
        else:
            memo[key] = st.pop()
        return memo[key]


ans = {"A":"Alice", "B":"Bob"}
for _ in range(int(input())):
    memo = dict()
    n, m, k = map(int, input().split())
    k *= 2
    s = input()
    edge = [list() for _ in range(n)]
    for _ in range(m):
        u, v = map(lambda x:int(x) - 1, input().split())
        edge[u].append(v)

    result = calc(0, 0)
    print(ans[result])