LoginSignup
0
0

ABC334をPythonで(A~E)

Posted at

ユニークビジョンプログラミングコンテスト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)

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0