ABC425をPythonで（A～E）

ユニークビジョンプログラミングコンテスト2025 秋（AtCoder Beginner Contest 425）の解答等の速報的まとめ

A問題

問題文の通りに計算する

A

n = int(input())

ans = 0
for i in range(1, n + 1):
    ans += (-1) ** i * i ** 3

print(ans)

B問題

-1がある部分に、aに含まれない数字を順番に入れる。
最後に1~nまで含まれるか確かめる

B

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

s = set([a_i for a_i in a if a_i != -1])

target = 1
p = [0] * n
for i in range(n):
    if a[i] == -1:
        while target in s:
            target += 1
        p[i] = target
        s.add(target)
        target += 1
    else:
        p[i] = a[i]

if sorted(p) == sorted([i for i in range(1, n + 1)]):
    print("Yes")
    print(*p)
else:
    print("No")

C問題

数列を入れ替えるのは効率が悪いので現在の先頭の位置をメモする
累積和を利用して答えを求める

C

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

accu = [0]
for a_i in a + a:
    accu.append(accu[-1] + a_i)

head = 0

for _ in range(q):
    com = list(map(int, input().split()))
    if com[0] == 1:
        c = com[1]
        head = (head + c) % n
    else:
        l, r = com[1:]
        print(accu[r + head] - accu[l + head - 1])

D問題

DFS
各ターンでそのマスに

• 1回だけ到達したら黒にして次も探索する
• 2回以上到達したら塗らない&次の探索の開始地点にしない

D

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

INF = float('inf')
dist = [[INF] * w for _ in range(h)]
q = list()
check = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            q.append((i, j))
            dist[i][j] = 0
            check[i][j] = True

while q:
    lst = set()
    double = set()
    while q:
        x, y = q.pop()
        for i, j in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
            if 0 <= i < h and 0 <= j < w:
                if dist[i][j] > dist[x][y]:
                    dist[i][j] = dist[x][y] + 1
                    if (i, j) in lst:
                        double.add((i, j))
                    lst.add((i, j))
                    check[i][j] = True

    for (i, j) in lst:
        if (i, j) not in double:
            q.append((i, j))
            s[i][j] = "#"

ans = 0
for i in range(h):
    for j in range(w):
        ans += s[i][j] == "#"

print(ans)

E問題

組み合わせのnが最大5000だから事前に計算できる
パスカルの三角形と同値なので、それで前計算する
あとはクエリごとに計算する

E

t, m = map(int, input().split())

pascal_triangle = []
for i in range(5010):
    lst = []
    for j in range(i + 1):
        if j == 0 or j == i:
            lst.append(1)
        else:
            lst.append((pascal_triangle[-1][j - 1] + pascal_triangle[-1][j]) % m)
    pascal_triangle.append(lst)


def cmb(n, r):
    r = min(r, n - r)
    if r > n: return 0
    if r == 0: return 1
    if r == 1: return n
    return pascal_triangle[n][r]

for _ in range(t):
    n = int(input())
    c = list(map(int, input().split()))
    total = sum(c)
    ans = 1
    for c_i in c:
        ans *= cmb(total, c_i)
        ans %= m
        total -= c_i
    print(ans)