ABC413をPythonで（A～E、G）

デンソークリエイトプログラミングコンテスト2025（AtCoder Beginner Contest 413）の解答等の速報的まとめ

A問題

配列Aの合計とMを比較する

A

n, m = map(int, input().split())
print("Yes" if sum(map(int, input().split())) <= m else "No")

B問題

文字を全部作成して、setで重複を省く

B

n = int(input())
s = [input() for _ in range(n)]

strings = set()
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        strings.add(s[i] + s[j])

print(len(strings))

C問題

dequeにクエリ1をそのまま入れる
クエリ2で$c$と$k$の計算で個数を合計して値を求める

C

from collections import deque

q = deque()

for _ in range(int(input())):
    com = list(map(int, input().split()))
    if com[0] == 1:
        c, x = com[1:]
        q.append([c, x])
    else:
        k = com[1]
        ans = 0
        while q and k > 0:
            c_i, x_i = q.popleft()
            if c_i <= k:
                ans += c_i * x_i
                k -= c_i
            else:
                ans += k * x_i
                c_i -= k
                k = 0
                q.appendleft([c_i, x_i])
        print(ans)

D問題

今回考えないといけない公比$r$は

1. $r>=1 : (1, 2, 4, 8, 16)$
2. $r<-1 : (1, -2, 4, -8, 16)$
3. $r=-1 : (1, -1, 1, -1, 1)$

確認方法は

1. 単純にソート
2. 絶対値でソート
3. 数が2種類かつ絶対値の等しいかつ個数差が1個以下

D

import collections

def check(lst):
    for i in range(len(lst) - 1):
        if lst[i + 1] * lst[0] != lst[1] * lst[i]:
            return False
    return True

def check2(lst):
    counts = collections.Counter(lst)
    if len(counts) == 2:
        k_0, k_1 = counts.keys()
        # print(k_0, counts[k_0], ":", k_1, counts[k_1])
        if abs(k_0) == abs(k_1) and abs(counts[k_0] - counts[k_1]) <= 1:
            return True
    return False


for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))

    if check(sorted(a)) or check(sorted(a, key=abs)) or check2(a):
        print("Yes")
    else:
        print("No")

E問題

2のべき乗の幅で大小比較をするのはマージソートっぽく感じた
コードの一個目を比較して小さいほうを前にして返すようにしたらうまくいった

コードで$a_2$を前にするのは問題文の操作でいうと

1. $a_1$を反転
2. $a_2$を反転
3. $a_1 + a_2$で反転

と一致する

E

def like_merge(a):
    if len(a) <= 1:
        return a
    a_1 = like_merge(a[:len(a) // 2])
    a_2 = like_merge(a[len(a) // 2:])
    if a_1[0] < a_2[0]:
        return a_1 + a_2
    else:
        return a_2 + a_1

for _ in range(int(input())):
    n = int(input())
    p = list(map(int, input().split()))

    print(*like_merge(p))

F問題

問題文は言い換えると、ゴールまでの最短距離を青木君がつぶすから次善のルートが何手でゴールに到達できるか全マス求める。

言い換えが間違っているのかコーディングが悪いのかできなかった

※追記
実装が良くなかったぽい
次善の探索をゴールから逆算していたが冗長なコードのどこかでバグっていたみたい
単純に、BFSで2回目に到達したらスコア加算&deque追加をしたらAC出来た

F

from collections import deque


h, w, k = map(int, input().split())
INF = float("inf")
field = [[INF] * w for _ in range(h)]
q = deque()
count = [[0] * w for _ in range(h)]
for _ in range(k):
    r, c = map(lambda x:int(x) - 1, input().split())
    field[r][c] = 0
    q.append([r, c])
    count[r][c] = 2

while q:
    x, y = q.popleft()
    for i, j in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
        if 0 <= i < h and 0 <= j < w:
            count[i][j] += 1
            if count[i][j] == 2:
                field[i][j] = field[x][y] + 1
                q.append([i, j])

ans = 0
for i in range(h):
    # print(field[i])
    for j in range(w):
        if field[i][j] < INF:
            ans += field[i][j]

print(ans)

G問題

問題文は、障害物を8方向で連結したときに右上と左下が連結するかといえる
よってそれを実装するが、UnionFindのコードは基本的にparentが対象の個数$n$と一致するので、今回の$n = h \times w$では制限にひっかかる
よって、parentをdictにしてfindで確認するときにデフォルト値を埋め込むようにすればうまくいく

G

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = dict()

    def find(self, x):
        if x not in self.parents:
            self.parents[x] = -1
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)


h, w, k = map(int, input().split())
if h == w == 1 or k == 0:
    exit(print("Yes"))

UF = UnionFind(h * w + 2)

left = h * w
right = h * w + 1

for i in range(h - 1):
    UF.union(left, (i + 1) * w)
    UF.union(right, (i + 1) * w - 1)

for j in range(w):
    UF.union(left, (h - 1) * w + j)
    UF.union(right, j)

nums = set()
for _ in range(k):
    r_i, c_i = map(lambda x:int(x) - 1, input().split())
    n = r_i * w + c_i
    for i, j in [(r_i + 1, c_i + 1), (r_i + 1, c_i), (r_i + 1, c_i - 1),
                 (r_i, c_i + 1), (r_i, c_i - 1),
                 (r_i - 1, c_i + 1), (r_i - 1, c_i), (r_i - 1, c_i - 1)]:
        if 0 <= i < h and 0 <= j < w:
            n_i = i * w + j
            if n_i in nums:
                UF.union(n_i, n)
    nums.add(n)

print("No" if UF.same(left, right) else "Yes")