ABC259 解説(Python)

Thumbnail

目次

A. GrowthRecord

  • Difficulty34(灰)

Xを境に変化量が変わるので、それで場合分け

N, M, X, T, D = map(int, input().split())
if X <= M <= N:
    print(T)
else:
    print(T - (X - M) * D)

B. Counterclockwise Rotation

  • Difficulty180(灰)

三角関数を利用したら良い。twitterを見ていると、知っているか知らないかで体感の難易度が大きく異なっていた模様

import math

a, b, d = map(int, input().split())
rad = math.radians(d)
x = a * math.cos(rad) - b * math.sin(rad)
y = a * math.sin(rad) + b * math.cos(rad)
print(x, y)

C. XX to XXX

  • Difficulty451(茶)

ランレングス圧縮に思い至らなかったので、アドホックな解放。シンプルにTの文字を前から見ていってSの対応する箇所と同じ文字なら別の配列(collect)に追加していく。

仮にSと文字が異なる場合はcollectの後ろの2つをみて、追加したい文字列と同じなら複製できる。違う場合はどうやっても一致させることができないので、"No"となる。

最終的にTとcollectを比較する。

S = list(input())
T = list(input())
if len(S) > len(T):
    print("No")
    exit()
collect = []

add_cnt = 0
for i in range(len(T)):
    if i - add_cnt < len(S) and S[i - add_cnt] == T[i]:
        collect.append(T[i])
    elif len(collect) >= 2 and collect[i - 1] == collect[i - 2] == T[i]:
        collect.append(T[i])
        add_cnt += 1
    else:
        print("No")
        exit()
    # print(collect)
if T == collect:
    print("Yes")
else:
    print("No")

D. Circumferences

  • Difficulty947(緑)

どの円がどの円と接しているかor交わっているか、の情報を保持できれば、最終的にSx,SyとTx, Tyが到達できるか判定できる。

UnionFind木で実装した。StartとGoalをどのようにUnionFind木に追加するか迷って、-1と-2を割り当てて追加した。回答を見ていると、接する円のindexを保持しておいて最終的に比較していた。(複数の円周上にあった場合でも別にどの円のindexをもっていても問題ない)

自分はいちいち追加する処理が発生していたので、indexを保持したほうがいいな。

class UnionFind:
    """Union Find木クラス
    Attributes:
        parent (list): 親要素を格納するリスト。親要素は自身のサイズを格納する。
    Notes:
        - parent[i] < 0 の場合、iは根。この時、-parent[i]はそのグループのサイズ
        - parent[i] = -1 とすると、iは独立。
    """

    def __init__(self, n):
        """
        Args:
            n (int): The number of objects. 要素数
        """
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """returns the root of x

        Args:
            x (int): The object to find the root of. 要素

        Returns:
            int: The root of 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):
        """unites the root of x and the root of y

        Args:
            x (int): The first object to union. 要素
            y (int): The second object to union. 要素
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:  # すでに同じ親
            return
        # union by size
        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):
        """returns the size of the group of x

        Args:
            x (int): The object to find the size of. 要素

        Returns:
            int: The size of the group of x.
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """returns True if the root of x is the same as the root of y

        Args:
            x (int): The first object to check. 要素
            y (int): The second object to check. 要素

        Returns:
            bool: True if the root of x is the same as the root of y.
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """returns the members of the group of x

        Args:
            x (int): The object to find the members of. 要素

        Returns:
            list: The members of the group of x.
        """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """returns the roots

        Returns:
            list: The roots.
        """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """returns the number of groups

        Returns:
            int: The number of groups.
        """
        return len(self.roots())

    def all_group_members(self):
        """returns all groups

        Returns:
            list: All group members.
        """
        return {r: self.members(r) for r in self.roots()}


N = int(input())
sx, sy, tx, ty = map(int, input().split())
X, Y, R = [0] * N, [0] * N, [0] * N
for i in range(N):
    X[i], Y[i], R[i] = map(int, input().split())
uf = UnionFind(N + 2)
for i in range(N):
    if (X[i] - sx) ** 2 + (Y[i] - sy) ** 2 == R[i] ** 2:
        uf.union(i, -1)
    if (X[i] - tx) ** 2 + (Y[i] - ty) ** 2 == R[i] ** 2:
        uf.union(i, -2)
    for j in range(i + 1, N):
        d = (X[i] - X[j]) ** 2 + (Y[i] - Y[j]) ** 2
        if not d < (R[i] - R[j]) ** 2 and d <= (R[i] + R[j]) ** 2:
            uf.union(i, j)
# print(uf.all_group_members())
if uf.find(-1) == uf.find(-2):
    print("Yes")
else:
    print("No")

E. LCM on Whiteboard

  • Diificulty1370(水)
  • 未回答