yura1685

ABC447の解法記事

C - Insert and Erase A

最初に，$A$ を挿入・削除することで一致させることが可能かどうかを確かめたい．これは $S, T$ の両方から $A$ を削除すれば簡単に判定できます．問題の操作の最小回数については，文字列を $A$ 以外の文字で分割した区間ごとに $A$ を増減させると考えると解くことが出来ます．$C$ 問題の割に実装が面倒くさくないか？

S = input()
T = input()

S2 = ''.join([s for s in S if s != 'A'])
T2 = ''.join([t for t in T if t != 'A'])

if S2 != T2:
    exit(print(-1))

def Count(X):
    counter = []
    cnt = 0
    for x in X:
        if x == 'A':
            cnt += 1
        else:
            counter.append(cnt)
            cnt = 0
    counter.append(cnt)
    return counter

Sc, Tc = Count(S), Count(T)
ans = 0
for i in range(len(Sc)):
    ans += abs(Sc[i] - Tc[i])

print(ans)

D - Take ABC 2

$A, B, C$ は左から順に取るに越したことはないです．よって文字列を左から見ていって，$A, AB, ABC$ の個数を持つカウンタを足し引きすれば良いです．

S = input()
cnta, cntb, cntc = 0, 0, 0

for s in S:
    if s == 'A':
        cnta += 1
    if s == 'B':
        if cnta > 0:
            cntb += 1
            cnta -= 1
    if s == 'C':
        if cntb > 0:
            cntc += 1
            cntb -= 1

print(cntc)

E - Divide Graph

$2^0 + 2^1 + \cdots + 2^{n} < 2^{n+1}$ より，コストの大きい辺はなるべく削除せずに残しておきたいです．よってコストの大きい順に連結成分の個数が $2$ になるまで辺を張っていき，連結成分が $2$ 個になった後は連結成分が $1$ 個にならないように辺を張っていけば良いです．

from atcoder.dsu import DSU

N, M = map(int,input().split())
uf = DSU(N)
edge = []
for _ in range(M):
    U, V = map(int,input().split())
    edge.append((U-1, V-1))
edge.reverse()

groups = N
cost = []

for i in range(M):
    u, v = edge[i]
    if i <= N-3:
        if not uf.same(u, v):
            groups -= 1
        uf.merge(u, v)
    else:
        if groups > 2:
            if not uf.same(u, v):
                groups -= 1
            uf.merge(u, v)
        else:
            if uf.same(u, v):
                pass
            else:
                cost.append(M-i)

mod = 998244353
ans = 0
for c in cost:
    ans += pow(2, c, mod)
print(ans % mod)