ABC346をPythonで（A～E）

ユニークビジョンプログラミングコンテスト2024 春（AtCoder Beginner Contest 346）の解答等のまとめ

A問題

問題文通りにfor文ループさせる

A

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

print(*[a_i * a_j for a_i, a_j in zip(a, a[1:])])

B問題

計算して求めるともできるが、可能性があるぐらいだけの数Sを連結させて$w+b$の幅を確認すればいい

B

s = "wbwbwwbwbwbw"

w, b = map(int, input().split())

s = s * (w // 7 + 2)

for i in range(len(s) - w - b):
    t = s[i:i + w + b]
    if t.count("w") == w and t.count("b") == b:
        exit(print("Yes"))

print("No")

C問題

もし$A$の中に$K$以下がなければ答えは$k \times (k+1) \div 2$
よって重複に気を付けて上の値から引き算すればいい

C

n, k = map(int, input().split())

a = set(map(int, input().split()))

ans = k * (k + 1) // 2
for a_i in list(a):
    if 1 <= a_i <= k:
        ans -= a_i

print(ans)

D問題

DはDPのD
$dp[i][j][k] = j$番目までで数字が$k$で同じものが$i$個あるときの最小コスト
とすればいい

D

n = int(input())
s = input()
c = list(map(int, input().split()))

INF = float("inf")
dp = [[[INF, INF] for _ in range(n)] for _ in range(2)]
dp[0][0][int(s[0])] = 0
dp[0][0][int(s[0]) ^ 1] = c[0]

for i in range(1, n):
    for A in range(4):
        a, b = A // 2, A % 2
        if a == b:
            dp[1][i][a] = min(dp[1][i][a], dp[0][i - 1][b] + c[i] * (int(s[i]) != a))
        else:
            dp[0][i][a] = min(dp[0][i][a], dp[0][i - 1][b] + c[i] * (int(s[i]) != a))
            dp[1][i][a] = min(dp[1][i][a], dp[1][i - 1][b] + c[i] * (int(s[i]) != a))

print(min(dp[1][-1]))

E問題

$i$番目で$a_i$行に$x_i$を塗るとしてその色が残るのは、

• $a_i$行目がそれ以降塗られない
• 各列のうち1列以上塗られない行がある
  の両方を満足した時

よって、逆から塗った情報を調べるとうまくいく

E

h, w, m = map(int, input().split())
query = [list(map(int, input().split())) for _ in range(m)]

ans = dict()
height = {i for i in range(h)}
width = {i for i in range(w)}

for t, a, x in reversed(query):
    a -= 1
    if t == 1:
        if a in height:
            if x not in ans:
                ans[x] = 0
            ans[x] += len(width)
            height.discard(a)
    else:
        if a in width:
            if x not in ans:
                ans[x] = 0
            ans[x] += len(height)
            width.discard(a)

    if len(height) == 0 or len(width) == 0:
        break

if len(height) * len(width) > 0:
    if 0 not in ans:
        ans[0] = 0
    ans[0] += len(height) * len(width)

print(len(ans))
for key in sorted(ans.keys()):
    print(key, ans[key])