AtCoder Beginner Contest 126

ABC AtCoder Union-Find

A / Changing a Character

Python なので指定された番号の文字をlower()するだけ。

def solve(N: int, K: int, S: str):
    sl = list(S)

    sl[K-1] = sl[K-1].lower()

    print(''.join(sl))
    return

B / YYMM or MMYY

前半二文字と後半二文字で区切って、それぞれの部分で[1,12], 0 or [13,99]判定をする。

def solve(S: str):
    p1 = int(S[:2])
    p2 = int(S[2:])

    if(0 < p1 <= 12 and 0 < p2 <= 12):
        print('AMBIGUOUS')
    elif(0 < p1 <= 12 and (p2 == 0 or p2 > 12)):
        print('MMYY')
    elif((p1 == 0 or p1 > 12) and 0 < p2 <= 12):
        print('YYMM')
    else:
        print('NA')

    return

C / Dice and Coin

方針は、全部のサイコロの場合の確率を求めて、全部足しあげる。 1~Nまでのそれぞれのサイコロが出た場合の勝率は以下の通り。

\frac{1}{N} * \frac{1}{2}^t \\\ t = \log_2(\frac{K}{i}) 
def solve(N: int, K: int):
    ans = .0
    for i in range(1,N+1):
        if(i <= K):
            t = math.ceil(math.log2(K/i))
            ans += (1/N) * (1/2) ** t
        else:
            ans += 1/N

    print(ans)
    
    return

D / Even Relation

グラフが作れなくて終わり。

E / 1 or 2

Union-Find木は、自分ではちゃんと練習していたつもりでいたので、溶けなかったのはだいぶ悔しい。 この問題は、与えられる魔法を考慮したときに、「カードをめくる回数を一番少なくするにはどうしたらよいか？」を考える問題。 与えられるZは捨てて、XとYだけで、Union-Find木を構成すると、その連結成分が答え。

def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    uf = UnionFind(N)

    for i in range(M):
        uf.union(X[i],Y[i])
    
    # 連結成分の数が答え
    print(uf.num_graph())

    return

F

ちょっと見てない