😎

AtCoder ABC229 個人的メモ

4 min read

A - First Grid

https://atcoder.jp/contests/abc229/editorial/2948
↑と同じ
条件を満たさないパターンは以下の2つなので、そのパターンか否かを判別
#.   |   .#
.#   |   #.
S1 = input()
S2 = input()

if S1[0] == S2[1] == "." or S1[1] == S2[0] == ".":
    print("No")
else:
    print("Yes")

B - Hard Calculation

AとBの各桁を足し算して10以上になるかを判別すればおk

A, B = input().split()

ans = 0
for i in range(min(len(A), len(B))):
    j = i + 1
    if int(A[-j]) + int(B[-j]) >= 10:
        ans = 1
        break

if ans:
    print("Hard")
else:
    print("Easy")

C - Cheese

チーズは1[g]ずつ載せることができるので、密度が大きいものから使っていけばおk

N, W = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(N)]

lst.sort()

weight = 0
value = 0
while weight < W and lst:
    a, b = lst.pop()
    res = min(W - weight, b)
    weight += res
    value += a * res

print(value)

D - Longest X

https://atcoder.jp/contests/abc229/editorial/2956

文字列Sの区間[l, r]の"."がK個以下となるr-l+1の最大値を求める。

from itertools import accumulate

S = input()
K = int(input())
N = len(S)

cumsum = list(accumulate((s == "." for s in S), initial=0))

ans = 0
right = 0
for left in range(N):
    while right < N and cumsum[right + 1] - cumsum[left] <= K:
        right += 1
    ans = max(ans, right - left)

print(ans)

E - Graph Destruction

頂点番号の大きい順にグラフに頂点と辺を追加していけばおk

union-findの実装
class UnionFind:
    """Union-Find(素集合データ構造(disjoint-set data structure)に対しての操作)"""

    def __init__(self, n: int):
        """
        Constructer(Initialize parameter in this class)

        Parameters
        ----------
        n : int
            Number of node

        Yields
        -----
        root : list
            When value is postive, express root of the node.
            When it is negative, express this node is root and size of set.
        """

        self.root = [-1] * n

    def find(self, x: int) -> int:
        """
        Search root of node x

        Parameters
        ----------
        x : int
            node x

        Returns
        -------
        x : int
            Root of node x
        """

        if self.root[x] < 0:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]

    def unite(self, x: int, y: int) -> bool:
        """
        Unite two set including node x and node y into one set.

        Parameters
        ----------
        x, y : int
            Node number

        Returns
        -------
        unite_result : bool
            False : Already two node include same set.
            True  : United
        """

        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.root[x] > self.root[y]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x
        return True

    def is_same(self, x: int, y: int) -> bool:
        """
        Determine if x and y are in same set.

        Parameters
        ----------
        x, y : int
            Node number

        Returns
        -------
        result : bool
            Determining result
        """

        return self.find(x) == self.find(y)

    def size(self, x: int) -> int:
        """
        Return size of set including node x.

        Parameters
        ----------
        x : int
            Node number

        Returns
        -------
        Size of set : int
        """

        return self.root[self.find(x)] * -1

N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(lambda n: int(n) - 1, input().split())
    # x < yとなるようにする
    if x > y:
        x, y = y, x
    edge[x].append(y)

union = UnionFind(N)
ans = [0] * (N)
for i in range(N - 2, -1, -1):
    # 頂点i+1が追加され連結成分が1つ増える(まだ頂点i+1に辺が追加されていない)
    ans[i] = ans[i + 1] + 1
    # 頂点i+1と既にグラフに追加されている頂点j(i<j)を結ぶ辺を追加する
    for adjacent_node in edge[i + 1]:
        # 頂点i+1と頂点n_nodeが既に連結なら、この辺によってグラフの連結成分の個数は変化しない
        if union.is_same(i + 1, adjacent_node):
            continue
        # そうでないならば、連結成分が1つ減る
        union.unite(i + 1, adjacent_node)
        ans[i] -= 1

print(*ans, sep="\n")

Discussion

ログインするとコメントできます