ABC323をPythonで（A~D）+α

ユニークビジョンプログラミングコンテスト2023 秋 (AtCoder Beginner Contest 323)

A問題

全探索

A

s = input()
if all(s[i] == "0" for i in range(1, 16, 2)):
    print("Yes")
else:
    print("No")

B問題

全探索

B

n = int(input())
lst = []
for i in range(1, n + 1):
    s = input()
    lst.append((s.count("o"), -i))

lst.sort(reverse=True)
ans = []
for _, i in lst:
    ans.append(-i)

print(*ans)

C問題

まず、各プレイヤーのスコアを計算する。
その後、正解していないものを使って今のスコアから最大スコアに並ぶ最少問数をDPで計算する。

C

n, m = map(int, input().split())
a = list(map(int, input().split()))
data = []
score = []
for i in range(1, n + 1):
    s = si()
    x = 0
    lst = []
    for j, s_i in enumerate(s):
        if s_i == "o":
            x += a[j]
        else:
            lst.append(a[j])
    data.append(lst)
    score.append(x + i)

maxi = max(score)
INF = float("inf")
for d_i, s_i in zip(data, score):
    if maxi == s_i:
        print(0)
    else:
        dp = {s_i: 0, maxi:INF}
        for a_i in d_i:
            dp_copy = dict(dp)
            for key, val in dp_copy.items():
                if key + a_i in dp:
                    dp[key + a_i] = min(val + 1, dp[key + a_i])
                elif key + a_i >= maxi:
                    dp[maxi] = min(dp[maxi], val + 1)
                else:
                    dp[key + a_i] = val + 1

        print(dp[maxi] if dp[maxi] < INF else -1)

D問題

スライムはそれぞれ限界までマージしたら各種1匹までに収まる。
よってそれぞれのサイズについて
1、はぐれがいたらそいつを加える
2、限界までマージする
3、1匹のがでたら隔離する
をできるだけ続ける。

D

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

data.sort()

s = set()
for s_i, c_i in data:
    while c_i >= 1:
        if s_i in s:
            c_i += 1
            s.discard(s_i)
        if c_i == 1:
            s.add(s_i)
            break

        if c_i % 2 == 1:
            s.add(s_i)
        c_i //= 2
        s_i *= 2

print(len(s))

EとFの感想

• E
  確率DPは自分にはなかなか難しい
• F
  難しくないのに気付いて取り組んだが、Eにとらわれすぎてコーナーつぶしの時間が足りなかった。

後日解く
書きました