ABC334をPythonで（A~E）

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

A

問題文の通りに書く

A

b, g = map(int, input().split())
print("Bat" if b > g else "Glove")

B

コーナーケースに気を付けて実装する
自分は結構手を焼いた

B

a, m, l, r = map(int, input().split())

l -= a
r -= a

def calc(x):
    res = abs(x) // m + 1
    return res

if l == r:
    print(0 if l % m > 0 else 1)
elif l == 0:
    print(calc(r))
elif 0 < l:
    print(calc(r) - calc(l - 1))
elif r == 0:
    print(calc(l))
elif r < 0:
    print(calc(l) - calc(r + 1))
else:
    print(calc(l) + calc(r) - 1)

C

残りが偶数の時は、ソートして隣接しているものでペアを組めばいい
奇数の時はどれを省くといいか全通り試す
ただし愚直にはやれないので小さいほうから順にやっていたパターンと大きいほうからとを組み合わせて確かめる

C

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

lst = [i for i in range(1, n + 1)]
for i in range(1, n + 1):
    if i not in a:
        lst.append(i)

lst.sort()

if k % 2 == 0:
    ans = sum(abs(j - i) for i, j in zip(lst[::2], lst[1::2]))
else:
    left = [0]
    for i, j in zip(lst[::2], lst[1::2]):
        left.append(abs(j - i) + left[-1])
    right = [0]
    for i, j in zip(lst[::-1][::2], lst[::-1][1::2]):
        right.append(abs(i - j) + right[-1])
    ans = min(l_i + r_i for l_i, r_i in zip(left, right[::-1]))

print(ans)

D

必要なトナカイの数が少ないほうから使うのが最適
よってソートと累積和と二部探索で答えを求める

D

from bisect import bisect

n, q = map(int, input().split())
r = sorted(map(int, input().split()))

for i in range(n - 1):
    r[i + 1] += r[i]

for _ in range(q):
    x = int(input())
    print(bisect(r, x))

E

それぞれのグループがどれに属するかをUnionFindで求める
緑に変えたときに起きるパターンが

1. 複数のグループをくっつけてグループの総数が減る
2. 1つのグループとだけくっついてグループの総数は変わらない
3. どれともくっつかずグループの総数が1増える

求める期待値は（各赤での変化後のグループ総数の和）÷（赤マスの数）で求まるので全通り計算する

E

from collections import defaultdict

class UnionFind:
    """
    URL : https://note.nkmk.me/python-union-find/
    """
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        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)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members

    def __str__(self):
        return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())


h, w = map(int, input().split())
field = [input() for _ in range(h)]
mod = 998244353

UF = UnionFind(h * w)

lst = []

for i in range(h):
    for j in range(w):
        if field[i][j] == "#":
            if i + 1 < h and field[i + 1][j] == "#":
                UF.union(i * w + j, (i + 1) * w + j)
            if j + 1 < w and field[i][j + 1] == "#":
                UF.union(i * w + j, i * w + j + 1)
        else:
            lst.append([i, j])

group = UF.group_count() - len(lst)

ans = 0
for i, j in lst:
    s = set()
    flag = True
    for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
        if 0 <= x < h and 0 <= y < w and field[x][y] == "#":
            flag = False
            s.add(UF.find(x * w + y))
    if flag:
        ans += group + 1
    else:
        ans += group - len(s) + 1

print(ans * pow(len(lst), -1, mod) % mod)