ABC 304 備忘録

概要

　今回はABC304（2023年6月3日21:00~22:40）についてポイントと自分の実装、および感想について述べていきたいと思う。※今回は諸事情により、コンテストにリアルタイムで参加できなかった。

A問題

ポイント

• 座っている人の年齢とそのインデックスを保持
• 最年少の年齢におけるインデックスをmin()で逐次更新
• 最年少のインデックスから時計回りに出力できるように配列を再構築

自分の実装

ABC_304_A.py

N =  int(input())

S = []
A = []
youngest = 10 ** 9 + 1
youngest_index = -1

for i in range(N):
    S_i, A_i = map(str, input().split())
    A_i = int(A_i)
    S.append(S_i)
    A.append(A_i)
    youngest = min(youngest, A_i)
    if youngest == A_i:
        youngest_index = i

ans = S[youngest_index:N] + S[0:youngest_index] if youngest_index != 0 else S

for i in ans:
    print(i)

B問題

ポイント

• 入力値の上から3桁しか考慮しないように配列で入力を保持

自分の実装

ABC_B.py:ABC_304_B.py

N = input()

if len(N) <= 2:
    print(int(N))
else:
    print(int(N[0:3]) * 10 ** (len(N)-3))

C問題

ポイント

• UnionFind を用いることで、条件を満たす人のグループを作成
• 最初の感染者である番号1の人と同じグループであるかを最後に判断させ、同じならばYesを出力

自分の実装

ABC_304_C.py

class UnionFind():
    # 初期化
    def __init__(self, n):
        self.par = [-1] * n
        self.rank = [0] * n
        self.siz = [1] * n

    # 根を求める
    def root(self, x):
        if self.par[x] == -1: return x # x が根の場合は x を返す
        else:
          self.par[x] = self.root(self.par[x]) # 経路圧縮
          return self.par[x]

    # x と y が同じグループに属するか (根が一致するか)
    def issame(self, x, y):
        return self.root(x) == self.root(y)

    # x を含むグループと y を含むグループを併合する
    def unite(self, x, y):
        # x 側と y 側の根を取得する
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry: return False # すでに同じグループのときは何もしない
        # union by rank
        if self.rank[rx] < self.rank[ry]: # ry 側の rank が小さくなるようにする
            rx, ry = ry, rx
        self.par[ry] = rx # ry を rx の子とする
        if self.rank[rx] == self.rank[ry]: # rx 側の rank を調整する
            self.rank[rx] += 1
        self.siz[rx] += self.siz[ry] # rx 側の siz を調整する
        return True
    
    # x を含む根付き木のサイズを求める
    def size(self, x):
        return self.siz[self.root(x)]

N, D = map(int, input().split())
D_square = D ** 2

coordinates = [[0, 0]]

for i in range(N):
    coordinates.append(list(map(int, input().split())))

UF = UnionFind(N+1)

for i in range(1, N):
    ith_index = coordinates[i]
    for j in range(i+1, N+1):
        jth_index = coordinates[j]
        if  (ith_index[0] -jth_index[0]) ** 2 + (ith_index[1] - jth_index[1]) ** 2 <= D_square:
            UF.unite(i, j)

for i in range(1, N+1):
    if UF.issame(1, i):
        print("Yes")
    else:
        print("No")

D問題

ポイント

•  切り分けられる領域の数を愚直に調べるとO(N^2)でTLEしてしまう
•  2分探索により、どの領域にあるかを、x, yともに不等式評価
•  いちごが載っている領域とその個数をdictで(key, value) = (領域, 個数)で記録することで計算量を節約
•  いちごが載っている領域数がケーキの領域数(A+1)*(B+1)よりも小さい場合はいちごが載っていない領域が存在するので、最小値は0であることに注意

自分の実装

ABC_304_D.py

from collections import deque, defaultdict
from bisect import bisect_left

W, H = map(int, input().split())

N = int(input())

# 二分探索
def binary_search(s, a, b, A, B):
    s_x, s_y = s[0], s[1]
    left_a, right_a = 0, A
    left_b, right_b = 0, B

    while left_a < right_a:
        mid_a = (left_a + right_a) // 2
        if a[mid_a] < s_x:
            left_a = mid_a + 1
        else:
            right_a = mid_a

    while left_b < right_b:
        mid_b = (left_b + right_b) // 2
        if b[mid_b] < s_y:
            left_b = mid_b + 1
        else:
            right_b = mid_b

    region = (left_a, left_b)
    return region
            
strawberries = deque()

for i in range(N):
    strawberries.append(list(map(int, input().split())))

A = int(input())

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

B = int(input())

b = list(map(int, input().split()))

# 各領域に存在するいちごの数をカウント
group = defaultdict(int)

for i in range(N):
    strawberry = strawberries.popleft()
    # 2分探索でどの領域にあるかを確認
    region = binary_search(strawberry, a, b, A, B)
    group[region] += 1

if len(group) >= (A+1) * (B+1):
    print(min(group.values()), max(group.values()))
else:
    print(0, max(group.values()))

E問題

ポイント

•  グラフのグループが分かれているかどうかを判断できればいいので、C問題と同じくUnionFindを用いてグラフを作成
•  いいグラフとなる条件の頂点同士を繋がってはいけない点としてset()で管理
•  各クエリで他の頂点同士を繋げた際にそれぞれの根の繋いではいけない頂点が含まれてしまう場合は No、そうでなければ Yes
•  いちいち新たに繋いだ点同士の根を結び直しているとTLE

自分の実装

ABC_304_E.py

class UnionFind():
    # 初期化
    def __init__(self, n):
        self.par = [-1] * n
        self.rank = [0] * n
        self.siz = [1] * n

    # 根を求める
    def root(self, x):
        if self.par[x] == -1: return x # x が根の場合は x を返す
        else:
          self.par[x] = self.root(self.par[x]) # 経路圧縮
          return self.par[x]

    # x と y が同じグループに属するか (根が一致するか)
    def issame(self, x, y):
        return self.root(x) == self.root(y)

    # x を含むグループと y を含むグループを併合する
    def unite(self, x, y):
        # x 側と y 側の根を取得する
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry: return False # すでに同じグループのときは何もしない
        # union by rank
        if self.rank[rx] < self.rank[ry]: # ry 側の rank が小さくなるようにする
            rx, ry = ry, rx
        self.par[ry] = rx # ry を rx の子とする
        if self.rank[rx] == self.rank[ry]: # rx 側の rank を調整する
            self.rank[rx] += 1
        self.siz[rx] += self.siz[ry] # rx 側の siz を調整する
        return True
    
    # x を含む根付き木のサイズを求める
    def size(self, x):
        return self.siz[self.root(x)]

N, M = map(int, input().split())

UF = UnionFind(N+1)

# 元々のグラフ
for i in range(M):
    u, v = map(int, input().split())
    UF.unite(u, v)

K = int(input())

# 繋げてはいけない組み合わせのメモ
out = [set() for i in range(N+1)]

# いいグラフである条件
for i in range(K):
    x, y = map(int, input().split())
    root_x, root_y = UF.root(x), UF.root(y)
    out[root_x].add(root_y)
    out[root_y].add(root_x)

Q = int(input())

for i in range(Q):
    # 追加で加える辺が結ぶ頂点
    p, q = map(int, input().split())
    # 追加で結んだ際にpに繋いではいけない頂点の根と一致した場合は"No"
    if UF.root(q) in out[UF.root(p)]:
        print("No")
    else:
        print("Yes")

感想

　今回はリアルタイムでは参加出来なかったが、もしやっていたとしたら時間内だとC問題までしか解けなかったと思う。D問題は2分探索の実装を尾も追いつくのに時間がかかったし、E問題は頂点同士を追加でつあげるのではなく、繋がって威はいけない頂点同士のグループを考えるということに解説を見るまで気づけなかった。ただ、解説を読んだところで普段はE問題まで実装できていなかったので、少し成長を感じた。