ABC358をPythonで（A～E）

CodeQUEEN 2024 予選 (AtCoder Beginner Contest 358)の解答等のまとめ

A問題

問題文どおりにする

A

print("Yes" if input() == "AtCoder Land" else "No")

B問題

直前の人がいつ終わるかが解ればいいので
直前に回答したものを記録すればいい

B

n, a = map(int, input().split())
t = list(map(int, input().split()))

last = 0
for t_i in t:
    print(max(t_i, last) + a)
    last = max(t_i, last) + a

C問題

bit全探索
bitで行くパターンを決めて、そのパターンですべての味が手に入れられるか調べる

C

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

ans = m + 10
for bit in range(1 << n):
    store = []
    for i in range(n):
        if bit >> i & 1:
            store.append(i)
    data = [0] * m
    for s_i in store:
        for j, s_j in enumerate(s[s_i]):
            if s_j == "o":
                data[j] = 1
    if data == [1] * m:
        ans = min(ans, len(store))

print(ans)

D問題

AとBをまとめて多いほうから考える（同数の時はAが先になるようにする）
Aがきたときは、スタックに入れる
Bがきたときは、スタックの最後の値を取得する
（なぜならスタックの最後に入っているのは、まだ選択していないものの中で買う条件を満たす最小のものになるから）
途中でスタックが空の状態でBが来たら条件は必ず満たせないので-1を返す

D

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

data = []
for a_i in a:
    data.append([a_i, True])
for b_i in b:
    data.append([b_i, False])

data.sort(reverse=True)

ans = 0
stack = []
for d_i, is_gift in data:
    if is_gift:
        stack.append(d_i)
    else:
        if stack:
            s_i = stack.pop()
            ans += s_i
        else:
            exit(print(-1))

print(ans)

E問題

メモ化再帰
$i$文字目以降でで$k$文字を埋める時の組み合わせは
$i$文字目を$c_i$個使うとしたとき、どこを埋めるかの組み合わせ$ \times$ $i+1$文字目以降で$k - c_i$文字埋める組み合わせ
を0から$min(k, c[i])$までの和が答えになる

E

class combination:
    # nが小さい(10**7未満)でないと厳しい
    def __init__(self, N, mod):
        self.fact = [1, 1]
        self.factinv = [1, 1]
        self.inv = [0, 1]

        for i in range(2, N + 1):
            self.fact.append((self.fact[-1] * i) % mod)
            self.inv.append((-self.inv[mod % i] * (mod // i)) % mod)
            self.factinv.append((self.factinv[-1] * self.inv[-1]) % mod)

    def cmb(self, n, r):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return self.fact[n] * self.factinv[r] * self.factinv[n - r] % mod


k = int(input())
c = list(map(int, input().split()))
mod = 998244353

C = combination(1010, mod)

memo = [[-1] * 1010 for _ in range(26)]


def dfs(i, k):
    global memo
    if i == 26:
        return 1 if k == 0 else 0
    elif memo[i][k] >= 0:
        return memo[i][k]
    else:
        res = 0
        for c_i in range(min(c[i], k) + 1):
            res += dfs(i + 1, k - c_i) * C.cmb(k, c_i) % mod
        memo[i][k] = res
        return res


ans = 0
for k_i in range(1, k + 1):
    used = 0
    ans += dfs(0, k_i)
    ans %= mod

print(ans)