【Atcoder解法検討】ABC304 A~E Python

A - First Player

問題ページ : A - First Player

考察

円環の取り扱いは$%$(割った余り）を利用する。

コード

N = int(input())
S = []
A = []
age_min = 10 ** 10
youngest = -1
for i in range(N):
    s, a = input().split()
    S.append(s)
    if int(a) < age_min:
        youngest = i
        age_min = int(a)

for i in range(N):
    idx = (i + youngest) % N
    print(S[idx])

B - Subscribers

問題ページ : B - Subscribers

考察

題意どおり,$10^3$以下ならそのまま出力。
それ以外の場合は$x = 桁数\ -\ 3$として、$10^x$でわって小数点切り捨て（整数の割り算）、その後$10^x$をかける。

コード

N = int(input())

if N < 10 ** 3:
    print(N)
    exit()

keta = len(str(N))
x = 10 ** (keta-3)

print(N // x * x)

C - Virus

問題ページ : C - Virus

考察

グラフの問題として捉える。
すべての2点間距離がD以下の2人を結合する。
人1と連結しているか判定する。
距離D以下の判定は小数点誤差をさけるためルートを使わず距離の2乗で判定する。
人１との連結判定はDFS,BFS,Union Findいずれでも可能だが、Union FindをACLから使用するのが楽。

コード

from atcoder.dsu import DSU

N, D = map(int, input().split())
XY = [tuple(map(int, input().split())) for _ in range(N)]

def is_connect(p0,p1,D):
    dist = (p1[0] - p0[0]) ** 2 + (p1[1] - p0[1]) ** 2
    if dist <= D * D:
        return True
    else:
        return False
    
uf = DSU(N)

for i in range(N):
    for j in range(i+1, N):
        if is_connect(XY[i], XY[j], D):
            uf.merge(i,j)

for i in range(N):
    if uf.same(0,i):
        print("Yes")
    else:
        print("No")

D - A Piece of Cake

問題ページ : D - A Piece of Cake

考察

まず$(A+1) \times (B+1)$が$10^{10}$を超えるケースがあることに注意し計算量をケアすることが必要。
主客転倒というか視点の持ち方というか、「各ピースが何個のイチゴを載せているか」という視点だけでなく、「各イチゴがどのピースに載っているか」という視点も大事。
各ピースに載っているイチゴの数の管理は全ピースの保持数を二次元リストで持つとTLEする懸念ので、イチゴが一つ以上載っているピースのみを辞書型で管理する。
イチゴの載っていないピースがあるか（最小値が0か）は、辞書型の要素数と全ピース数$(A+1) \times (B+1)$を比較する。

コード

from collections import defaultdict
from bisect import bisect_left

W, H = map(int, input().split())
N = int(input())
berry_pos = [tuple(map(int, input().split())) for _ in range(N)]
Anum = int(input())
A = list(map(int, input().split()))
Bnum = int(input())
B = list(map(int, input().split()))

cnt = defaultdict(int)
G = set()

for p,q in berry_pos:
    x = bisect_left(A,p)
    y = bisect_left(B,q)
    cnt[(x,y)] += 1
    G.add((x,y))

max_num = 0
min_num = 10 ** 6

for g in G:
    max_num = max(max_num,cnt[g])
    min_num = min(min_num,cnt[g])

if len(G) < (Anum + 1) * (Bnum +1):
    min_num = 0

print(min_num, max_num)

E - Good Graph

問題ページ : E - Good Graph

考察

Gが与えられた段階では良いグラフですので、題意は「頂点$p_i$と頂点$q_i$を連結させることで、頂点$x_i$と頂点$y_i$を結びパスを生じさせるか？」ということになります。
この後者は「頂点$x_i$を含む連結成分の要素と頂点$y_i$を含む連結成分の要素を連結させるか？」ということ、すなわち「頂点$p_i$,頂点$q_i$がそれぞれ頂点$x_i$を含む連結成分,頂点$y_i$を含む連結成分のどちらか一方づつに含まれるか？」と同意となります。
このような問題を扱うのにはUnion Findが適しています。頂点$x_i$を含む連結成分をそのリーダー(親）で表します。

コード

from atcoder.dsu import DSU

N, M = map(int, input().split())
UV = [tuple(map(int, input().split())) for _ in range(M)]
K = int(input())
XY = [tuple(map(int, input().split())) for _ in range(K)]
Q = int(input())
PQ = [tuple(map(int, input().split())) for _ in range(Q)]

uf = DSU(N)
G = set()

for u,v in UV:
    u -= 1
    v -= 1
    uf.merge(u,v)

for x, y in XY:
    x -= 1
    y -= 1
    xp = uf.leader(x)
    yp = uf.leader(y)
    G.add((xp,yp))
    G.add((yp,xp))

for p,q in PQ:
    p -= 1
    q -= 1
    pp = uf.leader(p)
    qp = uf.leader(q)

    if (pp,qp) in G:
        print("No")
    else:
        print("Yes")

青色diff以上は後日挑戦