ABC354をPythonで（A～E）

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

A問題

問題文通りにシミュレーションする

A

h = int(input())

t = 0
i = 0
while h >= t:
    t += 2 ** i
    i += 1

print(i)

B問題

問題文の通りにする

B

n = int(input())
t = 0
lst = []
for _ in range(n):
    s, c = input().split()
    lst.append(s)
    t += int(c)

lst.sort()
print(lst[t % n])

C問題

カードを強いほうから降順にソートする
強いほうから見たときにすでに出たコストより大きいものがあったときは対象にならないので除外

C

n = int(input())
card = [tuple(map(int, input().split())) for _ in range(n)]

d = {c_i: i for i, c_i in enumerate(card, 1)}

card.sort(reverse=True)
cost = float("inf")
ans = list()
for a, c in card:
    if cost >= c:
        cost = c
        ans.append(d[(a, c)])

print(len(ans))
print(*sorted(ans))

D問題

ぱっと見で面倒そうだったからさきにEを解いてから解き始めた
$4 \times 2$で繰り返しているのを使って累積和のように解こうとしたがうまくいかなかった

E問題

とってないカードのパターンはbitの範囲で収まるから

$dp[bit] = $とってないカードが$bit$の時に勝てるか

として各局面でとれるペアを取ったその先の盤面が負け盤面だったらTrueにする

E

n = int(input())

card = [list(map(int, input().split())) for _ in range(n)]
ANSWER = ["Takahashi", "Aoki"]

edge = [[False] * n for _ in range(n)]
for i in range(n):
    for j in range(i):
        if card[i][0] == card[j][0] or card[i][1] == card[j][1]:
            edge[i][j] = True
            edge[j][i] = True

dp = [False] * (1 << n)  # 勝てる手があるならTrue
for bit in range(1 << n):
    for j in range(n):
        if bit >> j & 1:
            for i in range(j):
                if bit >> i & 1 and edge[i][j] and not dp[bit - (1 << i) - (1 << j)]:
                    dp[bit] = True

print(ANSWER[dp[-1] ^ 1])